【博弈论/思维题】人人尽说江南好
选自HEOI2014
BZOJ 3609: [Heoi2014]人人尽说江南好
- 因为游戏规定，首先无法合并的一方判输， 每人都会使用最优策略， 那么贪心的想， 最优合并方案最后石子排布情况一定为m, m....m, n%m. 初始每堆石子都为一个， 所以这种情况是一定可以实现的
- 所以只需要计算出合并成最终方案的步数， 若为奇数， 先手胜， 偶数， 后手胜。
- sum = (n / m) * (m - 1) + (n % m) - 1; //n/m堆（能正好凑成m个的石子堆数）
- 因为每堆石子初始1个， 所以合并成一堆， 需要m-1次，最后剩下的n%m个， 合并成一堆也只需要(n%m)-1 次
- 特殊判断， 若n能被m整除, 后面的{ (n%m) - 1}没有意义， 如果直接代式子， 还会多减去一， 所以分开计算
1 /************************************************************** 2 Problem: 3609 3 User: Hwjia 4 Language: C++ 5 Result: Accepted 6 Time:0 ms 7 Memory:1288 kb 8 ****************************************************************/ 9 10 #include<cstdio> 11 #include<iostream> 12 using namespace std; 13 int T, n, m; 14 int main() { 15 scanf("%d", &T); 16 while(T--) { 17 scanf("%d%d", &n, &m); 18 int tot = (n / m) * (m - 1); 19 if(n % m != 0) tot += (n % m) - 1; 20 if(tot & 1) printf("0 "); 21 else printf("1 "); 22 } 23 return 0; 24 }
0ms！！
短小精悍的代码qwq
但是它胜在妙啊QuQ！