A 小月的增减

知识点：循环、分支

依次读入每个数，遇到奇数就让 $x$ 减少 $1$，遇到偶数就让 $x$ 增加 $1$，最后输出 $x$。注意 $0$ 是偶数，且 $x$ 可以为负数。

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

void solve() {
    int n, x;
    cin >> n >> x;
    for (int i = 0, y; i < n; ++i) cin >> y, x -= (y & 1) - !(y & 1);
    cout << x << endl;
}

B 小月的集市

知识点：整数除法、取模、模拟

先把 $a$ 枚金币平分，每人得到 $\lfloor a/b\rfloor$ 枚金币。剩余的 $a\bmod b$ 枚金币换成碎银后再平分，并向下取整，所以每人需要支付的金币数、碎银数分别为

\left\lfloor\frac{a}{b}\right\rfloor, \qquad \left\lfloor\frac{(a\bmod b)\cdot 10^k}{b}\right\rfloor.

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

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    int p = 1;
    while (k--) p *= 10;
    cout << a / b << " " << (a % b) * p / b << endl;
}

C 小月的长廊

知识点：区间计数、排序、二分查找

覆盖位置 $x$ 的区间数，等于已经开始的区间数减去已经结束的区间数，即

d(x)=\#\{j:l_j\le x\}-\#\{j:r_j<x\}.

分别将所有左端点、右端点排序，便能用二分查找求出这两个数量。注意区间包含端点，因此左端点统计不大于 $x$ 的数量，右端点统计严格小于 $x$ 的数量。最后枚举原来的每个区间，检查 $|d(l_i)-d(r_i)|\ge p$ 即可。

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

void solve() {
    int n, p;
    cin >> n >> p;
    vector<pii> a;
    vector<int> l(n), r(n);
    for (auto &&[u, v] : views::zip(l, r)) cin >> u >> v, a.push_back({u, v});

    sort(l.begin(), l.end());
    sort(r.begin(), r.end());

    auto get = [&](int x) -> int {
        return upper_bound(l.begin(), l.end(), x) - l.begin() -
               (lower_bound(r.begin(), r.end(), x) - r.begin());
    };

    int ans = 0;
    for (auto [x, y] : a) ans += abs(get(x) - get(y)) >= p;
    cout << ans << endl;
}

D 小月的回声

知识点：前缀和、值域枚举、哈希表

设 $p_i$ 为前 $i$ 个数的和。固定右端点 $r$，再枚举左端点的值 $x=a_l$，原条件就变为

a_l a_r=p_{r-1}-p_l \quad\Longleftrightarrow\quad p_l=p_{r-1}-x a_r.

由于 $x$ 只有 $1\sim30$ 这几种取值，可以按 $a_l$ 分组，用哈希表记录各个 $p_l$ 的出现次数。从左到右枚举 $r$，先将新满足长度限制的左端点 $l=r-2$ 加入，然后枚举 $x$，查询对应前缀和的数量并累加。这样表中恰好包含所有 $l\le r-2$ 的左端点，每个合法区间都会被统计一次。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), p(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = p[i - 1] + a[i];
    vector<unordered_map<int, int>> cnt(31);
    int ans = 0;
    for (int r = 1; r <= n; ++r) {
        int l = r - 2;
        if (l >= 1) cnt[a[l]][p[l]]++;
        if (r >= 3)
            for (int x = 1; x <= 30; ++x) {
                auto it = cnt[x].find(p[r - 1] - 1LL * x * a[r]);
                if (it != cnt[x].end()) ans += it->second;
            }
    }
    cout << ans << endl;
}

E 小月的时差

知识点：最短路、二分答案、图的连通性

先分别求出信号塔 $a,b$ 到每个点的最短距离 $da_u,db_u$，则点 $u$ 的时差就是

w_u=|da_u-db_u|

答案不超过 $x$，当且仅当只保留 $w_u\le x$ 的点后，$s,t$ 仍然连通。因为此时可以找到一条所有点权都不超过 $x$ 的简单路径；反过来，满足限制的路径也只会经过这些点。

