CF939 D
- 让你把区间分成 \(k\) 段, 段内用 \(xor\) 连接, 段之间用 \(or\) 连接,问你在结果不大于 \(x\) 的前提下, \(k\) 的最大值
- \(1 \leq n \leq 10^5, 0 \leq x,a_i \leq 2^30\)
- 标签:正向思维,二进制操作,按位贪心(从高到低)
- 参考题解1,参考题解2
- 注释版code
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
using namespace std;
using ll=long long;
const int N=1e5+5;
int t,n,x,ans=-1;
inline void sol(vector<int> a,const int p=30){// now deal with dep p
if(p<0) return ans=max(ans,(int)a.size()),void();
vector<int> pos;//pos: the set of the positione of all element that is 1 in pth bit
//Attention: pos take account for postion, rather than the concrete element
F(i,0,(int)a.size()-1){
if((a[i]>>p)&1) pos.emplace_back(i);
}
//odd
if(pos.size()%2==1 && ((x>>p)&1)==0) return;
//the pth of x is 0 => fail?
if(pos.size()%2==1 && ((x>>p)&1)==1) return sol(a,p-1);
//the pth of x is 1 => continue to solve
//even
bool rmv[(int)a.size()];
vector<int> b,c=a;//copy a to c
memset(rmv,0,sizeof(rmv));
//create the new seq
for(int i=0;i<(int)pos.size();i+=2){//every postion with 1
for(int j=pos[i]+1;j<=pos[i+1];++j){
rmv[j]=1; c[pos[i]]^=c[j];
}
}
F(i,0,(int)a.size()-1){
if(!rmv[i]) b.emplace_back(c[i]);
}
//make decision
if(((x>>p)&1)==0) return sol(b,p-1);//注意是return.两种情况选其一,单次复杂度就是 O(N)
ans=max(ans,(int)b.size());
//如果x上的这一位是1,第一,若按b这种分法,那么已经最优了
return sol(a,p-1);
//第二,那么其实这一位的限制没有任何意义,仍然踩在a的基础上,直接去考虑下一位.
}
//核心:倒着做,简单来说对于每一次操作,奇数个1就直接考虑最终结果,
//偶数个1就按最优策略(相邻两两配对)添加xor,这样能使这一位上的异或和最终一定为0(尽可能小),剩下没确定符号的位置在solve(b,p-1)中继续讨论
//发现了吗,没有讨论or添加的过程,或者换句话说or的添加过程是依靠贪心来约束的.
//b.size()即段数,不一定最优
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>t; while(t--){
cin>>n>>x;
vector<int> a(n);
F(i,0,n-1) cin>>a[i];
ans=-1;
sol(a);
cout<<ans<<'\n';
}
return 0;
}
- 反思:
- 经典的二进制贪心,从低位到高位。核心在以贪心的方式把 \(or\) 运算给回避掉了,这样就这剩下一种运算需要处理。
- 另一方面就是直白的正向思维(感觉有点儿反套路化逆向思维的感觉),就逐渐逐渐加符号上去,而不是先全填成 \(or\) 或者 \(xor\) 再去改。想多了的话反而容易遭。
- 二进制贪心不一定是什么一个前缀相同然后0,1之间讨论大小关系, 但共同点是两种贪心都和势能很像:只关注已有的条件来推测最终的结果,中间具体状态不关心。