注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2819]Nim  

2015-06-20 15:25:31|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2819: Nim

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1219  Solved: 464
[Submit][Status][Discuss]

Description

著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面,vfleaking用以下方式来找灵感:拿出很多石子,把它们聚成一堆一堆的,对每一堆编号1,2,3,4,...n,在堆与堆间连边,没有自环与重边,从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作:

1.随机选两个堆v,u,询问若在v到u间的路径上的石子堆中玩Nim游戏,是否有必胜策略,如果有,vfleaking将会考虑将这些石子堆作为初始局面之一,用来坑玩家。
2.把堆v中的石子数变为k。

由于vfleaking太懒了,他懒得自己动手了。请写个程序帮帮他吧。

Input

 第一行一个数n,表示有多少堆石子。
接下来的一行,第i个数表示第i堆里有多少石子。
接下来n-1行,每行两个数v,u,代表v,u间有一条边直接相连。
接下来一个数q,代表操作的个数。
接下来q行,每行开始有一个字符:
如果是Q,那么后面有两个数v,u,询问若在v到u间的路径上的石子堆中玩Nim游戏,是否有必胜策略。
如果是C,那么后面有两个数v,k,代表把堆v中的石子数变为k。

对于100%的数据:
1≤N≤500000, 1≤Q≤500000, 0≤任何时候每堆石子的个数≤32767
其中有30%的数据:
石子堆组成了一条链,这3个点会导致你DFS时爆栈(也许你不用DFS?)。其它的数据DFS目测不会爆。

注意:石子数的范围是0到INT_MAX

Output

对于每个Q,输出一行Yes或No,代表对询问的回答。

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

HINT

Source

Solution

直接树剖。线段树维护区间异或值。
1A好开森

Code

/**************************************************************
    Problem: 2819
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:7744 ms
    Memory:48708 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B,op;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 1<<19
int n,t[N<<1],d,m,et,la[N],top[N],fa[N],son[N],siz[N],dep[N],v[N],x,y,id[N],tim,i,ans,st;
struct E{int to,nxt;}e[N<<1];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
#define swap(a,b) (st=a,a=b,b=st)
void dfs(int x,int f){
    siz[x]=1,dep[x]=dep[fa[x]=f]+1;
    for(int i=la[x];i;i=e[i].nxt)if(e[i].to!=f){
        dfs(e[i].to,x);siz[x]+=siz[e[i].to];
        if(siz[son[x]]<siz[e[i].to])son[x]=e[i].to;
    }
}
void dfs2(int x,int t){
    if(id[x]=++tim,top[x]=t,son[x])dfs2(son[x],t);
    for(int i=la[x];i;i=e[i].nxt)
    if(e[i].to!=fa[x]&&e[i].to!=son[x])dfs2(e[i].to,e[i].to);
}
void query(int l,int r){
    for(l+=d-1,r+=d+1;l^r^1;l>>=1,r>>=1)~l&1?ans^=t[l^1]:1,r&1?ans^=t[r^1]:1;
}
void getlca(int x,int y){
    int fx=top[x],fy=top[y];ans=0;
    while(fx!=fy){
        if(dep[fx]<dep[fy])swap(x,y),fx=top[x],fy=top[y];
        query(id[fx],id[x]),x=fa[fx],fx=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);query(id[x],id[y]);
    puts(ans?"Yes":"No");
}
int main(){
    for(n=F(),i=1;i<=n;i++)v[i]=F();
    for(i=1;i<n;i++)x=F(),y=F(),add(x,y),add(y,x);
    for(dfs(1,0),dfs2(1,1),d=1;d<=n+1;d<<=1);
    for(i=1;i<=n;i++)t[id[i]+d]=v[i];
    for(i=n+d>>1;i;i--)t[i]=t[i<<1]^t[i<<1|1];
    for(m=F();m--;){
        while(op=getc(),op!='Q'&&op!='C');
        if(op=='Q')x=F(),y=F(),getlca(x,y);
        else for(t[i=id[F()]+d]=F();i>>=1;t[i]=t[i<<1]^t[i<<1|1]);
    }
}
  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018