HDU 2897 邂逅明下(SG博弈论) - c++编程基础

题目地址：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; }