菜单

澳门皇家赌场BZOJ 1874: [BeiJing2010 温特坎普]取石子游戏(SG函数),bzojbeijing二〇一〇

2019年8月22日 - 皇家赌场系统

Sample Output

YES
1 1
Hint
样例中国共产党有四堆石子,石子个数分别为7、6、9、3,每人每趟能够从别的一群石子中抽出1个或许2个石子,小H有
必胜战术,事实上假设从第一群石子中取一个石子就能够。

Sample Input

4
7
6
9
3
2
1
2

Description

小H和小Z正在玩三个取石子游戏。
取石子游戏的准绳是那般的,每一个人每一次能够从一群石子中抽出若干个石子,
每一遍取石子的个数有限定,什么人无法取石辰时就能输掉游戏。
小H先进行操作,他想问你他是或不是有必胜计谋,倘诺有 ,第一步怎么样取石子。

Input

输入文件的第一行事石子的堆数N 
接下去N行,每行一个数Ai,表示每堆石子的个数
接下来一行为每一回取石子个数的门类数M 
接下去M行,每行一个数Bi,表示每趟可以取的砾石个数,
输入保险那M个数依据递增顺序排列。 N≤10
Ai≤一千 对于任何数目,M≤10,Bi≤10

Output

出口文件首先行事“YES”或许“NO”,表示小H是不是有必胜战术。 
若结果为“YES”,则第二行包涵八个数,第二个数表示从哪堆石子取,第一个数表示取多少个石子,
若有各样答案,取第一个数最小的答案,
若仍有各个答案,取第三个数最小的答案。

BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏(SG函数),bzojbeijing二零零六

Time Limit: 5 Sec  Memory
Limit: 162 MB
澳门皇家赌场,Submit: 871  Solved: 365
[Submit][Status][Discuss]

HINT

Source

Day2

  那题不算是很难,数据范围极小,直接暴力求SG函数。
改变难点已经付出了
看清的时候枚举每一批石子,看看拿走多少个仍旧满意条件(推断的时候不要暴力枚举,直接用求出来的ans答案,结合异或的性质)
注意二个特地坑的地点!! ^的运算级比==低!!  

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10,INF=1e9+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int S[1005],SG[1005],N,M;
int a[MAXN],b[101];
main()
{
    #ifdef WIN32 
    freopen("a.in","r",stdin);
    freopen("b.out","w",stdout);
    #else
    #endif
    N=read();
    for(int i=1;i<=N;i++) a[i]=read();
    M=read();
    for(int j=1;j<=M;j++) b[j]=read();
    sort(b+1,b+M+1);
    int limit=1001;
    for(int i=1;i<=limit;i++)
    {
        memset(S,0,sizeof(S));
        for(int j=1;j<=M&&b[j]<=i;j++)
            S[ SG[i-b[j]] ] = 1;
        for(int j=0;;j++) 
            if(S[j]==0) 
                {SG[i]=j;break;}
    }
    int ans=0;
    for(int i=1;i<=N;i++)
        ans=ans^(SG[a[i]]);
    if(ans==0) {printf("NO\n");return 0;}
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M&&b[j]<=a[i];j++)
        {
            if( (ans ^ SG[a[i]-b[j]] ^ SG[a[i]]) == 0) //好坑啊。。 
            {
                printf("YES\n%d",i);
                printf(" %d",b[j]);
                return 0;
            }
        }
    }
    return 0;
}

 

1874: [BeiJing2009
WinterCamp]取石子游戏(SG函数),bzojbeijing贰零零玖 Time Limit:5 Sec Memory
Limit:162 MB Submit:871 Solved:365 [Submit][Status][Discuss]
Description 小H和…

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图