【（博弈）dfs序+树状数组】BZOJ2819-Nim

【题目大意】

普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。现在对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：
1.随机选两个堆v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略，如果有，vfleaking将会考虑将这些石子堆作为初始局面之一，用来坑玩家。
2.把堆v中的石子数变为k。

【思路】

对于普通的Nim游戏，如果所有石子数量异或和为1，则必胜，否则不能。

现在这些堆组成了一棵树，我们用query(x)表示从x到根节点的异或值，显然u到v的路径上的异或和胃query(u) xor query(v) xor (num[lca(u,v)])(因为它们的最近公共祖先被重复异或了两次，抵消掉了，所以又要异或回来。)

第一种做法就是用数量剖分，映射到线段树上去解决。

由于每个u的值改变，它仅仅会影响到它及它子树的query值，而且一个节点及其子树的dfs序是连续的，可以用树状数组来维护一下。

关于利用dfs序相同性质的一道题目，和AC自动机结合更困难些→♦

树状数组维护xor和维护和一个道理，相当于一个区间修改点查询的树状数组。注意一下修改操作的方法：delta=num[u]^v，这样异或的时候原来的num[u]就抵消了，留下了v。这比较简单，但是不要忘记了修改后要num[u]→v。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 const int MAXN=+;

 const int DEG=;

 vector<int> E[MAXN];

 int start[MAXN],end[MAXN];

 int n,num[MAXN],e[MAXN];

 int anc[MAXN][DEG],dep[MAXN];

 int cnt=;

 void addedge(int u,int v)

 {

     E[u].push_back(v);

     E[v].push_back(u);

 }

 /*树状数组区间修改点查询部分*/

 int lowbit(int x)

 {

     return (x&(-x));

 }

 void modify(int x,int y,int delta)

 {

     if (x<y) swap(x,y);

     x++;

     while (x<MAXN) e[x]^=delta,x+=lowbit(x);

     while (y<MAXN) e[y]^=delta,y+=lowbit(y);

 }

 int query(int x)

 {

     int ret=;

     while(x) ret^=e[x],x-=lowbit(x);

     return ret;

 }

 /*dfs序部分及lca的初始化*/

 void dfs(int u,int fa,int d)

 {

     dep[u]=d;

     anc[u][]=fa;

     start[u]=++cnt;

     for (int i=;i<E[u].size();i++)

         if (E[u][i]!=fa) dfs(E[u][i],u,d+);

     end[u]=cnt;

 } 

 /*lca部分*/

 void getanc()

 {

     for (int i=;i<DEG;i++)

         for (int j=;j<=n;j++)

             anc[j][i]=anc[anc[j][i-]][i-];

 }

 int swim(int u,int H)

 {

     int i=;

     while (H)

     {

         if (H&) u=anc[u][i];

         i++;

         H>>=;

     }

     return u;

 }

 int lca(int u,int v)

 {

     if (dep[u]<dep[v]) swap(u,v);

     u=swim(u,dep[u]-dep[v]);

     if (u==v) return u;

     for (int i=DEG-;i>=;i--)

     {

         if (anc[u][i]!=anc[v][i])

         {

             u=anc[u][i];

             v=anc[v][i];

         }

     }

     return anc[u][];

 }

 /*main*/

 void init()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++) scanf("%d",&num[i]);

     for (int i=;i<n-;i++)

     {

         int u,v;

         scanf("%d%d",&u,&v);

         addedge(u,v);

     }

     dfs(,,);

     getanc();

     memset(e,,sizeof(e));

     for (int i=;i<=n;i++) modify(start[i],end[i],num[i]);

 }

 void solve()

 {

     int q;

     scanf("%d",&q);

     for (int i=;i<q;i++)

     {

         char c[];int u,v;

         scanf("%s%d%d",c,&u,&v);

         if (c[]=='Q')

         {

             int LCA=lca(u,v);

             int ans=query(start[u])^query(start[v])^num[LCA];

             if (ans) puts("Yes");else puts("No");

         }

         else

         {

             modify(start[u],end[u],num[u]^v);

             num[u]=v;

         }

     }

 }

 int main()

 {

     init();

     solve();

     return ;

 }

巴特西

【（博弈）dfs序+树状数组】BZOJ2819-Nim

最新文章

热门文章