一个标准的NIM游戏 加上一条规则:每堆石子对于每个数目的石子只能被取一次
可以SG打表
dp[i][j]表示现在有i个石子 j是可以取的石子数的状压 第i位为1就表示i个石子没被取过
#include <cstdio> #include <cstring> bool vis[100]; int mex() { for(int i = 0; ; i++) if(!vis[i]) return i; } int sg[11][1 << 10]; int main() { memset(sg, -1, sizeof(sg)); for(int i = 0; i < (1 << 10); i++) sg[0][i] = 0; for(int i = 1; i <= 10; i++) { sg[i][0] = 0; for(int j = 1; j < (1 << 10); j++) { memset(vis, false, sizeof(vis)); for(int k = 0; k < i; k++) if((j >> k) & 1) vis[sg[i - k - 1][j ^ (1 << k)]] = true; sg[i][j] = mex(); } } for(int i = 0; i <= 10; i++) printf("i = %d: sg = %d\n", i, sg[i][(1 << i) - 1]); return 0; }
打表找到规律数X的SG值就是该数最多能被多少个整数划分 即找到最大的Y 使得sum(1~Y)<=X Y即为数X的SG值
#include<iostream> #include<cstdio> using namespace std; int n,ans; int main() { int i,j,p; cin>>n; for(i=1;i<=n;i++) { scanf("%d",&p); for(j=1;j*(j+1)/2<=p;j++); ans^=j-1; } ans?puts("NO"):puts("YES"); }
CodeForces 768E SG函数 整数划分 Game of Stones
原文：https://www.cnblogs.com/Aragaki/p/11663319.html