很明显是nim游戏,考虑到数据量,我们无法老老实实的求解sg值。
于是我选择打表找规律。
老老实实地打到sg[100]
我们就发现了规律。
sg[i] i为偶数时sg[i]=i/2
i为奇数时,如果sg[i-1]为偶数(此时i-1为偶数)那么sg[i]=sg[i-1]/2
如果sg[i-1]为奇数时,sg[i]=sg[i/2] (向下取整)
ok初始条件为sg[1]==0(边界)那么我们就可以递归求解了。
我们观察上述规律发现每次至少/2。而事实上很可能更快,所以复杂度应该小于O(nlogn)
##代码如下:
#include<iostream> #include<algorithm> using namespace std; int rsg(int x) { if (x == 1)return 0; if (x & 1) { if ((x >> 1) & 1) return rsg(x >> 1); else return x >> 2; }else return x >> 1; } int main() { int T;cin >> T; for (int tcase = 1;tcase <= T;++tcase) { int n;cin >> n; int ans = 0; for (int i = 1;i <= n;++i) { int tmp;cin >> tmp; tmp = rsg(tmp); ans ^= tmp; }cout << "Case " << tcase << ": "; ans > 0 ? cout << "Alice\n" : cout << "Bob\n"; } }