Alice and Bob用一堆石子玩游戏。初始时这堆石子有n颗，玩家轮流操作，Alice先手。 每一次操作为：当前玩家选一个数X（1<=X<=m，X不超过当前这堆石子的总数量），并从该堆取走X颗石子。如果这堆石子被取光，则当前玩家赢。如果这堆石子还有剩余，则把剩余石子数量写成二进制，如果该二进制数含有奇数个1，则当前玩家立刻输掉游戏。 例如，19写成二进制为10011，含有3个1。因此，当某个玩家取走石子后剩余19颗石子，则立刻输掉比赛。 给定n和m，假定两人都按最优策略操作，求谁有必胜策略。
输入格式： 第1行：1个整数n 第2行：1个整数m
输出格式： 第1行：Alice或者Bob
输入样例1： 3 2
输出样例1： Bob
输入样例2： 387 22
输出样例2： Alice
数据规模与约定： 1 <= n <= 500,000,000, 且含有偶数个1 1 <= m <= 50
注：本题的时间复杂度与实际耗时相当不科学。因此首先提出最优时间复杂度O(n/m)
题解： 看到这个时间复杂度估计人人都会了，毕竟是很直观很暴力的算法。考虑用N，P来表示结点（N：先手必胜，P:先手必败） 特殊情况：0-P结点，表示前一个人已经拿完，即当前先手已经失败 每一个在二进制下奇数个1的数（简称结束数）-N结点，表示前一个人拿完后，还剩下结束数个石头，即之前的人失败，当前先手必胜
从剩余0个石头开始向上递推，记录目前最大的P结点为cur。不难发现，在每一个P结点向上m个数中，每一个都一定是N结点（都可以一步到达当前这个P结点），所以在没有特殊情况下，下一个P结点一定是cur+m+1。
特殊情况即为cur+m+1刚好是一个结束数，必然为N结点，因此再向上依次+1，直到找到一个不是结束数的数为止。
另外，如果m=1，为避免超时，可以用特别处理来解决，依次从n向下找，直到访问到第一个结束数，通过经过的数字个数，来判断胜负。
这里还要特别介绍一个函数： __builtin_popcount(x) x是一个整型变量，返回值为x在二进制下1的个数。不需要头文件，是从yl学的黑科技，不推荐大赛使用。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define SF scanf #define PF printf using namespace std; int n,m,cur; bool flag; inline bool check(int x){ return __builtin_popcount(x)%2; } int main(){ SF("%d%d",&n,&m); cur=0; if(m==1){ while(!check(n)){ n--; flag=!flag; } if(!flag) PF("Alice"); else PF("Bob"); return 0; } while(cur<n){ cur=cur+m+1; while(check(cur)) cur++; } if(cur==n) PF("Bob"); else PF("Alice"); }