算法1
(暴力枚举) $O(n^2)$
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
int dfs(long long a,long long b,int count)//用count记录先后手,count从1开始,那么先手就是偶数,后手之为奇数
{
if((a/b>=2 || a==b)&&(count%2!=0)) return 1;//碰到满足条件的,又是先手,那么先手一定赢,返回1
if((a/b>=2 || a==b)&&(count%2==0)) return 0;//碰到满足条件,但是这回是后手先开始,此时的后手就
//必赢(因为题目说双方都选择最优策略)返回0
dfs(b,a-b,count+1);
}
int main()
{
long long a,b;
while(cin>>a>>b)
{
if(a==0&&b==0) return 0;
if(b>a) swap(a,b);
if(dfs(a,b,1)) printf("win\n");
else printf("lose\n");
}
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla