BJ 集训测试2 Problem A 游戏

BJ 集训测试2 Problem A 游戏

​​我们取线性基，当石子堆数超过30时线性基大小小于石子堆数，因此一定可以消出一个异或和为0的集合。

据此我们只需要暴力，当询问区间长度大于30时答案为Yes，否则我们提出这个区间然后消元即可。

时间复杂度O(nlogn+nlog2a) 。 考虑经典博弈问题nim游戏 如果后手必胜就要求我们这个区间内的所有异或是0 那么题目变成给定区间 选定区间 求区间的子集是否存在异或为0的子集 那么考虑到线性基 因为权值大小最多30位 那么30个之后一定能把线性基插满也就会一定存在这样的子集 输出yes即可 否则的话直接用线性基处理即可 但是这个区间修改怎么办 那考虑线段树 在线段树上维护两个标记 f0,f1分别表示这一位如果是0 我经过这些操作之后会变成什么 下放的时候考虑标记是怎么构成的 比如讲两个1的标记合并 那么设父节点标记分别为f0,f1 如果我这个节点1的地方成了0 那么查询我父节点0是否会变成1 那么我的tree[x].f1=(f1&tree[x].f1)|(f0&(~tree[x].f1)) tree[x].f0=(f1&tree[x].f0)|(f0&(~tree[x].f0)) 我上一位是1的地方 在我这一位0如果会变成1 那么他仍然会变成1 反之 如果如果我0的地方还是0 那么我从上一位变过来的时候如果会变成1 我也将他更新成1

#include#include#include#define N 110000#define lc x<<1#define rc x<<1|1#define rg registerusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ int f0,f1;}tree[N<<2];int bin[31],n,q,a[N],p[33];inline void add(int x,int v0,int v1){ tree[x].f0=(v1&tree[x].f0)|(v0&(~tree[x].f0)); tree[x].f1=(v1&tree[x].f1)|(v0&(~tree[x].f1));}inline void build(int x,int l,int r){ tree[x].f0=0,tree[x].f1=bin[30]-1; if (l==r) {tree[x].f1&=a[l];return;} int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);}inline void pushdown(int x){ int f0=tree[x].f0,f1=tree[x].f1;add(lc,f0,f1);add(rc,f0,f1);tree[x].f0=0;tree[x].f1=bin[30]-1;}inline void modify(int x,int l,int r,int l1,int r1,int v,int ty){ if (l1<=l&&r1>=r){ if(ty==1){tree[x].f0&=v;tree[x].f1&=v;return;} if (ty==2){tree[x].f0|=v;tree[x].f1|=v;return;} tree[x].f0^=v;tree[x].f1^=v;return; }pushdown(x);int mid=l+r>>1; if (l1<=mid) modify(lc,l,mid,l1,r1,v,ty);if (r1>mid) modify(rc,mid+1,r,l1,r1,v,ty);}inline int query(int x,int l,int r,int p){ if (l==r) return tree[x].f1; int mid=l+r>>1;pushdown(x); if (p<=mid) return query(lc,l,mid,p);else return query(rc,mid+1,r,p);}inline bool insert1(int x){ for (rg int i=30;~i;--i){ if (!(x&bin[i])) continue; if (!p[i]) {p[i]=x;break;} x^=p[i]; }return x!=0;}int main(){ freopen("stone.in","r",stdin); n=read();for (rg int i=1;i<=n;++i) a[i]=read(); for (rg int i=0;i<=30;++i) bin[i]=1<30) {puts("Yes");continue;}bool flag=0;memset(p,0,sizeof(p)); for (rg int j=l;j<=r;++j){ x=query(1,1,n,j); if (insert1(x)) continue;else {puts("Yes");flag=1;break;} }if (!flag) puts("No"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。