A 小红的博弈

如果小红可以一次拿完，就是小红赢，否则小紫赢。

void solve() {
    int n;
    cin >> n;
    if (n <= 2) cout << "red" << "\n";
    else cout << "purple" << "\n";
}

B 小红选点

$n$ 只有 $1000$ ，暴力即可。

void solve() {
    int n;
    cin >> n;
    vector<PII> a(n);
    PII x, y;
    for (int i = 0; i < n; ++i) cin >> a[i].fi >> a[i].se;
    int ans = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            PII u = a[i], v = a[j];
            int dis = (u.fi - v.fi) * (u.fi - v.fi) + (u.se - v.se) * (u.se - v.se);
            if (dis > ans) {
                ans = dis;
                x = u, y = v;
            }
        }
    }
    cout << x.fi << " " << x.se << " " << y.fi << " " << y.se << "\n";
}

C 小红的矩形

如果横/纵坐标相等就往纵/横方向延伸出一格，否则取 $(x_1,y_2)$ 和 $(x_2,y_1)$ 即可。

void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x1 == x2) {
        cout << x1 + 1 << " " << y1 << " " << x2 + 1 << " " << y2 << "\n";
    } else if (y1 == y2) {
        cout << x1 << " " << y1 + 1 << " " << x2 << " " << y2 + 1 << "\n";
    } else {
        cout << x1 << " " << y2 << " " << x2 << " " << y1 << "\n";
    }
}

D 小红拿石子1.0

对于小红来说，所有剩下堆的“已被小紫拿掉的量”都是相同的（都是 $d$ ），所以当前拿走石子最多的堆即是最优的。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(all(a), [&](int a, int b) {
        return a > b;
    });
    int d = 0;
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= d) continue;
        ans += a[i] - d;
        d++;
    }
    cout << ans << "\n";
}

E 小红玩树

记 $db[u]$ 为从小紫起点 $b$ 到 $u$ 的最短边数。

对小红从 $a$ 出发的一条路径 $a=p_0,p_1,p_2,\cdots,p_t = leaf$（小红第 $i$ 步到达 $p_i$ ）：

• 小红一旦走到叶子 ，立即获胜，所以只要小红能在到达前不被捕获就能赢。
• 在小红到达中间点 $p_i$（ $i < t$ ）之后，小紫会进行其第 $i$ 次回合并可走 $2$ 步，因此若 $db[p_i]\leq 2*i$ ，小紫可以在该回合到达 $p_i$ 并抓住小红（小紫胜）。 因此如果要继续向下走到更远的节点，必须保证对到达的中间点 $p_i$ 有 $db[p_i]>2i$ 。
• 对叶子 $p_t$ ，小红在第 $t$ 步到达并立即获胜；小紫在那之前只进行了 $t-1$ 次回合，小紫能否在小红到达前占据该叶子由 $db[p_i]\leq 2(t-1)$ 判断。 因此只要 $db[p_t]>2(t-1)$ ，小红到达该叶子时小紫尚未占据，她就获胜。

void solve() {
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    vector<int> db(n + 1, inf);
    queue<int> q;

    db[b] = 0;
    q.push(b);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (db[v] == inf) {
                db[v] = db[u] + 1;
                q.push(v);
            }
        }
    }

    if (g[a].size() <= 1) {
        cout << "red" << "\n";
        return;
    }

    vector<bool> vis(n);
    queue<PII> qu;
    vis[a] = 1;
    qu.push({a, 0});
    bool f = false;

    while (!qu.empty() && !f) {
        auto [u, d] = qu.front();
        qu.pop();
        for (int v : g[u]) {
            if (vis[v]) continue;
            if (g[v].size() == 1) {
                if (db[v] > 2 * d) {
                    f = true;
                    break;
                } else {
                    vis[v] = 1;
                    continue;
                }
            }
            if (db[v] > 2 * (d + 1)) {
                vis[v] = 1;
                qu.push({v, d + 1});
            } else {
                vis[v] = 1;
            }
        }
    }

    if (f) cout << "red" << "\n";
    else cout << "purple" << "\n";
}

