即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

bzoj 1874 取石子游戏 博弈论

编程语言 Loi_a 21℃ 0评论

博弈论基础题,第一次写博弈论题目。


每堆石子的游戏是相互独立的,一个局面是由这n堆石子n个子游戏构成。


对于每堆石子,用sg[i]表示有i个石子的sg值,sg值由它的后继状态推过来:sg[i]=mex(sg[i-b[j]]);


最后的答案即为 : sg[ a[i] ] 的异或和;若ans=0则先手必败,否则先手必胜。


做第二问时,则按照输出的顺序枚举,第i堆移走k个的答案为ans^sg[a[i]]^sg[a[i]-k];若得到的ans=0则表示操作后我可以造成一个先手必败的局面,此时为要求的答案。

我WA半天才发现一个天大的错误 :^的优先级要小于==,也就是说


if( a^x==0 ) 和 if( (a^x)==0 )是不一样的。论学扎实语言的重要性!

#include
#include
#include
#include
using namespace std;
int a[20],b[20];
bool use[1005];
int sg[1005];
int main()
{
    int n,mx=1000;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int m;scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]);
    sort(b+1,b+m+1);
    for(int i=1;i<=mx;i++)
    {
        memset(use,0,sizeof(use));
        for(int j=1;j<=m;j++)
            if(b[j]<=i) use[sg[i-b[j]]]=1;
            else break;
        for(int k=0;k<=10;k++)
            if(!use[k]) {sg[i]=k;break;}
    }
    int Xor=0;
    for(int i=1;i<=n;i++)
        Xor^=sg[a[i]];
    if(Xor==0)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i]>=b[j]&&(Xor^sg[a[i]]^sg[a[i]-b[j]])==0)
            {
                printf("%d %d",i,b[j]);
                return 0;
            }
}

转载请注明:CodingBlog » bzoj 1874 取石子游戏 博弈论

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情