https://anoth3r.top/solution/nkwk118/

牛客周赛 Round 118 题解

A 小红的博弈

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

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

B 小红选点

只有 ，暴力即可。

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 小红的矩形

如果横/纵坐标相等就往纵/横方向延伸出一格，否则取 和 即可。

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

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

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 小红玩树

记 为从小紫起点 到 的最短边数。

对小红从 出发的一条路径 （小红第 步到达 ）：

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

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

打表看出来的：

• 记 。
• 若 ，则小紫获胜；否则小红获胜。

一个比较好理解的思路：

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

严格证明如下：

• 如果 ，小紫必胜：

  • 任一初始高度不超过 的列，若没有被小红在之前某次彻底删除，则在第 次小紫的动作后会被减到 。
  • 小红在这 轮内至多可以删除 列。
  • 但最开始就有 列高度为 。小红在 次行动中最多能把其中 列删掉，仍至少留下一列初始为 的列没有被小红删除；该列在第 次小紫的操作后会被减到 。再考虑任意其它初始高度 的列，要么被小红删掉，要么也在第 次小紫操作之前被减到 。于是在第 次小紫操作结束时，所有列都已为空。
  • 故小紫必胜。

• 如果 ，小红必胜：

  • 小红的第一步按两种情况选一堆删除：

    • 若 ：小红删除一堆高度为 的堆。
    • 若 ：
      • 若存在高度 的列，小红删除任意这样一堆；
      • 否则所有堆高度都是 （此时 ），小红随便删除一堆。

    然后小紫把剩余所有堆高度都减 。

  • 记“红删 + 紫减 ”后的新最大高度为 及新最大高度的堆数为 ，然后我们证明：

    • ：
      • 无论小红删哪堆，小紫把所有剩余堆减 后，原来高度为 的堆高度变为 。 因此新的最大高度 。（若小红没有删掉所有原来高度为 的堆，则 ；若小红删掉了所有原来高度为 的堆，则 。总之 。）
    • ：
      • 若原来 ：小红删一个高度为 的堆，剩下高度为 的堆数变为 。减 后它们高度变为 ，于是新的最大高度 且 。所以 成立。

  • 基底：若 ，且 ，小红第一步删掉唯一的 （若存在），小紫回合无子可取，红胜成验证。

  • 归纳：由上面的构造，若命题在所有最大高度 时成立，那么在高度 且 时，小红能做一步把局面变为高度 且仍满足条件，按归纳假设，小红必胜。

• 证毕

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";
}