首页 > 其他 > 详细

[SHOI2008]小约翰的游戏

时间:2019-04-23 16:18:45      阅读:101      评论:0      收藏:0      [点我收藏+]

题目

不会,抄论文

这是一个非常牛逼的东西,叫做\(anti\)博弈,就是进行最后一次操作的人输

我们考虑一下这道题

显然如果石子个数都是\(1\),那么有奇数堆石子先手必败,有偶数堆石子先手必胜

如果只有一堆石子大于\(1\),如果当前是奇数堆石子,那么我们可以把这堆石子取到只剩下一个,如果是偶数堆石子,我们直接把大于\(1\)的这一堆都拿走,这样我们就能让对方面对必败局面

考虑刚才的局面的\(SG\)函数值,显然不为\(0\)

而我们发现随着游戏的进行石子的减少,刚才的局面一定会出现

所以只要\(SG\)函数不为\(0\)且不是最开始的那种全是\(1\)的情况就能判定先手必胜了

因此我们得到了针对\(anti-SG\)\(SJ\)定理

对于一个\(anti-SG\)游戏先手必胜的条件为满足下两个条件之一

  1. \(SG\)函数大于\(0\),且有至少一个单个游戏的\(SG\)函数大于\(1\)

  2. \(SG\)函数等于\(0\),且没有任何一个单个游戏的\(SG\)函数大于\(1\)

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int T,a,n;
int main() {
    T=read();
    while(T--) {
        n=read();int tot=0,s=0;
        for(re int i=1;i<=n;i++) 
            a=read(),tot+=(a==1),s^=a;
        if(tot==n) puts(s?"Brother":"John");
            else puts(s?"John":"Brother");
    }
    return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int T,a,n;
int main() {
    T=read();
    while(T--) {
        n=read();int tot=0,s=0;
        for(re int i=1;i<=n;i++) 
            a=read(),tot+=(a==1),s^=a;
        if(tot==n) puts(s?"Brother":"John");
            else puts(s?"John":"Brother");
    }
    return 0;
}

[SHOI2008]小约翰的游戏

原文:https://www.cnblogs.com/asuldb/p/10756902.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!