取石子游戏:思路+易错点+代码

开局关键点:0 0 ----> 多测

一.思路
先看到题目可能会有点懵,不要慌,看说明/提示
*没有思路且没有看 说明/提示 的同学们可以先回去做了

总体来说,就是分为两种情况:

1.max(a,b)/min(a,b)>=2//直接从dfs函数返回先手胜
2.max(a,b)/min(a,b)<2//进行"唯一的一种取法",并进入下一轮dfs

总体框架:

void dfs(int a1,int b1){
	if(max(a1,b1)/min(a1,b1)>=2){
		ans=1;//标记先手胜
		return;
	}else{
		dfs(max(a1,b1)-min(a1,b1),min(a1,b1));
	}
}

二.易错点
首先,"先手必胜"中的"先手"指的是什么?如果不明确其定义,可以这样写:

void dfs(int a1,int b1){
	if(max(a1,b1)/min(a1,b1)>=2){
		cout<<"win";
		return;
	}else{
		dfs(max(a1,b1)-min(a1,b1),min(a1,b1));
	}
}

(然后连样例都过不了)
拿样例举个例子:

显然,这一局B胜,但如果直接输出"win"就是a胜,所以需要加一个变量来记录一下当前轮是A行动,还是B行动,也就是:

void dfs(int a1,int b1,int x){
	if(max(a1,b1)/min(a1,b1)>=2){
		if(x==1)ans=1;
		return;
	}else{
		dfs(max(a1,b1)-min(a1,b1),min(a1,b1),(x+1)%2);
	}
}

(这里使用int x来记录,1是先手,0是后手;如果觉得这个较为抽象,也可以用char x之类的)

其次,有一种特殊情况是a==b,那么这个时候,我们可以直接判定,先手(也就是A)必胜,也就是:

if(a==b){
    cout<<"win"<<endl;
    continue;
}

三.代码

#include<bits/stdc++.h>
using namespace std;
int a,b;
bool ans=0;
void dfs(int a1,int b1,int x){
	if(max(a1,b1)/min(a1,b1)>=2){
		if(x==1)ans=1;
		return;
	}else{
		dfs(max(a1,b1)-min(a1,b1),min(a1,b1),(x+1)%2);
	}
}
int main(){
	while(1){   //多测
		cin>>a>>b;
		ans=0;   //初始化
		if(a==0&&b==0){
			return 0;
		}
		if(a==b){    //特判
			cout<<"win"<<endl;
			continue;
		}
		dfs(a,b,1);
		if(ans)cout<<"win"<<endl;
		else cout<<"lose"<<endl;
	}
}