F 小红拿石子2.0

打表看出来的：

• 记 $mx=max(a),cnt = \text{数组中等于}mx\text{的堆数}$ 。
• 若 $cnt\geq mx+1$ ，则小紫获胜；否则小红获胜。

一个比较好理解的思路：

• 小紫会在小红最后一步时有一个以上的 $1$ 的情况下会赢。
• 所以小红要尽量减少最后剩下来 $1$ 的数量。
• 所以小红的操作一定是尽可能把 $mx$ 的数量减少到 $1$ 个。
• 所以只用看小红能不能在 $mx$ 变为 $1$ 之前把它拿得只剩 $1$ 个即可。

严格证明如下：

• 如果 $cnt>mx$ ，小紫必胜：
  • 任一初始高度不超过 $mx$ 的列，若没有被小红在之前某次彻底删除，则在第 $mx$ 次小紫的动作后会被减到 $0$ 。
  • 小红在这 $mx$ 轮内至多可以删除 $mx$ 列。
  • 但最开始就有 $cnt>mx$ 列高度为 $mx$ 。小红在 $mx$ 次行动中最多能把其中 $mx$ 列删掉，仍至少留下一列初始为 $mx$ 的列没有被小红删除；该列在第 $mx$ 次小紫的操作后会被减到 $0$ 。再考虑任意其它初始高度 $<mx$ 的列，要么被小红删掉，要么也在第 $mx$ 次小紫操作之前被减到 $0$ 。于是在第 $mx$ 次小紫操作结束时，所有列都已为空。
  • 故小紫必胜。
• 如果 $cnt\leq mx$ ，小红必胜：
  • 小红的第一步按两种情况选一堆删除：
    • 若 $cnt = mx$ ：小红删除一堆高度为 $mx$ 的堆。
    • 若 $cnt<mx$ ：
      • 若存在高度 $<mx$ 的列，小红删除任意这样一堆；
      • 否则所有堆高度都是 $mx$（此时 $cnt=n<mx$ ），小红随便删除一堆。
    • 然后小紫把剩余所有堆高度都减 $1$ 。
  • 记“红删 + 紫减 $1$ ”后的新最大高度为 $mx’$ 及新最大高度的堆数为 $cnt’$ ，然后我们证明：
    • $mx’\leq mx-1$ ：
      • 无论小红删哪堆，小紫把所有剩余堆减 $1$ 后，原来高度为 $k$ 的堆高度变为 $k-1$ 。 因此新的最大高度 $mx’\leq mx-1$ 。（若小红没有删掉所有原来高度为 $mx$ 的堆，则 $mx’=mx-1$；若小红删掉了所有原来高度为 $mx$ 的堆，则 $mx'<mx-1$ 。总之 $mx’\leq mx-1$ 。）
    • $cnt’\leq mx’$ ：
      • 若原来 $cnt=mx$ ：小红删一个高度为 $mx$ 的堆，剩下高度为 $mx$ 的堆数变为 $mx-1$ 。减 $1$ 后它们高度变为 $mx-1$ ，于是新的最大高度 $mx’=mx-1$ 且 $cnt’=mx-1=mx’$ 。所以 $cnt’\leq mx’$ 成立。
  • 基底：若 $mx=1$ ，且 $c\leq 1$ ，小红第一步删掉唯一的 $1$ （若存在），小紫回合无子可取，红胜成验证。
  • 归纳：由上面的构造，若命题在所有最大高度 $<mx$ 时成立，那么在高度 $mx$ 且 $c\leq m$ 时，小红能做一步把局面变为高度 $mx'<mx$ 且仍满足条件，按归纳假设，小红必胜。
• 证毕

void solve() {
    int n, mx = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i], mx = max(mx, a[i]);

    int cnt = 0;
    for (int i = 0; i < n; ++i) cnt += a[i] == mx;

    if (cnt >= mx + 1) cout << "purple" << "\n";
    else cout << "red" << "\n";
}