取石子游戏-题解 题目：普及难度 DFS算法(类似模拟) 题解目录 * 题目分析 * 辨析-题中"最优策略" * 输赢判断 * 代码实现 题目分析 a,b两堆石子,两个人(先后手)去取，每次只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍 最后能把a或b中石子取完的人获胜(a=0||b=0) 要求输出先手能否获胜 辨析-题中"最优策略" 题中说两个人都采取最优策略 那么此处的最优策略是什么呢？ 由前面的题目分析可得，最后能把a或b中石子取完的人获胜 因此这两个人若都采用最优策略的话，肯定是希望在自己的回合时能够一次性取完石子或者是取尽可能多的石子 又因为每次只能取较少的那堆石子数目的整数倍 所以取的一次"最优策略"取的上限是a%b (a>b) 先后手输赢判断 判断输赢的话题目中是给了提示的 设石子数目为(a,b),且a>=b,如果[a/b]>=2则先手必胜，否则先手只有唯一的一种取法 所以就有了输赢的条件 1.[A/B]>=2 2.A=0或B=0 (由1可推) 3.A=B (由1可推) 对于判断先后手可以在dfs模拟时设虚参step 起始时step=1 (先手) 当满足上述所说的输赢条件时 判断step为奇数还是偶数 如果为奇数则是正手胜利，否则相反 代码实现 首发题解，如有不对，尽情指正awa

#include <bits/stdc++.h> using namespace std; int a,b; bool flag; void dfs(int a,int b,int step){ if(b>a) swap(a,b);//保证a始终大于b double ans=a*1.0/b; if(ans>=2||(a0||b0)||ab){ if(step%21){ flag=1; }return ; } dfs(a%b,b,step+=1); //因为“最优策略”所以每一次要尽可能取完 a%b } int main(){ cin>>a>>b; while(a!=0&&b!=0){ dfs(a,b,1); if(flag) {cout<<"win"<<endl;} else {cout<<"lose"<<endl;} }

开局关键点:0 0 ----> 多测 一.思路 先看到题目可能会有点懵,不要慌,看说明/提示 *没有思路且没有看 说明/提示 的同学们可以先回去做了 总体来说,就是分为两种情况: 总体框架: 二.易错点 首先,"先手必胜"中的"先手"指的是什么?如果不明确其定义,可以这样写: (然后连样例都过不了) 拿样例举个例子: 显然,这一局B胜,但如果直接输出"win"就是a胜,所以需要加一个变量来记录一下当前轮是A行动,还是B行动,也就是: (这里使用int x来记录,1是先手,0是后手;如果觉得这个较为抽象,也可以用char x之类的) 其次,有一种特殊情况是a==b,那么这个时候,我们可以直接判定,先手(也就是A)必胜,也就是: 三.代码