https://www.luogu.org/problem/show?pid=1290
首先，能一眼看出来必胜状态为(kb,b)，其中k为正整数 当状态为(a,b)，其中b<a<2b的时候，显然只有一种决策，即(b,a-b) 当状态(a,b)中，a>2b的时候，一次可以减掉k*b，这时候有很多种情况，是不是每种都要考虑呢？ 不是的，假如给定数据(100000001,2) 这时候如果每个人都考虑a-2的情况的话，一个很大的数字就会在两个人之间来回转手 看两个人这样“踢皮球”是没有什么意思的，于是就有如下的方法： 对于(a,b)，a>2b，有两种决策： 一种是把a减到b<a<2b的范围内，这样就是对手下一步只有一种决策(b,a-b) 一种是减到a<b的范围内，这样就是我们选了对手的那个决策(b,a-b) 于是情况就少很多了，直接dfs就可以了这个是题解，然后我就认为这个是水题嘛； 然后一直WA 这个是AC的
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int x,y,m; bool dfs(int x,int y,bool p){ if(x<y)swap(x,y); if(x%y==0)return true; if(x<y+y)return !dfs(x-y,y,!p); if( dfs( x%y+y , y ,!p) == false ) return true; if( dfs( y , x%y ,!p) == false ) return true; return false; } int main() { scanf("%d",&m); while(m--){ scanf("%d%d",&x,&y); if(dfs(x,y,1))printf("Stan wins\n");else printf("Ollie wins\n"); }}这个是WA的
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int x,y,m; bool dfs(int x,int y,bool p){ if(x<y)swap(x,y); if(x%y==0)return p; if(x<y+y)return dfs(x-y,y,!p); if( dfs( x%y+y , y ,!p)) return true; if( dfs( y , x%y ,!p) ) return true; return false; } int main() { scanf("%d",&m); while(m--){ scanf("%d%d",&x,&y); if(dfs(x,y,1))printf("Stan wins\n");else printf("Ollie wins\n"); }}我的AC程序，就是不断用递归下一层来更新这一层； WA程序是用递归最底层来更新这一层； 这是有区别的啊
