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进行第一次操作),每次操作为:
- 将树上任意一条边删除(无边可删的玩家算输)
- 将不能到达关键点的边删除
当然,小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(博弈论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享