$HDU1846 Brave Game$ 博弈论

佚名 6年前 (2019-05-10) 随笔 377人围观抢沙发百度已收录

正解:博弈论

解题报告:

传送门!

巴什博奕板子题鸭$QwQ$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

就有个结论,是说当$(m+1)\mid n$时先手必败,否则必胜

这个瞎证明一下就能出来

就考虑当$(m+1)\mid 1$时,若先手取了$d$个,后手就取$m+1-d$个,这样就能成功拿到最后一个了

知道这一点的话那如果$(m+1)\nmid 1$的时候就先手取几个使得$(m+1)\mid 1$,这样就先手必胜了

$over$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}

int main()
{
    int T=read();
    while(T--){ri n=read(),m=read();if(n%(m+1))printf("first\n");else printf("second\n");}
    return 0;
}