题目地址：HDU 2897
本来这题可以用NP状态转换，但是数据太大，所以可以通过打表sg函数值，来找出规律。感觉sg函数打表就是利用的NP状态转换的那两条规则。
通过打表可以发现，从1开始，连续p个0，然后接着连续q个正整数，然后再连续p个0，接着连续q个正整数，就这样循环下去。所以规律就很明显了。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long int sg[10000], _hash[10000]; void getsg(int n, int p, int q) { int i, j; memset(sg,0,sizeof(sg)); for(i=p+1;i<=n;i++) { memset(_hash,0,sizeof(_hash)); for(j=p;j<=q;j++) { _hash[sg[i-j]]=1; } for(j=0;j<=n;j++) { if(!_hash[j]) { sg[i]=j; break; } } } for(i=0;i<=n;i++) { printf("%d ",sg[i]); } } int main() { int n, p, q, x; while(scanf("%d%d%d",&n,&p,&q)!=EOF) { //getsg(n,p,q); x=n%(p+q); if(x>=1&&x<=p) puts("LOST"); else puts("WIN"); } return 0; }