EOJ Monthly 2019.9 (based on September Selection) A.才艺展示(博弈sg找规律)、D.站军姿(概率)

本文主要是介绍EOJ Monthly 2019.9 (based on September Selection) A.才艺展示(博弈sg找规律)、D.站军姿(概率)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. 才艺展示(sg找规律)

题目

Cuber QQ 和 Little Fang 两人会按照游戏规则轮流写 { 1,2,⋯,N } （ N 是一个正整数）中的一个数。

游戏的规则是这样的，若一个人写下数 i ，则另一个人只能写 i+1 或 2i （ i,i+1,2i 均不超过 N ）。两个人中，谁先写到 N 这个数字，谁就能获胜。

当然 Cuber QQ 为了表现自己的绅士，他让 Little Fang 先写， Little Fang 的开场是单调而固定的，他一定会写数字 1 。

由于表演需要，两个人一共要玩 T 局游戏。每局游戏都会给定提前正整数 N ，当然 Cuber QQ 和 Little Fang 的聪明程度是毋庸置疑的，所以他们都会按照最优的策略进行游戏。

1<=T<=1e5，1<=N<=1e18

思路来源

涛神

题解

先sg打个表

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1005;
int n;
int ok[N];
int dfs(int i)
{if(~ok[i])return ok[i]; if(i==n)return ok[i]=0;//是否必败 bool f=1;//是否必败 if(i+1<=n)f&=dfs(i+1);if(2*i<=n)f&=dfs(2*i);ok[i]=f^1;return ok[i];
}
void out(int x)
{int s[10],cnt;for(;x;x/=2)s[++cnt]=x%2;reverse(s+1,s+cnt+1);for(int i=1;i<=10-cnt;++i)printf("%d",0);for(int i=1;i<=cnt;++i)printf("%d",s[i]);puts(""); 
}
int main()
{for(int i=1;i<=1000;++i){n=i;memset(ok,-1,sizeof ok);if(dfs(1)){printf("%-10d:",n);out(i);}}return 0;
}

看前面看不出来，转化成二进制(i->2*i)发现，

后手必胜当且仅当二进制位只有偶数位能为1

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int T;
ll n,lose;
int main()
{for(int i=0;i<64;i+=2)lose|=(1ll<<i);scanf("%d",&T);while(T--){scanf("%lld",&n);if(n&lose)puts("Little Fang Win");else puts("Cuber QQ Win");}return 0;
}

和涛神讨论了一下证明：

①n%2==1 先手必胜 n=2*i+1 先手可以控制不去2*i这个状态从而获胜

由于2*i这个状态是偶数先手位于1 不管后手怎么取后手选完之后的数都是偶数

先手每次都+1就保持奇数状态从而让对手去2*i 从而先手必胜

②n与4*n走到的人相同，故二者胜负情况相同，若A走到n，分两种情况，

(1)B走到2*n，此时A可走到4*n

(2)B走到n+1，此时A可走到2*n+2，由于剩下无法*2，+1交替知A走到4*n

③4*n与4*n+2胜负情况相同，只需证4n+2只能由4n通过+1+1得，不能通过(2*n+1) *2得即可

显然2*n+1只能通过2*n转移得来，若A走到2*n，B走到2n+1，则A走到4*n+2，A获胜

同理，所以在A走到2*n时，B不会走+1，只会*2到4*n，所以4*n+2与4*n同胜负

④n==2时，后手获胜

①到④可证明，后手获胜的情况，