ECNU OJ 3354 领外卖（博弈-SG函数）

你的名字 2022-05-29 12:41 176阅读 0赞

#  #

# 3354. 领外卖 #

[DESCRIPTION][] [STATISTICS][] [1 DISCUSSION][]

**Time limit per test:** 2.0 seconds

**Memory limit:** 256 megabytes

林吉吉(LJJ)和金大哥(JDG)为了谁去领外卖吵得不可开交，为了确定谁去领外卖，李蓓蓓学姐设计了一个简单的游戏：给定一堆 n 个石子，每个人轮流从石子堆取走若干个石子，要求每次取走的石子数为正完全平方数（即此数为某个正整数的平方），拿走最后一颗石子的人获胜，林吉吉先手。

请问若双方都以最佳方式进行选择，谁将去领外卖？

### Input ###

第一行为数据组数 T

每组数据的第一行为 n 即石子的数目

数据约束：  
对于 50%的数据保证 n≤30  
对于所有数据保证 T≤10001≤n≤105

### Output ###

每组数据，若林吉吉赢了就输出 `JDG will get takeaways!` 否则输出 `LJJ will get takeaways!`

### Examples ###

input

3
    1
    2
    3

output

JDG will get takeaways!
    LJJ will get takeaways!
    JDG will get takeaways!

拿[HDU1847][]稍微改了改能拿的石子的限制数目情况就AC了。

HDU1847[传送门][HDU1847]：https://blog.csdn.net/mikasa3/article/details/51366553

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 100010
    int sg[MAXN],f[MAXN],temp[MAXN];
    void solve()
    {
        int i,j,cnt=MAXN;
        f[0]=1;
        for(i=0; i<MAXN; i++) //f表示所有能取到的石子数的值
            f[i]=i*i;
        memset(sg,-1,sizeof(sg));
        sg[0]=0;
        for(i=1; i<=MAXN; i++) //求sg值,i表示石子数
        {
            memset(temp,-1,sizeof(temp));
            for(j=0; j<=cnt&&f[j]<=i; ++j)
                temp[sg[i-f[j]]]=0;//i-f[j]表示从i张石子中取走f[j]个后的状态
            for(j=0;; ++j)
                if(temp[j]==-1)
                {
                    sg[i]=j;
                    break;
                }
        }
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
    //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        solve();
        while(t--)
        {
            int n;
            cin>>n;
            if(sg[n]) cout<<"JDG will get takeaways!"<<endl;//必败点
            else cout<<"LJJ will get takeaways!"<<endl;
        }
        return 0 ;
    }

[DESCRIPTION]: https://acm.ecnu.edu.cn/problem/3354/
[STATISTICS]: https://acm.ecnu.edu.cn/problem/3354/statistics/
[1 DISCUSSION]: https://acm.ecnu.edu.cn/problem/3354/discussion/
[HDU1847]: https://blog.csdn.net/mikasa3/article/details/51366553