A 小月的 DX 分

知识点：计数、加权求和

直接计算即可，$3a+2b+c$。

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

void solve() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    cout << a * 3 + b * 2 + c << endl;
}

B 小月的配对

知识点：枚举、取模

直接枚举每个位置 $i$，读取对应的排列值 $p_i$，判断
$$(i+p_i)\bmod k=0$$
是否成立。满足条件就把答案加一。

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

void solve() {
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1, x; i <= n; ++i) cin >> x, ans += (i + x) % k == 0;
    cout << ans << endl;
}

C 小月的程序

知识点：前缀性质、后缀性质、分类讨论

选择参数 $k$ 后，前 $k$ 个数会变成
$$a_k,a_{k-1},\dots,a_1.$$
要让这部分非递减，原数组前缀必须满足
$$a_1\ge a_2\ge\dots\ge a_k.$$
反转不会影响后缀，所以还需要
$$a_{k+1}\le a_{k+2}\le\dots\le a_n.$$
最后只剩反转部分与后缀的连接处，要求 $k<n$ 时满足 $a_1\le a_{k+1}$；当 $k=n$ 时没有连接处。

预处理 $p_i$ 表示前缀 $a_1,\dots,a_i$ 是否非递增，$s_i$ 表示后缀 $a_i,\dots,a_n$ 是否非递减。枚举每个 $k$，按上述条件判断即可。

时间复杂度 $\mathcal{O}(n)$，空间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<bool> p(n + 1), s(n + 1);
    p[1] = s[n] = true;
    for (int i = 2; i <= n; ++i) p[i] = p[i - 1] && a[i - 1] >= a[i];
    for (int i = n - 1; i >= 1; --i) s[i] = s[i + 1] && a[i] <= a[i + 1];
    int ans = 0;
    for (int k = 1; k <= n; ++k) {
        bool ok = p[k];
        if (k < n) ok = ok && s[k + 1] && a[1] <= a[k + 1];
        ans += ok;
    }
    cout << ans << endl;
}

D 小月的删数

知识点：交替和、前缀和、按值分组

固定删除数值 $c$ 后，原数组会被这些被删除位置分成若干个连续保留段。每删除一个元素，后面保留元素在新数组中的奇偶下标都会翻转，因此这些保留段在交替和中的符号会交替变化。

采用下标从 $0$ 开始，定义交替前缀和
$$P_i=\sum_{j=0}^{i-1}(-1)^j a_j.$$
任意连续段 $[l,r)$ 的原始交替和可以由 $P_r-P_l$ 得到。扫描数值 $c$ 的所有出现位置时，维护上一段的起点，并在每次遇到被删位置后翻转当前段的符号，就能在线性时间内得到删除 $c$ 后的读数。所有不同的数值分别处理，所有位置总共只会被扫描一次。

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

constexpr int inf = 2e18 + 9;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), p(n + 1);
    unordered_map<int, vector<int>> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p[i + 1] = p[i] + (i % 2 ? -a[i] : a[i]);
        mp[a[i]].push_back(i);
    }
    int ans = inf;
    for (auto [u, v] : mp) {
        int st = 0, op = 0, s = 0;
        for (auto x : v) {
            int t = p[x] - p[st];
            s += op ? -t : t;
            op ^= 1;
            st = x + 1;
        }
        ans = min(ans, llabs(s + (op ? p[st] - p[n] : p[n] - p[st])));
    }
    cout << ans << endl;
}

E 小月的折返颜色

知识点：并查集缩点、树上计数、按颜色分组

先把颜色相同的相邻节点用并查集合并。合并后，每个连通块内部颜色完全相同；把每个连通块缩成一个点，得到的仍然是一棵树，且相邻缩点颜色一定不同。

原树上一条路径恰好换色两次，当且仅当它在缩点树上经过
$$U\longrightarrow V\longrightarrow W$$
这两条边，并且两个端点连通块的颜色相同。固定中间点 $V$，枚举它的邻居连通块：若当前邻居连通块的颜色为 $q$、大小为 $s$，此前已经处理过的邻居中颜色为 $q$ 的节点总数为 $cnt_q$，则它与此前这些节点形成的合法点对数为
$$cnt_q\cdot s.$$
处理完当前邻居后再令 $cnt_q\mathrel{+}=s$。这样每个无序点对只会在它们路径的中间连通块处统计一次。

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

void solve() {
    int n;
    cin >> n;
    vector<int> c(n + 1);
    for (int i = 1; i <= n; ++i) cin >> c[i];

    DSU d(n);
    vector<pii> e(n - 1);
    for (auto &[u, v] : e) {
        cin >> u >> v;
        if (c[u] == c[v]) d.merge(u, v);
    }

    vector<vector<int>> g(n + 1);
    for (auto [u, v] : e) {
        u = d.find(u), v = d.find(v);
        if (u == v) continue;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int ans = 0;
    vector<int> cnt(n + 1);
    for (int u = 1; u <= n; ++u) {
        for (int v : g[u]) {
            ans += cnt[c[v]] * d.size(v);
            cnt[c[v]] += d.size(v);
        }
        for (auto v : g[u]) cnt[c[v]] = 0;
    }
    cout << ans << endl;
}

F 小月的峰

知识点：二分答案、区间 DP、单调性

二分步幅上限 $d$。固定 $d$ 后，要求每一段相邻读数的差值都不超过 $d$，并且峰值位置 $p$ 满足

$$x_1<x_2<\dotsx_{p+1}>\dots>x_n.$$

从左向右维护上升前缀在第 $i$ 个位置可以取到的区间 $f_i=[L_i,R_i]$。若前一位置可取区间为 $[L_{i-1},R_{i-1}]$，那么严格上升且步幅不超过 $d$ 要求
$$x_i\in [L_{i-1}+1,R_{i-1}+d]\cap[l_i,r_i].$$
因此
$$L_i=\max(l_i,L_{i-1}+1),\qquad R_i=\min(r_i,R_{i-1}+d).$$

同理，从右向左计算下降后缀的可行区间。枚举峰值位置 $i$，只要上升前缀区间和下降后缀区间有交集，就存在一个合法峰值。

可行性关于 $d$ 单调：若某个 $d$ 可行，更大的步幅上限也一定可行。因此二分最小的 $d$。由于所有端点位于 $[-10^9,10^9]$，取 $d=2\times10^9$ 已经覆盖任意一对端点的距离；若此时仍不可行，则答案为 $-1$。

时间复杂度 $\mathcal{O}(n\log V)$。

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

    auto check = [&](int d) {
        vector<pii> f(n + 1, {1, 0});
        f[1] = a[1];
        for (int i = 2; i < n; ++i) {
            f[i] = {max(a[i][0], f[i - 1][0] + 1), min(a[i][1], f[i - 1][1] + d)};
            if (f[i][0] > f[i][1]) break;
        }

        int l = a[n][0], r = a[n][1];
        for (int i = n - 1; i >= 2; --i) {
            l = max(a[i][0], l + 1);
            r = min(a[i][1], r + d);
            if (l > r) break;
            if (max(l, f[i][0]) <= min(r, f[i][1])) return true;
        }
        return false;
    };

    int l = 1, r = 2E9, ans = r;
    if (!check(r)) return cout << -1 << endl, void();
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (check(m))
            ans = m, r = m - 1;
        else
            l = m + 1;
    }
    cout << l << endl;
}

约定

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

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

void solve() {
    
}

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

使用到的算法模板见 $\tt{Github}$ 仓库 林月的XCPC模板库