CF73中的Div2的E题，Interesting Game，题目是这样的，可以对一堆石头分成a1,a2,a3…,an这n堆，第i堆有ai颗石头，并满足ai = ai-1 + 1，两个人轮流操作，直到一方不能做这样的操作的话，他就输了。
要想使用SG那个异或定理的话，就要用SG函数的定义，根据SG函数的定义求出SG函数的值。
然后这题就是对没种情况进行枚举，求出每个状态的SG值，并记录下如果赢的话，最少要弄几堆，代码如下：
#include <iostream> #include <string> using namespace std; const int MAX = 1e5 + 5; int dp[MAX], sum[MAX], tmp[MAX]; int m_min[MAX]; void ready() { memset(dp, 0, sizeof(dp)); memset(tmp, 0, sizeof(tmp)); memset(m_min, 0, sizeof(m_min)); sum[0] = sum[1] = sum[2] = 0; int ans = 0; for(int i = 3; i < MAX; i++) { for(int j = 2; ; j++) { if((j + 1) * j / 2 > i) break; int left = i - (j + 1) * j / 2; if(left % j) continue; int x = left / j; //dp[1 + x]^...^dp[j + x] = sum[j + x] ^ sum[x] tmp[sum[j + x] ^ sum[x]] = i; if(m_min[i] == 0 && (sum[j + x] ^ sum[x]) == 0) m_min[i] = j; } while(tmp[dp[i]] == i) dp[i]++; sum[i] = sum[i - 1] ^ dp[i]; } } int main() { ready(); int n; scanf("%d", &n); if(dp[n] == 0) printf("-1"); else printf("%d", m_min[n]); }
然后这题的话，就可以用同样的方法做出来了。
ZOJ1083这题是道经典问题，题意是对一条线段进行染色，每次只能然一段长度为2单位的线，谁不能染的话，就输掉，也是要求出SG函数。就是利用到可以把一个游戏拆成几个子游戏的这个特点。
#include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <stdlib.h> using namespace std; const int MAX = 100; int dp[MAX], tmp[MAX]; void ready() { memset(dp, 0, sizeof(dp)); memset(tmp, 0, sizeof(tmp)); for(int i = 2; i < MAX; i++) { for(int j = 0; j < i - 1; j++) tmp[dp[j] ^ dp[i - j - 2]] = i; while(tmp[dp[i]] == i) dp[i]++; } } int main() { ready(); int n; while(scanf("%d", &n) != EOF) { int ans = 0; for(int i = 0; i < n; i++) { int t; scanf("%d", &t); ans ^= dp[t]; } puts(ans == 0 ? "No" : "Yes"); } }转载于:https://www.cnblogs.com/litstrong/archive/2011/06/19/2084846.html
