链接：https://ac.nowcoder.com/acm/contest/121952

A – 小红的博弈

算法：

    博弈论，贪心。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    if (n <= 2)
        cout << "red" << endl;
    else
        cout << "purple" << endl;
}

B – 小红选点

算法：

    暴力枚举。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<pii> a(n);
    for (auto &[x, y] : a)
        cin >> x >> y;

    double ans = -1;
    int xx, yy, xxx, yyy;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            auto [x1, y1] = a[i];
            auto [x2, y2] = a[j];
            double cur = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);

            if (cur > ans)
            {
                ans = cur;

                xx = x1, yy = y1, xxx = x2, yyy = y2;
            }
        }
    }

    cout << xx << ' ' << yy << ' ' << xxx << ' ' << yyy << endl;
}

C – 小红的矩形

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    if (x1 == x2)
        cout << x1 + 1 << ' ' << y1 << ' ' << x2 + 1 << ' ' << y2 << endl;
    else if (y1 == y2)
        cout << x1 << ' ' << y1 + 1 << ' ' << x2 << ' ' << y2 + 1 << endl;
    else
    {
        if (x2 < x1)
        {
            swap(x1, x2);
            swap(y1, y2);
        }

        if (x1 < x2 && y1 < y2)
            cout << x2 << ' ' << y1 << ' ' << x1 << ' ' << y2 << endl;
        else
            cout << x1 << ' ' << y2 << ' ' << x2 << ' ' << y1 << endl;
    }
}

D – 小红拿石子1.0

算法：

    贪心。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    ranges::sort(a, greater<>());

    ll ans = 0;
    for (int i = 0; i < n; ++i)
        ans += max(0, a[i] - i);

    cout << ans << endl;
}

E – 小红玩树

算法：

    最短路，博弈论。

思路：

    如果存在一个叶子节点 \(u\) 使得 \(distance(a, u) * 2 <= distance(b, u)\) 小红就胜利。

关键代码：

const int inf = 1e9;

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

    if (n == 2)
    {
        cout << "red" << endl;
        return;
    }

    vector<int> st(n + 1, 0);
    vector<int> dist1(n + 1, inf);
    auto dfs1 = [&](auto &&self, int u, int f, bool flag) -> void
    {
        for (auto v : g[u])
        {
            if (v == f)
                continue;

            bool ok = flag;
            if (v == b)
                ok |= 1;

            dist1[v] = dist1[u] + 1;
            st[v] = ok;

            self(self, v, u, flag | ok);
        }
    };

    vector<int> dist2(n + 1, inf);
    auto dfs2 = [&](auto &&self, int u, int f) -> void
    {
        for (auto v : g[u])
        {
            if (v == f)
                continue;

            dist2[v] = dist2[u] + 1;
            self(self, v, u);
        }
    };

    dist1[a] = 0;
    dfs1(dfs1, a, 0, 0);

    dist2[b] = 0;
    dfs2(dfs2, b, 0);

    for (int u = 1; u <= n; ++u)
    {
        if (deg[u] != 1)
            continue;

        if (dist1[u] * 2 <= dist2[u])
        {
            cout << "red" << endl;
            return;
        }
    }

    cout << "purple" << endl;
}

F – 小红拿石子2.0

算法：

    博弈论。

思路：

    考虑小红什么时候可以赢。

    小红想赢需要最后一回合只剩一个数字。

    假设 \(a[i]\) 为最后剩余的数字，那么先前最多执行 \(a[i] – 1\) 轮游戏，那么大于等于 \(a[i]\) 的所有元素（除去最后剩余的 \(a[i]\)）都必须在先前取走，其个数记为 \(cnt\)，只要 \(a[i] – 1 >= cnt\) 小红就可以胜利。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    map<int, int> m;
    for (int i = 0; i < n; ++i)
        ++m[a[i]];

    ranges::sort(a);

    int tot = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        int op = a[i] - 1;

        int L = n - (ranges::lower_bound(a, a[i]) - a.begin()) - 1;

        if (op >= L)
        {
            cout << "red" << endl;
            return;
        }
    }

    cout << "purple" << endl;
}