2013年8月19日 18:53

BZOJ2819: Nim【树状数组+dfs序+倍增求LCA】

BZOJ

树上的Nim取石子游戏。

说白了就是,维护一棵树,支持:修改点权,询问一条路径上点权的xor值是否为零。

可以用树链剖分做。但是介于n和q都50w这么大感觉常数很DT。。

既然它只修改点的话,影响到的只是它这棵子树。那么很容易就想到了dfs序。这个子树就是连续一段。

先维护每个点dfs开始时和结束时的时间戳。修改的时候先在它自己的开始、结束位置上xor它自己变成零,然后再修改。

(x,y)路径上的xor值=query(x的开始) xor query(y的开始) xor lca(x,y)的点权。很好想通。LCA就倍增算一下好了。

没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define YES *o++='Y',*o++='e',*o++='s',*o++='\n'
#define NO *o++='N',*o++='o',*o++='\n'
const int maxn=500100,maxm=1000100;
int p[maxm],n1[maxm],h[maxn],begin[maxn],end[maxn],bit[maxm],st[maxn],a[maxn],n,ee=0,tot=0;
int anc[maxn][20],dep[maxn];	char buf[25000000],*o=buf,*pt=buf;
inline int getint(){
    int s=0;	while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; 
	return s;
}inline char getop(){
	while(*pt!='Q'&&*pt!='C')	pt++;	return *pt++;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}inline void dfs(int s){
	int top=0;
	begin[st[++top]=s]=dep[s]=++tot;
	while(top){
		int u=st[top],f=0;
		for(int i=h[u];~i;i=n1[i]){
			if(!~begin[p[i]]){
				begin[p[i]]=++tot;
				anc[p[i]][0]=u;
				dep[p[i]]=dep[u]+1;
				st[++top]=p[i];
				h[u]=n1[i];
				f=1;
				break;
			}
		}if(!f){
			end[u]=++tot;
			top--;
		}
	}
}inline int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	int k=dep[u]-dep[v],j=0;
	while(k){
		if(k&1)	u=anc[u][j];
		j++,k>>=1;
	}if(u==v)	return u;
	for(int j=19;~j;j--)
		if(anc[u][j]!=anc[v][j])	u=anc[u][j],v=anc[v][j];
	return anc[u][0];
}inline void modify(int i){
	for(int x=begin[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
	for(int x=end[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
}inline int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r^=bit[x];
	return r;
}int main(){
	fread(buf,1,25000000,stdin);
	n=getint();
	for(int i=1;i<=n;i++)	a[i]=getint();
	memset(h,-1,sizeof(h));
	memset(begin,-1,sizeof(begin));
	for(int i=1;i<n;i++)	ae(getint(),getint());
	dfs(1);
	for(int i=1;i<=n;i++)	modify(i);
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	int q=getint(),x,y,z;
	while(q--){
		if(getop()=='Q'){
			x=getint();y=getint();
			if(ask(begin[x])^ask(begin[y])^a[lca(x,y)])	YES;
			else	NO;
		}else{
			x=getint();y=getint();
			modify(x);
			a[x]=y;
			modify(x);
		}
	}return fwrite(buf,1,o-buf,stdout),0;
}

Comments(0)

Tags:

2013年6月12日 16:29

博弈论初探I【Nim取石子游戏】

专题

题目1:有n堆石子,第i堆有A(i)颗石子。两人依次从中拿取,规定每次只能从一堆中取若干根,可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

令C=A(1) xor A(2) xor A(3) xor ... xor A(n),若C>0,则记为利己态,用S表示,若C=0,则记为利他态,用T表示。

【定理1】对于一个S态,一定能从一堆石子中取出若干个,使其成为T态。

【证明】既然是S态,则此时C>0,我们要使得C变为0。

设C转化为二进制后,最高位的1是第p位。那么一定存在一个A(t)的二进制最高位的1是第p位。(显然,不然C的第p位不可能是1)

然后,把第t堆石子的个数变为x=A(t) xor C。因为A(t)和C的二进制最高位的1是同一位。那么异或之后这一位就变成了0。那么x一定小于A(t)。

此时的C'=A(1) xor A(2) xor ... xor A(t) xor C xor A(t+1) xor ... xor A(n)。把C带进去,得到

C'=A(1) xor A(2) xor ... xor A(n) xor A(1) xor A(2) xor ... xor A(n)。显然C'=0。

所以,只要在第t堆石子中取出A(t)-x颗石子,就把S态变为了T态。


【定理2】对于一个T态,从任意一堆取任意个石子出来,都会变为S态。

【证明】用反证法。设此时第i堆的石子数变成了A(i')。此时C=0。如果C'>0,那么命题就成立了。

假设C'=0。则C'=A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

因为C=0。所以C xor C'=0。则A(1) xor A(2) xor ... xor A(i) xor... xor A(n) xor A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

A(i) xor A(i')=0。A(i)=A(i')明显不对了。所以命题得证。


得到了这两个定理之后,我们可以发现,任何一个S态,我们都可以通过自己的控制将它转化成T态。而对方怎么做都是将T态再转回S态,很被动。所以只要先手是S态,总是可以根据定理1得到的策略获胜。



题目2:有n堆石子,第i堆有A(i)颗石子。两人依次从中拿取,规定每次只能从一堆中取若干根,可将一堆全取走,但不可不取,最后取完者为,求必胜的方法。

再来定义几个状态。一堆石子里只有一个石子,记为孤单堆。否则记为充裕堆。

在T态中,如果充裕堆的个数大于等于2,记为T2态,1个充裕堆,记为T1态,没有充裕堆,记为T0态。S0、S1、S2同理。

【定理3】在S0态中,若孤单堆的个数为奇数。那必输。T0态必赢。

【证明】也就是奇数个石子,每次取一个。很明显先去的人必输。


【定理4】在S1态中,方法正确就必胜。

【证明】如果孤单堆的个数是奇数,那么就把充裕堆取完;如果是偶数,就把充裕堆取的只剩1根。这样留下的就是奇数个孤单堆,对方先手。由定理3得,对方必输,己方必胜。


【定理5】S2态不可一次变为T0态。

【证明】显然,充裕堆不可能一次从2堆以上变为0。


【定理6】S2态可一次变为T2态。

【证明】由定理1得S态可以一次变为T态,而且不会一次取完整堆,那么充裕堆的个数是不会变的,由定理5得S2态不能一次变为T0态,那么转化的T态是T2态。


【定理7】T2态只能转变为S1或S2态。

【证明】由定理2得,T态一次只能变为S态。由于充裕堆数不会变为0。所以是S1或S2态。


【定理8】在S2态中,只要方法正确,就必胜。

【证明】由定理6得,先转化为T2态。由定理7,对方只能再转化回S1或S2态。由定理4,己方必胜。


【定理9】T2态必输。

【证明】同证明8。


我们得到了几个必胜态:S2,S1,T0。必输态:T2,T1,S0。


比较一下两题:

第一题的过程:S2-T2-S2-T2-.....-T2-S1-T0-S0-T0-...-S0-T0(全0)

第二题的过程:S2-T2-S2-T2-.....-T2-S1-S0-T0-S0-...-S0-T0(全0)

我们可以发现前面的过程是一样的。关键在于得到了S1态之后,怎样抉择使自己获胜。而这个是自己可以掌握的。

因此,我们只需要把T2态留给对方,迟早他会转化成S1态。己方就必胜。



HDU 1850

题意:题目1模型。首先判断是否先手必胜。如果必胜则输出第一次的可行方案数。

根据定理1,先得到C的二进制最高位的1是第p位。然后计算n个数中有多少个数最高位的1也是第p位即可。



#include<cstdio>
int a[105];
int main(){
    int n,Xor,t;
    while(scanf("%d",&n),n){
        Xor=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),Xor^=a[i];
        if(!Xor){ printf("0\n"); continue;} 
        int k=0,ans=0; while(Xor)k++,Xor>>=1;
        for(int i=1;i<=n;i++)if(a[i]&(1<<k-1))ans++;
        printf("%d\n",ans);
    }return 0;
}

HDU 1907 

题意:有n堆糖果,每次吃任意一堆中的任意个。可以吃完一堆。不能不吃。吃完最后的负。问先手输赢情况。

很明显就是上面的题目2模型。









#include<cstdio>
int main(){
    int tc; scanf("%d",&tc);
    int n,t;
    while(tc--){
        scanf("%d",&n); int Xor=0,k=0;
        for(int i=1;i<=n;i++) scanf("%d",&t),k+=t>1,Xor^=t;   
        if((Xor&&k>=1)||(!Xor&&!k))printf("John\n");
        else printf("Brother\n");
    }return 0;
}

HDU 2509 也转化为题目2模型。代码大同小异。

Comments(1)

Tags:

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1