abc308 G
比較 scrambled egg 吧。
引理：若 \(x<y<z\)，那麽 \(\min\{x⊕y,y⊕z\}<x⊕z\)。換句話説，blackboard 上有用的只有相鄰的數。
證明：加入考慮到了第 \(i\) 位。若 \(x \& (1<<i),y\& (1<<i),z \& (1<<i)\) 不同為 \(1\)，那麽要麽是 \(0,0,1\) 要麽是 \(0,1,1\)。前者 \(x⊕y<x⊕z\)，後者 \(y⊕z<x⊕z\)。而 \(x<y<z\)，所以不可能一直同爲 \(1\)，所以引理成立。
同樣，若 \(x\le y\le z\)，那麽 \(\min\{x⊕y,y⊕z\}\le x⊕z\)。
只需要用 set 維護就可以了。
code
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
int q;
multiset<int> nums;
multiset<int> xors;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>q;
while (q--){
int ty,x;
cin>>ty;
if (ty!=3){
cin>>x;
}
if (ty==1){
nums.insert(x);
auto it=nums.lower_bound(x);
int l=*prev(it),r=*next(it);
if (it!=nums.begin() && next(it)!=nums.end()){
xors.erase(xors.find(l^r));
}
if (it!=nums.begin()){
xors.insert(l^x);
}
if (next(it)!=nums.end()){
xors.insert(x^r);
}
}
else if (ty==2){
auto it=nums.lower_bound(x);
int l=*prev(it),r=*next(it);
if (it!=nums.begin() && next(it)!=nums.end()){
xors.insert(l^r);
}
if (it!=nums.begin()){
xors.erase(xors.find(l^x));
}
if (next(it)!=nums.end()){
xors.erase(xors.find(x^r));
}
nums.erase(nums.find(x));
}
else{
cout<<*(xors.begin())<<endl;
}
}
return 0;
}
// 413!413!413!
abc307G
比較 scrambled egg 吧。怎麽評分 \(2330\)，虛高。
很顯然一個加一，一個減一，sum 是不變的。於是根據條件，可以確定所有數是哪些數。
假如有一個數是 \(x\)，有 \(cnt\) 個，可以 dp 如下：
\(dp_{i,j}\) 表示 \(1\sim i\) 中有 \(j\) 個 \(x\) 的最小步數。這樣可以算出來 \(i+1\) 沒有動之前是什麽。
轉移很簡單。
code
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 5e3+3;
ll n,sum;
ll a[N],s[N],x,f,cnt;
ll dp[N][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<=n; i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
sum+=a[i];
}
x=sum/n;
cnt=n-abs(sum-x*n);
f=((sum-x*n)<0?-1:1);
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for (int i=0; i<=n; i++){
for (int j=max(0ll,i-(n-cnt)); j<=min(i*1ll,cnt); j++){
ll ad=s[i]-j*x-(i-j)*(x+f);
// to x
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+abs(a[i+1]+ad-x));
// to x+f
dp[i+1][j]=min(dp[i+1][j],dp[i][j]+abs(a[i+1]+ad-(x+f)));
}
}
cout<<dp[n][cnt]<<endl;
return 0;
}
// 413!413!413!