取石！

mk14_61 · 2026-07-24 08:15:52 · 题解

水题。

思路

显然考虑 A,B 的大小关系，A = B 时为 Bash 博弈。

考虑 A > B，若存在 x_i > B，则先手可以选择将 x_i 取走 B+1 使得局面跑 Bash 的胜负情况不变，先手必胜，否则为 NIM。

现在考虑 A < B，显然只有 A 的第一次操作是重要的，操作完第一次后就转为 A > B，于是判断是否存在有且仅有一堆 x_i > A 且 x_i - A \le A 即可，注意取完后转化为 NIM，若取值范围内无法使得 NIM SG 值为 0 则先手仍必败。若不存在 x_i > A 就是 NIM。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, a, b, x[N], res;
bool o;
int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i ++)
        cin >> x[i];
    if (a == b) {
        for (int i = 1; i <= n; i ++)
            res ^= x[i] % (a + 1);
    }
    else if (a > b) {
        bool o = 0;
        for (int i = 1; i <= n; i ++)
            res ^= x[i], o |= (x[i] > b);
        if (o)
            res = 1;
    }
    else {
        int o = 0, num = 2e9;
        for (int i = 1; i <= n; i ++) {
            if (x[i] - a > a || (x[i] > a && o)) {
                o = -1;
                break;
            }
            else if (x[i] > a)
                o = 1, num = x[i];
            res ^= x[i];
        }
        if (o == -1)
            res = 0;
        else if (o == 1) {
            res ^= num;
            if (num - a <= res && res <= a)
                res = 1;
            else
                res = 0;
        }
    }
    cout << (res ? "Petyr" : "Varys");
    return 0;
}