博弈专题 sg函数子状态+链涂色

题目链接:https://vjudge.net/contest/299140#problem/J
题目大意:一个圆环N个珠子,每次每个人只能给连续的M个数珠子涂色,最后不能涂的就算输。

每次涂色后相当于把链分成没有涂色的两部分



根据sg定理:当前状态的SG函数等于各个子状态SG函数的异或和
所以枚举所有的子状态就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int sg[1010]={0};
int n, m;
int  get_sg(int len)
{
    if(len<m)//长度<m无法涂色
    {
        return 0;
    }
    if(sg[len]!=-1)
    {
        return sg[len];
    }
    bool vis[1010]={0};
    for(int i=0;i+m<=len;i++)
    {
        vis[get_sg(i)^get_sg(len-m-i)]=true;
    }
    for(int i=0;i<=len;i++)//mex
    {
        if(!vis[i])
        {
            return sg[len]=i;
        }
    }
}

int main()
{
    int T, CUT=0;
    scanf("%d",&T);
    while(T--)
    {
        CUT++;
        scanf("%d %d",&n,&m);
        printf("Case #%d: ",CUT);
        if(m==1)
        {
            if(n&1)
            {
                printf("aekdycoin\n");
            }
            else
            {
                printf("abcdxyzk\n");
            }
            continue;
        }
        memset(sg, -1, sizeof(sg));
        sg[0]=0;
        if(n>=m&&!get_sg(n-m))
        {
            printf("aekdycoin\n");
        }
        else
        {
            printf("abcdxyzk\n");
        }

    }

    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
简历当中有水分算不算造假...
点赞 评论 收藏
分享
05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
仁者伍敌:牛子这些人还会点一个自动回复,boss都不带回复的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务