巴什博弈
链接:https://ac.nowcoder.com/acm/problem/207846
来源:牛客网
输入
复制
6,3,5
返回值
复制
-1
备注:
对于100%的数据,1\leq n\leq 1e9,1\leq q,p\leq 1e9对于100%的数据,1≤n≤1e9,1≤q,p≤1e9
(其中30%的数据,p=q)(其中30%的数据,p=q)
听说写题解能促进学习动力,弱鸡路过。
巴什博弈,也就是两个人能拿相同多的数量m时,面对一堆石子n,最后一个拿的胜利。
这里要看石子数量n是否是m+1的倍数,因为在m+1时,先手必败,此时先拿者不可能拿完,后拿着者要么拿光(此时n剩余<m)或者后来者重新使这个数量恢复至m+1的倍数关系。
而不是m+1倍数时,第一个拿的使之变成倍数关系,达成自己胜利条件。
而这里当q!=p时,谁大谁赢,(要先看n是否比他们的q或p小)
class Solution { public: /** * * @param n int整型 * @param p int整型 * @param q int整型 * @return int整型 */ int Gameresults(int n, int p, int q) { // write code here if(n<=p) return 1; else if(n<=q) return -1; if(q==p) { if(n%(q+1)==0) return -1; else return 1; } if(p>=q) return 1; else return -1; } };