自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:30:08，当前版本为作者最后更新于2021-03-30 16:12:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道水题体现出我没有任何码力，整天写错各种细节。也许这就是为什么我 CF 也打得不好吧。

首先口胡是非常简单的。我们考虑分类。

$A=B$ 时即普通的 Bash 博弈，直接计算 SG 值异或和即可。SG 值就是 $x \bmod{(A+1)}$。

$A>B$ 时先按照两人都只能最多取 $B$ 计算，如果此时 Petyr 能赢则显然原游戏也能赢，如果此时 Petyr 不能赢，我们考虑能不能有使 SG 值仍为 $0$ 的操作。容易发现若有某一堆石子数 $>B$ 则可以从这一堆取 $B+1$ 颗，SG 值不变，Petyr 能获胜。若都 $\le B$ 则此游戏状态和 nim 没有区别，所以 Varys 必然获胜。

$A<B$ 时考虑 Petyr 的第一步操作。若 Petyr 能获胜，则他可以操作一步后到达 Varys 必败的情况，此与 $A>B$ 时 Petyr 必败的情况是一致的。于是我们枚举每堆使 SG 值变成 $0$ 的操作，如果操作完后还有一堆石子数 $>A$，则必然有 Petyr 落败。只有最初的 SG 值不为 $0$，至多只有一堆的石子数 $>A$，且操作后这一堆的石子数可以 $\le A$ 时 Petyr 能获胜。判断一下就行了。

时间复杂度 $O(n)$。

Code:

#include<cstdio>
int n,t,f,v,a,b,r;
int x[100003];
int main()
{
	scanf(" %d %d %d",&n,&a,&b);
	for(int i=0;i<n;++i)scanf(" %d",&x[i]);
	if(a==b)
	{
		for(int i=0;i<n;++i)r^=x[i]%(a+1);
		puts((r)?"Petyr":"Varys");
		return 0;
	}
	if(a>b)
	{
		for(int i=0;i<n;++i)r^=x[i]%(b+1),(x[i]>b)&&(f=1);
		puts((r|f)?"Petyr":"Varys");
		return 0;
	}
	for(int i=0;i<n;++i)r^=x[i]%(a+1),(x[i]>a)&&(++v);
	for(int i=0;i<n;++i)t=x[i]%(a+1)^r,x[i]=(t>x[i]%(a+1))?(x[i]-x[i]%(a+1)+t-a-1):(x[i]-x[i]%(a+1)+t),(x[i]>a)&&(f=1);
	puts(((r)&&(!f)&&(v<2))?"Petyr":"Varys");
	return 0;
}