首页 > 代码库 > 【BZOJ】【2819】NIM

【BZOJ】【2819】NIM

2024-10-23 13:17:39   210人阅读

这题……咋说捏，其实是一道披着博弈论外衣的树上操作问题……

随便用dfs序或者树链剖分转成序列，然后查询路径上的所有点的NIM和（异或和）就行了，毕竟除了是在树上以外，就是裸的NIM问题。

 

树链剖分：一开始把线段树写跪了，然后输出“Yes”和“No”的时候全部大写了，再然后发现线段树空间开小了……

 

代码如下：

技术分享
  1 //BZOJ 2819  2 #include<cstdio>  3 #include<vector>  4 #include<cstring>  5 #include<cstdlib>  6 #include<iostream>  7 #include<algorithm>  8 #define rep(i,n) for(int i=0;i<n;++i)  9 #define F(i,j,n) for(int i=j;i<=n;++i) 10 #define D(i,j,n) for(int i=j;i>=n;--i) 11 #define pb push_back 12 using namespace std; 13 const int N=500010; 14 #define debug 15 int n,a[N],t[N<<2],fa[N],top[N],dep[N],son[N],size[N],tid[N],cnt=0; 16 vector<int>G[N]; 17 bool vis[N]; 18  19 #define mid (l+r>>1) 20 #define L (o<<1) 21 #define R (o<<1|1) 22 void updata(int o,int l,int r,int pos,int v){ 23     if (l==r) t[o]=v; 24     else{ 25         if (pos<=mid) updata(L,l,mid,pos,v); 26         else updata(R,mid+1,r,pos,v); 27         t[o]=t[L]^t[R]; 28     } 29 } 30  31 int ql,qr,ans=0; 32 void query_it(int o,int l,int r){ 33     if (ql<=l && qr>=r) ans^=t[o]; 34     else{ 35         if (ql<=mid) query_it(L,l,mid); 36         if (qr>mid) query_it(R,mid+1,r); 37     } 38 } 39 //segment tree end 40  41 void dfs(int x,int f,int deep){ 42     int y,maxsize=0; 43     vis[x]=1; fa[x]=f; dep[x]=deep; size[x]=1; son[x]=0; 44     rep(i,G[x].size()){ 45         y=G[x][i]; 46         if (vis[y]) continue; 47         dfs(y,x,deep+1); 48         size[x]+=size[y]; 49         if (size[y]>maxsize) maxsize=size[y],son[x]=y; 50     } 51 } 52  53 void connect(int x,int f){ 54     tid[x]=++cnt; 55     top[x]=f; vis[x]=1; 56     if (son[x]) connect(son[x],f); 57     rep(i,G[x].size()){ 58         int y=G[x][i]; 59         if (!vis[y]) connect(y,y); 60     } 61 } 62  63 void query(int x,int y){ 64     while(top[x]!=top[y]){ 65         if (dep[top[x]]<dep[top[y]]) swap(x,y); 66         ql=tid[top[x]]; qr=tid[x]; 67         query_it(1,1,n); 68         x=fa[top[x]]; 69     } 70     if (dep[x]>dep[y]) swap(x,y); 71     ql=tid[x]; qr=tid[y]; 72     query_it(1,1,n); 73 } 74  75 int main(){ 76 //    freopen("file.in","r",stdin); 77     scanf("%d",&n); 78     F(i,1,n) scanf("%d",&a[i]); 79     int x,y; 80     F(i,2,n){ 81         scanf("%d%d",&x,&y); 82         G[x].pb(y); 83         G[y].pb(x); 84     } 85     dfs(1,0,1); 86     memset(vis,0,sizeof vis); 87     connect(1,1); 88     F(i,1,n) updata(1,1,n,tid[i],a[i]); 89     int q; 90     scanf("%d",&q); 91     char cmd[3]; 92     F(i,1,q){ 93         scanf("%s%d%d",cmd,&x,&y); 94         if (cmd[0]==‘Q‘){ 95             ans=0; 96             query(x,y); 97             printf(ans ? "Yes\n" : "No\n"); 98         } 99         else updata(1,1,n,tid[x],y);100     }101     return 0;102 }
View Code

 

【BZOJ】【2819】NIM


联系
我们