题解 P7467 【[CERC2018] Game of Stones】
VinstaG173
·
·
题解
这道水题体现出我没有任何码力，整天写错各种细节。也许这就是为什么我 CF 也打得不好吧。
首先口胡是非常简单的。我们考虑分类。
$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:
```cpp
#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;
}
```