本文共 1746 字，大约阅读时间需要 5 分钟。
题意：每次必须拿且只能拿不超过一半的石头，不能拿为败
思路：显然算出每个的sg函数，但是范围1e9显然不能直接打表。所以先打表找规律，发现偶数一直是自己的一半，奇数好像没规律。偶数x的sg函数值是x/2，说明前x/2~x-1的sg函数值涵盖了所有0~x/2集合的值，那么比他大1的奇数x+1少了x/2的sg函数值，那么x+1的sg函数值就是x/2的sg函数值，然后不断递归。
代码：
#include #include #include #include #include #include #include #include #include #include typedef long long ll;const int maxn = 1000 + 10;const int seed = 131;const ll MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;using namespace std;int main(){ int T, Case = 1; scanf("%d", &T); while(T--){ ll ans = 0, n, a; scanf("%lld", &n); while(n--){ scanf("%lld", &a); if(a & 1){ while(a & 1) a >>= 1; ans ^= a / 2; } else ans ^= a / 2; } if(ans) printf("Case %d: Alice\n", Case++); else printf("Case %d: Bob\n", Case++); } return 0;}
打表代码：
#include #include #include #include #include #include #include #include #include #include typedef long long ll;const int maxn = 1000 + 10;const int seed = 131;const ll MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;using namespace std;int sg[maxn], s[maxn];void getSG(){ sg[0] = 0; for(int i = 1; i < maxn; i++){ memset(s, 0, sizeof(s)); for(int j = 1; j <= i / 2; j++){ s[sg[i - j]] = 1; } for(int j = 0; j < maxn; j++){ if(!s[j]){ sg[i] = j; break; } } }}int main(){ getSG(); for(int i = 1; i < maxn; i++) cout << i << " " << sg[i] << endl; int T, Case = 1; scanf("%d", &T); while(T--){ ll ans = 0, n, a; scanf("%lld", &n); while(n--){ scanf("%lld", &a); ans ^= sg[a]; } if(ans) printf("Case %d: Alice\n", Case++); else printf("Case %d: Bob\n", Case++); } return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/9720577.html