随着 $x$ 增大，可经过的点只会增加，因此可以二分最小可行的 $x$，每次用广度优先搜索检查连通性。起点也必须满足 $w_s\le x$；当 $s=t$ 时同样适用。

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

constexpr int inf = 2e18 + 9;

void solve() {
    int n, m, a, b, s, t;
    cin >> n >> m >> a >> b >> s >> t;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto dijkstra = [&](int s, vector<int> &dis) {
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push({0, s});
        dis[s] = 0;
        while (q.size()) {
            auto [d, u] = q.top();
            q.pop();
            if (d != dis[u]) continue;
            for (auto v : g[u]) {
                if (dis[v] > d + 1) {
                    dis[v] = d + 1;
                    q.push({dis[v], v});
                }
            }
        }
    };

    vector<int> da(n + 1, inf), db(n + 1, inf), w(n + 1);
    dijkstra(a, da), dijkstra(b, db);
    for (int i = 1; i <= n; ++i) w[i] = abs(da[i] - db[i]);
    auto check = [&](int x) {
        if (w[s] > x) return false;
        vector<bool> vis(n + 1);
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        while (q.size()) {
            auto u = q.front();
            q.pop();
            if (u == t) return true;
            for (auto v : g[u]) {
                if (vis[v] || w[v] > x) continue;
                vis[v] = 1;
                q.push(v);
            }
        }
        return false;
    };
    int l = 0, r = *max_element(w.begin(), w.end()), ans = r;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans << endl;
}

F 小月的订单

知识点：动态规划、前后缀合并、滚动数组

两批订单之间一定有一个不选的位置。枚举这个空位 $i$，第一批只从 $[1,i-1]$ 中选，第二批只从 $[i+1,n]$ 中选，便能同时保证先后顺序和跨批次不相邻。

设 $f_{k,i}$ 表示从前 $i$ 个位置中选出恰好 $k$ 个互不相邻的订单、按第一批费用支付的最小总费用。考虑是否选择位置 $i$，有

f_{k,i}=\min\bigl(f_{k,i-1},\ f_{k-1,i-2}+a_i\bigr).

同理，设 $g_{k,i}$ 表示从后缀 $[i,n]$ 中选出恰好 $k$ 个互不相邻的订单、按第二批费用支付的最小总费用，则

g_{k,i}=\min\bigl(g_{k,i+1},\ g_{k-1,i+2}+b_i\bigr).

选 $0$ 个订单的费用为 $0$，其余无法选出的状态为正无穷；越界的前后缀视为空区间。两批各选 $k$ 个的最小费用就是

c_k=\min_{1\le i\le n}\bigl(f_{k,i-1}+g_{k,i+1}\bigr).

任何合法方案都能在两批之间找到这样的空位，而合并得到的方案也一定合法，因此取 $c_k\le s$ 的最大 $k$ 即可。

总共要选 $2k$ 个互不相邻的位置，至少需要 $4k-1$ 个位置，所以只需枚举 $k\le\lfloor(n+1)/4\rfloor$。每次转移只依赖上一层，用滚动数组将空间压到 $\mathcal{O}(n)$。费用均为正数，从更大方案中各删去一份订单就能得到更小方案，因此一旦 $c_k>s$ 就可以停止枚举。

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

constexpr int inf = 2e18 + 9;

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

    vector<int> f(n + 2), g(n + 2);
    int ans = 0;
    for (int k = 1; k <= (n + 1) / 4; ++k) {
        vector<int> nf(n + 2, inf), ng(n + 2, inf);
        for (int i = 1; i <= n; ++i) nf[i] = min(nf[i - 1], f[max(0LL, i - 2)] + a[i]);
        for (int i = n; i >= 1; --i) ng[i] = min(ng[i + 1], g[min(n + 1, i + 2)] + b[i]);

        int res = inf;
        for (int i = 1; i <= n; ++i) res = min(res, nf[i - 1] + ng[i + 1]);
        if (res > s) break;
        ans = k;
        f.swap(nf), g.swap(ng);
    }
    cout << ans << 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;
}

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