A 小橙分硬币

知识点：构造、分类讨论、奇偶性

总价值为 $a+2b$，若总价值为奇数，一定无法平分。若有 $1$ 元硬币，则只要总价值为偶数，总能通过若干枚 $1$ 元硬币调整出一半的价值。

特殊地，当 $a=0$ 时，只有 $2$ 元硬币，此时必须让两人拿到相同数量的 $2$ 元硬币，因此 $b$ 必须为偶数。

时间复杂度 $\mathcal{O}(1)$​

void solve() {
    int a, b;
    cin >> a >> b;
    cout << ((!a && (b & 1) || ((a + 2 * b) & 1)) ? "NO" : "YES") << endl;
}

B 小橙玩游戏

知识点：博弈论、状态归纳、必胜必败态

设当前轮到小橙且 $n \le 2$，她可以一步将 $n$ 变为非正数，因此小橙必胜。

当 $n \ge 3$ 时，可以归纳证明轮到小橙都是必败态：小橙无论减 $1$ 还是减 $2$，小橘都能选择合适操作，要么直接结束游戏，要么把局面交回到另一个小橙必败态。因此只有 $n \le 2$ 时先手小橙获胜。

时间复杂度 $\mathcal{O}(1)$​

void solve() {
    int n;
    cin >> n;
    cout << (n <= 2 ? "xiaocheng" : "xiaoju") << endl;
}

C 小橙买水果

知识点：贪心、环形结构、单调段

买到某个水果后，只能沿着价格非递增的方向继续免费获得后面的水果。因此对于每个位置 $i$，如果 $a_i > a_{i-1}$，它不可能由前一个水果免费得到，必须付费购买。所以答案是所有“严格上升点”的价格之和。若环上不存在严格上升点，则所有价格相等，任意买一个水果即可获得全部水果，答案为最小价格。

时间复杂度 $\mathcal{O}(n)$​

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &v : a) cin >> v;
    a.push_back(a.front());
    bool f = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (a[i] > a[i - 1]) ans += a[i], f = 1;
    if (!f) ans = *min_element(a.begin(), a.end());
    cout << ans << endl;
}

D 小橙访问传送门

知识点：最短路建模、传送等价类、贪心

同色传送门之间可以零代价互相到达，因此所有红色传送门可以看成一个点，所有蓝色传送门也可以看成一个点。只需考虑从原点进入红色集合、进入蓝色集合，以及红蓝集合之间切换的最小步行代价。

记：

• $c_R$ 为原点到最近红色传送门的距离；
• $c_B$ 为原点到最近蓝色传送门的距离；
• $d$ 为最近一对异色传送门之间的距离。

完成访问并回到原点的方式只有本质上的三类：原点分别连接两个颜色集合一次，或从某个颜色集合出发跨到另一个颜色集合后再原路意义上返回。因此答案为
$$\min(c_R+c_B+d,\ 2(c_R+d),\ 2(c_B+d)).$$
时间复杂度 $\mathcal{O}((n+m)\log(n+m))$

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pii> p(n + m);
    for (int i = 0; i < n; ++i) cin >> p[i][0], p[i][1] = 0;
    for (int i = 0; i < m; ++i) cin >> p[n + i][0], p[n + i][1] = 1;
    sort(p.begin(), p.end());
    int d = inf, c1 = inf, c2 = inf;
    for (int i = 0; i < n + m; ++i) {
        if (p[i][1]) c1 = min(c1, abs(p[i][0]));
        if (!p[i][1]) c2 = min(c2, abs(p[i][0]));
        if (i && (p[i][1] ^ p[i - 1][1])) d = min(d, abs(p[i][0] - p[i - 1][0]));
    }
    cout << min({c1 + c2 + d, 2 * (c1 + d), 2 * (c2 + d)}) << endl;
}

E 小橙分配边权

知识点：图论、最短路性质、构造

若存在源点 $s$，则必须有 $a_s=0$。对任意边 $(u,v)$，由于最短路距离分别为 $a_u,a_v$，边权至少需要满足 $w(u,v)\ge |a_u-a_v|$。因此若直接令每条边权为 $|a_u-a_v|$，任意路径长度都不会小于终点的 $a$ 值。

接下来只需要保证每个点都能从某个 $a_s=0$ 的点出发，沿着 $a$ 值不下降的路径到达。这样路径长度会发生望远镜求和，恰好为 $a_i$。

若不存在这样的零点或存在点不可达，则无解；否则输出每条边的 $|a_u-a_v|$ 即可。

时间复杂度 $\mathcal{O}(n+m)$​

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int s = 0;
    for (int i = 1; i <= n; ++i)
        if (!a[i]) {
            s = i;
            break;
        }
    vector<vector<int>> g(n + 1);
    vector<pii> e(m);
    for (int i = 0; i < m; ++i) {
        cin >> e[i][0] >> e[i][1];
        g[e[i][0]].push_back(e[i][1]), g[e[i][1]].push_back(e[i][0]);
    }
    vector<bool> vis(n + 1);
    auto dfs = [&](auto &&self, int u) -> void {
        vis[u] = 1;
        for (auto v : g[u])
            if (!vis[v] && a[v] >= a[u]) self(self, v);
    };
    if (s) dfs(dfs, s);
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            cout << -1 << endl;
            return;
        }
    for (auto [u, v] : e) {
        cout << abs(a[u] - a[v]) << endl;
    }
}

F 小橙协调网格

知识点：二维差分、切比雪夫距离、枚举中心

若最终中心为 $(x,y)$，格子 $(i,j)$ 保持不变当且仅当
$$a_{i,j}=\max(|x-i|,|y-j|).$$
也就是说，若 $a_{i,j}=k$，那么合法中心 $(x,y)$ 必须落在以 $(i,j)$ 为中心、切比雪夫半径为 $k$ 的正方形边界上。

于是对每个格子，把半径 $k$ 的正方形整体加一，再把半径 $k-1$ 的内部正方形减一，就能用二维差分统计每个中心能匹配多少个格子。设最大匹配数为 $mx$，则最少修改次数为 $nm-mx$。

时间复杂度 $\mathcal{O}(nm)$

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> d(n + 2, vector<int>(m + 2));

    auto add = [&](int r1, int c1, int r2, int c2, int val) {
        r1 = max(r1, 1LL), c1 = max(c1, 1LL), r2 = min(r2, n), c2 = min(c2, m);
        if (r1 > r2 || c1 > c2) return;
        d[r1][c1] += val;
        d[r1][c2 + 1] -= val;
        d[r2 + 1][c1] -= val;
        d[r2 + 1][c2 + 1] += val;
    };

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int k;
            cin >> k;
            add(i - k, j - k, i + k, j + k, 1);
            if (k > 0) add(i - (k - 1), j - (k - 1), i + (k - 1), j + (k - 1), -1);
        }
    }

    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
            mx = max(mx, d[i][j]);
        }
    }

    cout << n * m - mx << endl;
}

备注

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii array<int, 2>
#define endl "\n"

constexpr int inf = 2e18 + 9;

void solve() { }

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}