1661 黑板上的游戏
Alice和Bob在黑板上玩一个游戏,黑板上写了n个正整数a1, a2, …, an,游戏的规则是这样的:
1 . Alice占有先手主动权。
2 . 每个人可以选取一个大于1的数字擦去,并写上一个更小的数字,数字必须是整数,然后由对方进行下一次操作。
3 . 如果擦去的数字是 x (x > 1) ,则写上的数字不能比 x/k 小,但是要比 x 小。这里的除法为有理数除法。
4 . 不可以擦去任何一个数字 1 ,如果当前无法找到一个数字进行操作,则当前方输。
假设Alice和Bob都会选择最优的策略,请问Alice是否存在必胜的方案?
Input
第一行两个空格隔开的正整数n和k,其中n表示数字的个数,k表示游戏的参数。
第二行n个空格隔开的正整数,其中第i个表示ai。
1 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^18, 1 ≤ ai ≤ 10^18。
Output
如果存在必胜方案,则输出“Alice i y”,其中i和y表示先手的一种能必胜的操作:将第i个数修改为y。
如果没有,则输出“Bob”表示后手必胜。(输出不含引号)
Input示例
4 2
2 3 3 3
Output示例
Alice 2 2
解题思路:
官方题解(很详细):
固定
如果
如果
可能的
这里补一个简要证明,基于
其中
考虑
由于后继局面可以写成一个区间的形式,所以下面的分析用
当
假设
由于
当
后继是
由上述可以知道
如果
如果
然后找一下具体的式子即可,有了具体的式子就方便找逆映射了。
需要注意很多的细节问题。。。
/** 2016 - 08 - 29 下午 Author: ITAK Motto: 今日的我要超越昨日的我,明日的我要胜过今日的我, 以创作出更好的代码为目标,不断地超越自己。 **/ #include#include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef unsigned long long ULL; const LL INF = 1e18+5; const int MAXN = 1e6+5; const LL MOD = 1e9+7; const double eps = 1e-7; const double PI = acos(-1); using namespace std; LL Scan_LL()///输入外挂 { LL res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } int Scan_Int()///输入外挂 { int res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } void Out(LL a)///输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } LL a[MAXN], sg[MAXN]; int main() { int n; LL k; while(~scanf("%d%lld",&n,&k)) { LL ans = 0, tmp, ret, x; int j = -1; memset(a, 0, sizeof(a)); for(int i=1; i<=n; i++) { x = Scan_LL(); a[i] = x; if(x == 1) continue; tmp = x; LL tp1 = x/k; LL tp2 = x%k; while(tmp) { if(tp2 == 0) { tp1--; tp2 = k; sg[i] = (tp1*(k-1)+tp2-1); ///cout<<"a["<