SHU训练六——博弈(一)
2021/5/2 10:28:43
本文主要是介绍SHU训练六——博弈(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Incredible Chess
题解
Left Right
思路:
nim模板题。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=510; int a[maxn],b[maxn]; int main(){ int T,Case=1; cin>>T; while(T--){ int n;cin>>n; int res=0; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; res^=(y-x-1); } cout<<"Case "<<Case++<<":"; if(res) printf(" Alice\n"); else puts(" Bob"); } return 0; }
Matrix Game
题意:
给定一个n*m的格子,每个格子都有石子,玩家可以每次在任意一行中取任意个石子,问先手是否能赢。
思路:
由于每次玩家都是在任意一行取石子,把每一行的石子加起来就转化成nim游戏了。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=510; int main(){ int T,Case=1; cin>>T; while(T--){ int n,m;cin>>n>>m; ll res=0; for(int i=1;i<=n;i++){ ll tmp=0; for(int j=1;j<=m;j++){ ll x;cin>>x; tmp+=x; } res^=tmp; } cout<<"Case "<<Case++<<":"; if(res) printf(" Alice\n"); else puts(" Bob"); } return 0; }
Misere Nim
题意:
n堆石子,每个人可以取任意个但是不能不取,取走最后一个石子的人输。求输赢状态。
思路:
Anti-Nim游戏。
结论为:
先手必胜当且仅当
所有堆的石子数都为1并且游戏的SG值为0
有些堆的石子数大于1且游戏的SG值不为0
证明
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=510; int main(){ int T,Case=1; cin>>T; while(T--){ ll res=0,cnt=0; int n;cin>>n; for(int i=1;i<=n;i++){ ll x;cin>>x; res^=x; if(x==1) cnt++; } cout<<"Case "<<Case++<<":"; if((cnt==n&&res==0)||(cnt<n&&res)) printf(" Alice\n"); else puts(" Bob"); } return 0; }
Crazy Calendar
题意:
给定一个n*m的格子,每个格子都有石子,每次可以将格子的任意个石子向正下方或正右方移动,直到到达边缘,问输赢情况。
思路:
当先手移动到右下角时,先手必胜。
到右下角距离为偶数的点对答案不会产生影响,到右下角距离为奇数的点才会影响答案,对所有奇数点做一遍nim游戏就好啦。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int T,Case=1; cin>>T; while(T--){ ll res=0,cnt=0; int n,m;cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ ll x;cin>>x; int cnt1=n-i+1+m-j+1; if(cnt1%2){ res^=x; } } } cout<<"Case "<<Case++<<":"; if(!res) printf(" lose\n"); else puts(" win"); } return 0; }
Partitioning Game
题意:
n堆物品,每堆物品有多个组成,Alice和Bob轮流依次对这些物品进行操作,每次都要把其中一堆物品分成不同的个数,最后一个没办法再进行操作的人输掉比赛。
思路:
由于每一堆物品的分割都是相互独立的,所以我们可以用SG函数来处理,先计算一堆的,对于一个由a件物品组成的堆,可以分割的后继方法有(1,a-1),(2,a-2),(3,a-3),……,((a-1)/2,a-(a-2)/2);
由于由同一堆分割好的两堆也是相互独立的,所以再用SG定理,得到:SG(x)=mex{SG(1)^SG(a-1), SG(2)^SG(a-2), SG(3)^SG(a-3), ... ,SG((a-1)/2)^SG(a-(a-1)/2)};
则最后的答案是:SG(a1)SG(a2)SG(a3)...SG(an);
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=10010; int sg[maxn],vis[maxn]; void init(){ memset(sg,0,sizeof sg); for(int i=1;i<=10000;i++){ memset(vis,0,sizeof vis); for(int j=1;j+j<i;j++) vis[sg[j]^sg[i-j]]++; for(int j=0;j<=10000;j++) if(!vis[j]){ sg[i]=j;break; } } } int main(){ init(); int T,Case=1; cin>>T; while(T--){ int n,res=0;cin>>n; for(int i=1;i<=n;i++){ int x;cin>>x; res^=sg[x]; } cout<<"Case "<<Case++<<":"; if(res) printf(" Alice\n"); else puts(" Bob"); } return 0; }
Again Stone Game
题意:
有n堆石子,两个人轮流操作,每次至少选择一堆,拿走至少一个石子,但是不要拿走超过一半的石子。不能操作者输。
思路:
先SG函数打表找规律,得到:
该堆石子数为偶数时,SG值等于他的一半
为奇数时,将他不断/2变为偶数,SG值等于该偶数的SG值
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; int sg[maxn],vis[maxn]; void init(){ memset(sg,0,sizeof sg); for(int i=1;i<maxn;i++){ memset(vis,0,sizeof vis); for(int j=1;j<=i/2;j++) vis[sg[i-j]]=1; for(int j=0;;j++){ if(!vis[j]){ sg[i]=j;break; } } } } int main(){ int T,Case=1; cin>>T; while(T--){ int n;cin>>n; int res=0; for(int i=1;i<=n;i++){ int x;cin>>x; if(x%2) x/=2; res^=(x/2); } cout<<"Case "<<Case++<<":"; if(!res) puts(" Bob"); else puts(" Alice"); } return 0; }
Game of Hyper Knights
题意:
给出一个棋盘,两个人每次按照图中方式移动棋子,不能移动者输。问输赢。
思路:
二维的SG函数,先手必胜的条件是所有棋子的SG值异或和不为0.对于每个棋子,SG值等于后继点的mex值。dfs求解即可。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; int sg[1100][1100]; int nx[]={-2,-3,-2,-1,-1,1}; int ny[]={1,-1,-1,-2,-3,-2}; int dfs(int x,int y){ if(sg[x][y]!=-1) return sg[x][y]; set<int>s; for(int i=0;i<6;i++){ int xx=x+nx[i],yy=y+ny[i]; if(xx>=0&&yy>=0) s.insert(dfs(xx,yy)); } for(int i=0;;i++) if(s.count(i)==0){ sg[x][y]=i; return i; } } int main(){ memset(sg,-1,sizeof sg); int T,Case=1; cin>>T; while(T--){ int n;cin>>n; int res=0; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; res^=dfs(x,y); } cout<<"Case "<<Case++<<":"; if(!res) puts(" Bob"); else puts(" Alice"); } return 0; }
这篇关于SHU训练六——博弈(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现