hdu 4746 Stone 2013长春网络赛 博弈
搞ACM搞到今天这个地步,连个这么简单的博弈都推不出来了……………………
题目大意,两个人数数,谁先数到>=n谁就输…… 先手开始报数,x属于【1,k】另一个人报【x+1,x+k】……
分析胜败状态就好了,n-1肯定是必胜状态,那么前面只要是能一步转化到必胜状态的都是必败状态,n-2,n-k-1; n-k-2又是必胜状态, 也就是说连续的k+1个状态里面只有一个是必胜状态…… 找到规律之后%(K+1)就好,注意特判……
博弈真是忘得一干二净了……
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,k; int main() {///非常简单的博弈题,就是没做出来啊; 分析必败必胜状态就好了,n肯定是必败状态,n-1是必胜;n-2,n-3,n-k-1都是必败,因为下一步 ///可以转化到n-1必胜状态…… int i,j; long long l,r,m,c; while(scanf("%d%d",&n,&k)) { if(n==0&&k==0)break; if(n<=k) { if(n==1)cout<<"Jiang"<<endl; else cout<<"Tang"<<endl; }else { if(n%(k+1)==1)cout<<"Jiang"<<endl; else cout<<"Tang"<<endl; } } }