hdu1536(sg函数)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1536

题意：首先输入K 表示一个集合的大小之后输入集合表示对于这对石子只能去这个集合中的元素的个数

之后输入一个m 表示接下来对于这个集合要进行m次询问

之后m行每行输入一个n 表示有n个堆每堆有n1个石子问这一行所表示的状态是赢还是输如果赢输入W否则L

思路：sg函数

一开始直接打表tle了，因该是多组输入的原因吧

然后我们再仔细考虑一下这个m，m<=100，一般来说，给的数据不可能每组的max(a[i]) （1<=i<=m）都达到1e4；

所以我们可以不必每次打表都打到1e4，我们可以通过dfs针对具体数据打表；这样就不会tle啦；

代码：

 #include <iostream>

 #include <string.h>

 #include <algorithm>

 #define MAXN 200010

 using namespace std;

 int f[MAXN], sg[MAXN], n;

 int dfs_sg(int x){//sg函数

     if(sg[x]!=-){//之前已经计算过

         return sg[x];

     }

     int vis[];

     memset(vis, , sizeof(vis));

     for(int i=; i<n; i++){//找到当前节点能到达的点

         if(f[i]<=x){

             dfs_sg(x-f[i]);

             vis[sg[x-f[i]]]=;

         }

     }

     for(int i=; ; i++){//求mex函数

         if(!vis[i]){

             sg[x]=i;

             return sg[x];

         }

     }

 }

 int main(void){

     std::ios::sync_with_stdio(false), cin.tie(), cout.tie();

     while(cin >> n){

         if(n==){

             break;

         }

         memset(sg, -, sizeof(sg));

         for(int i=; i<n; i++){

             cin >> f[i];

         }

         sort(f, f+n);

         int k, t, x;

         cin >> k;

         while(k--){

             cin >> t;

             int ans=;

             for(int i=; i<t; i++){

                 cin >> x;

                 ans^=dfs_sg(x);

             }

             if(ans==){

                 cout << "L";

             }else{

                 cout << "W";

             }

         }

         cout << endl;

     }

     return ;

 }

巴特西

hdu1536(sg函数)

最新文章

热门文章