【BZOJ2819】Nim

Description

著名游戲設(shè)計(jì)師vfleaking，最近迷上了Nim。普通的Nim游戲?yàn)?#xff1a;兩個(gè)人進(jìn)行游戲，N堆石子，每回合可以取其中某一堆的任意多個(gè)，可以取完，但不可以不取。誰(shuí)不能取誰(shuí)輸。這個(gè)游戲是有必勝策略的。于是vfleaking決定寫(xiě)一個(gè)玩Nim游戲的平臺(tái)來(lái)坑玩家。
為了設(shè)計(jì)漂亮一點(diǎn)的初始局面，vfleaking用以下方式來(lái)找靈感：拿出很多石子，把它們聚成一堆一堆的，對(duì)每一堆編號(hào)1,2,3,4,...n,在堆與堆間連邊，沒(méi)有自環(huán)與重邊，從任意堆到任意堆都只有唯一一條路徑可到達(dá)。然后他不停地進(jìn)行如下操作：
1.隨機(jī)選兩個(gè)堆v,u，詢問(wèn)若在v到u間的路徑上的石子堆中玩Nim游戲，是否有必勝策略，如果有，vfleaking將會(huì)考慮將這些石子堆作為初始局面之一，用來(lái)坑玩家。
2.把堆v中的石子數(shù)變?yōu)閗。
由于vfleaking太懶了，他懶得自己動(dòng)手了。請(qǐng)寫(xiě)個(gè)程序幫幫他吧。

Input

?第一行一個(gè)數(shù)n，表示有多少堆石子。
接下來(lái)的一行，第i個(gè)數(shù)表示第i堆里有多少石子。
接下來(lái)n-1行，每行兩個(gè)數(shù)v,u，代表v,u間有一條邊直接相連。
接下來(lái)一個(gè)數(shù)q，代表操作的個(gè)數(shù)。
接下來(lái)q行，每行開(kāi)始有一個(gè)字符：
如果是Q，那么后面有兩個(gè)數(shù)v,u，詢問(wèn)若在v到u間的路徑上的石子堆中玩Nim游戲，是否有必勝策略。
如果是C，那么后面有兩個(gè)數(shù)v,k，代表把堆v中的石子數(shù)變?yōu)閗。
對(duì)于100%的數(shù)據(jù)：
1≤N≤500000, 1≤Q≤500000, 0≤任何時(shí)候每堆石子的個(gè)數(shù)≤32767
其中有30%的數(shù)據(jù)：
石子堆組成了一條鏈，這3個(gè)點(diǎn)會(huì)導(dǎo)致你DFS時(shí)爆棧（也許你不用DFS？）。其它的數(shù)據(jù)DFS目測(cè)不會(huì)爆。
注意：石子數(shù)的范圍是0到INT_MAX

Output

對(duì)于每個(gè)Q，輸出一行Yes或No，代表對(duì)詢問(wèn)的回答。

Sample Input

【樣例輸入】
5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3

Sample Output

Yes
No
Yes
Yes
Yes

題解：一個(gè)常識(shí)結(jié)論：Nim游戲先手必勝當(dāng)且僅當(dāng)所有堆的異或和不為0，否則先手必輸

然后用樹(shù)狀數(shù)組+倍增LCA維護(hù)DFS序的異或和就行了（當(dāng)然，如果你維護(hù)的是入棧出棧序，可以不用倍增LCA）

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=500010; int n,m,cnt; int to[maxn<<1],next[maxn<<1],head[maxn],fa[maxn][20],dep[maxn],s[maxn],p[maxn],q[maxn],v[maxn]; char str[10]; int rd() {int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();return ret*f; } void add(int a,int b) {to[cnt]=b,next[cnt]=head[a],head[a]=cnt++; } void dfs(int x) {p[x]=++p[0];for(int i=head[x];i!=-1;i=next[i])if(to[i]!=fa[x][0])fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);q[x]=p[0]; } void updata(int x,int val) {if(!x) return ;for(int i=x;i<=n;i+=i&-i) s[i]^=val; } int query(int x) {int i,ret=0;for(i=x;i;i-=i&-i) ret^=s[i];return ret; } int main() {scanf("%d",&n);int i,j,a,b,c,d;memset(head,-1,sizeof(head));for(i=1;i<=n;i++) v[i]=rd();for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b),add(b,a);dep[1]=1,dfs(1);for(i=1;i<=n;i++) updata(p[i],v[i]),updata(q[i]+1,v[i]);for(j=1;(1<<j)<=n;j++)for(i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];m=rd();for(i=1;i<=m;i++){scanf("%s",str),a=rd(),b=rd();if(str[0]=='Q'){c=a,d=b;if(dep[a]<dep[b]) swap(a,b);for(j=19;j>=0;j--) if(dep[fa[a][j]]>=dep[b]) a=fa[a][j];if(a!=b){ for(j=19;j>=0;j--) if(fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];a=fa[a][0];}if(query(p[c])^query(p[d])^v[a]) printf("Yes\n");else printf("No\n");}if(str[0]=='C'){updata(p[a],v[a]),updata(q[a]+1,v[a]);updata(p[a],b),updata(q[a]+1,b);v[a]=b;}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/CQzhangyu/p/7044261.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ2819】Nim 树状数组+LCA的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。