CF1610I Mashtali vs AtCoder(博弈论)

2021/11/27 6:10:26

本文主要是介绍CF1610I Mashtali vs AtCoder(博弈论),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

一天,小A和小B两人在玩一种非常有趣的游戏。该游戏是一棵有\(n\)个节点的树,树上有\(k\)个关键点\(1,2,3,...,k\),小A和小B轮流进行操作(小A进行第一次操作),每次操作为:

  1. 将树上任意一条边删除(无边可删的玩家算输)
  2. 将不能到达关键点的边删除

当然,小A和小B都很聪明,他们每次操作都不会失误。

现在他们将要举行\(n\)场游戏(对于第\(i\)场游戏,\(k=i\)),小A想知道,他对于每场游戏是否能获胜。

若第\(i\)局游戏小A可以获胜,则输出\(1\),否则输出\(2\)。

Solution

删边游戏:传送门

结论:\(SG\)等于儿子节点的\(SG+1\)的异或和。

对于\(k=1\)的情况,直接用上述结论求\(SG\)即可。

考虑\(k>1\)的情况,在此之前,先思考一下如何\(O(n)\)求不同根的\(SG\)。

画画图后,发现\(SG\)函数能直接换根做,这样\(SG[i]^=((SG[fa[i]] \oplus SG[i]+1)+1)\)

但其实跟这道题没什么关系

回到正题,发现在关键点间的路径,你删除任意一条,都只会删除这一条(你搁着搁着呢?!),所以想删除完\(cnt1\)条关键点的路径,需要\(cnt1\)步。

我们感性理解一下,当你删除关键点间路径时,会将一个连通块拆成两个连通块,即拆分成多个相同规则的删边游戏,即为\(multi-SG\)。于是,我们对每个删边游戏求\(SG\),最后根据\(multi-SG\)的结论,\(SG\)为被拆分出来的后继游戏的\(SG\)异或和。

所以对于\(k>1\)的情况的\(SG\)为:关键点间路径所构成的连通块所连接的点(不在关键点路径上)的\(SG\)值得异或和。

说得再形象一点就是:将关键点间的路径的联通块缩点,将连接到联通块的边全部连到点上,这时\(k>1\)的\(SG\)值又可以看成删边游戏来解释,只不过没有+1。

最后,求出当前局面\(SG\)值后,还有\(cnt1\)条边需要删,则需要判断再删\(cnt1\)条边后谁是赢家。

于是,这道题就差不多做完了。考虑代码实现,对于关键点,每进行一次游戏,关键点会+1,那么如何去更新关键点联通块呢?

发现题目关键点为\(1,2,...,k\),发现是有顺序的,而且每次答案只会受到当前关键点添加进去所造成的影响,于是可以继承\(i-1\)好关键点的信息,每次往1号节点那边靠,这样即可较为轻松的求的答案。

那么如果题目关键点一次性给出完,且询问少数次,还可以直接缩点求\(SG\)值,对于题目关键点乱给的情况,也可以以第一个关键点为根,这样子后面关键点朝着第一个关键点的方向靠。

\(code:\)

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 300000 + 5;
int n,Last[MAX_N],Next[MAX_N<<1],End[MAX_N<<1],tot;
inline void addedge(int x,int y){End[++tot]=y,Next[tot]=Last[x],Last[x]=tot;}
int gs[MAX_N],ans[MAX_N],fa[MAX_N],vis[MAX_N],cnt[MAX_N];
void dfs(int x){
	gs[x]=0;
	for(int i=Last[x];i;i=Next[i]){
		int y=End[i];
		if(y!=fa[x]){
			fa[y]=x;
			dfs(y);
			gs[x]^=(gs[y]+1);
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1);
	ans[1]=gs[1];
	vis[1]=1;
	for(int i=2;i<=n;i++){
		ans[i]=ans[i-1];
		cnt[i]=cnt[i-1];
		for(int j=i;!vis[j];j=fa[j]){
			vis[j]=1;
			ans[i]^=(gs[j]+1)^gs[j];
			cnt[i]++;
		}
	}
	for(int i=1;i<=n;i++){
		if(ans[i]^(cnt[i]&1)) printf("1");
		else printf("2");
	}
	return 0;
}


这篇关于CF1610I Mashtali vs AtCoder(博弈论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程