[Usaco2010 Hol]rocks 石头木头 【博弈、NIM和、SG函数】

【题目链接】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1777
http://ace.delos.com/ioiupload?d=gold&a=nejLCFTaRn6&lang=ch
【Experience】
呃,今天弄了一下那个论文,以及参详了DD——崔牛的神文的一部分。
神文地址:http://hi.baidu.com/yufuwan1/blog/item/4bb477443c425d4a500ffe2d.html
此乃转载地址,好像原地址已经消失不见了。。。
于是论文自然就是WC2009的:《从“k倍动态减法游戏”出发探究一类组合游戏问题》
然后表示,NIM积依然不懂,第一个例子就不懂。。。
幸好这题不用NIM积。。。
【算法分析】
首先我们可以发现,如果是离根距离为偶数的点上面的石头是不可能决定胜负的。
因为,假设一个人把一些石头从偶点移动一次,那么就到达一个奇点,然后另外一个人就能再从这个奇点移同样数目的石头到偶点。直到这些石头到根。
如果按照这个策略做的话,结果不会发现任何改变。
所以偶点的石头与胜负无关。
然后接下来我们来看奇点的石头。
假设我们从这个奇点移了一些石头,那么再偶数点上的石头再次对结果无关。
所以,每个奇点上的石头是独立的。
有了独立这个性质,那么我们就可以利用Sprague-Grundy Theorem
来处理。如果你看了上面崔牛那篇的第二部分,那么就很容易想到了。
因为是独立的游戏,那么SG(X)=SG(a1)^SG(a2)^...^SG(an)。(^即xor)
如果SG(X)=0,那么证明X是先手必败态。
然后每次只能移L这么多个石头,有一种很简单的方法得出每一个奇点的SG函数值。
就是SG=Rocks_Num%(L+1)。
如果你看了DD那篇神文。
就容易知道SG是怎么求出来的了。
就是画一个有向图,每个点代表剩下x个石子时候的局面,然后再连转移的有向边,然后。。。就能发现规律了。
于是根据Sprague-Grundy Theorem,我们可以轻易得到整个局面的SG函数。
然后剩下的问题是关心在它变那些值的时候我们怎么处理。
由于我们实际上就是需要维护整个局面的SG值,于是我们可以围观到这样的式子:
Ans=k ^ Ai
Ans’=k ^ Ai‘
于是Ans'=k ^ Ai ^ Ai ^ Ai'=Ans ^ Ai ^ Ai'
嗯,就这样。
【CODE】
/*
ID:jie22221
TASK:rocks
LANG:C++
*/
#include int N,T,L,ans,fa,i,w,x;
int d[10005],SG[10005];

int main(){
freopen("rocks.in","r",stdin);
freopen("rocks.out","w",stdout);
scanf("%d%d%d",&N,&T,&L);
d[1]=0; SG[1]=ans=0;
for (i=2;i<=N;i++){
scanf("%d%d",&fa,&w);
d[i]=d[fa]+1;
SG[i]=w%(L+1);
if (d[i]%2==1) ans^=SG[i];
}
for (i=1;i<=T;i++){
scanf("%d%d",&x,&w);
if (d[x]%2==1){
w%=(L+1);
ans^=SG[x]^w;
SG[x]=w;
}
if (ans==0) puts("No");
else puts("Yes");
}
}

加入对话

1条评论

留下评论

您的电子邮箱地址不会被公开。