LightOJ-1296 Again Stone Game(SG打表找规律)
题意：n堆石子，对于每堆的操作是：一堆数量为k个的石子，每堆至少取1个至多取k/2个(特殊：1个石子取不了)。数据范围[1, 1e9].
思路：数据范围太大，不能预处理SG值，所以打出前100个石子的SG进行找规律，发现偶数时SG值为其本身/2，奇数时，发现其SG值为其不断除以2直至变成一个偶数，其SG值等于该偶数的SG值。
Code：
#include <string.h>
#include <cstdio>
using namespace std;
int SG[1005], mex[1005];
void GETSG() //打表找规律
{
int i, j;
SG[0] = 0;
for(i = 1; i <= 100; ++i)
{
memset(mex, 0, sizeof mex);
for(j = 1; j <= i/2; ++j) mex[SG[i-j]] = 1;
for(j = 0; ; ++j) if(!mex[j]) break;
SG[i] = j;
printf("%2d: %d\n", i, SG[i]);
}
}
int main()
{
int t, n, ans, x;
// GETSG();
scanf("%d", &t);
for(int _ = 1; _ <= t; ++_)
{
scanf("%d", &n); ans = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &x);
// ans ^= SG[x];
while(x&1) x /= 2;
ans ^= (x/2);
}
printf("Case %d: ", _);
if(ans) puts("Alice");
else puts("Bob");
}
return 0;
}继续加油~