A 小月的数组

知识点：模拟、数组

你说得对，但是这就是 std::views，有 filter，有 transform，还能 take 一个无限长的 iota。有惰性求值，甚至末尾都不用写。只要用管道符接起来，就能从一个容器直接流进另一个容器。有组合，甚至中间不落地、不分配，一圈循环都不多跑。转换的时候甚至可以只遍历一次，还有 move 语义。然后，元素类型提上来之后，还能获得编译期内联，缩短手写 for 的行数，缩短运行时间。然后还有 constexpr，constexpr 一用，整条 pipeline 在编译期就折叠成一条循环，然后还有管道符，管道符一接就啊啊啊啊啊啊。

读入然后输出就行。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &&[u, v] : views::zip(a, b)) cin >> u >>v;
    for (auto v : a) cout << v << " ";
    cout << endl;
    for (auto v : b) cout << v << " ";
    cout << endl;
}

B 小月的屏幕

知识点：模拟、边界判断

当处于边界（ $i=1,i=n,j=1,j=m$ ）的时候判断即可，用或连接就可以避免重复计数。

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

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            if (i == 1 || i == n || j == 1 || j == m)
                ans += c == '#';
        }

    cout << ans << endl;
}

C 小月的同余

知识点：前缀和、模运算、线性扫描

记总和与前缀和为

$$S=\sum_{t=1}^{n}a_t,\qquad P_i=\sum_{t=1}^{i}a_t.$$

位置 $i$ 的前缀和为 $P_i$，后缀和为

$$S-P_{i-1}=S-P_i+a_i.$$

因此扫描数组时维护当前的 $P_i$，比较

$$P_i\bmod m\quad\text{和}\quad(S-P_i+a_i)\bmod m.$$

由于 $a_i$ 可能为负数，需要将余数规范到 $[0,m-1]$ 后再比较。

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

void solve() {
    int n, m, s = 0;
    cin >> n >> m;

    vector<int> a(n);
    for (auto &v : a) cin >> v, s += v;

    auto norm = [&](int x) {
        x %= m;
        if (x < 0) x += m;
        return x;
    };

    int p = 0, ans = 0;
    for (int i = 0; i < n; ++i) p += a[i], ans += norm(p) == norm(s - p + a[i]);

    cout << ans << endl;
}

D 小月的储物格

知识点：有序集合、循环模拟

将储物格编号改为从 $0$ 开始，并把所有未占用的位置放入有序集合 $\texttt{st}$。

设上一轮占用的位置为 $l$，本轮走 $d_i$ 步后先到达

$$p=(l+d_i)\bmod n.$$

由于经过已占用位置也计入步数，所以只需在未占用集合中寻找从 $p$ 开始的第一个位置。调用 $\texttt{lower\_bound}(p)$；若迭代器到达末尾，则回到集合首元素。选中后累加标签值并删除该位置。

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

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (auto &v : a) cin >> v;

    set<int> st;
    for (int i = 0; i < n; ++i) st.insert(i);

    int s = 0, l = 0;
    for (int i = 0, x; i < m; ++i) {
        cin >> x;
        int p = (l + x) % n;

        auto it = st.lower_bound(p);
        if (it == st.end()) it = st.begin();

        l = *it, s += a[l];
        st.erase(it);
    }

    cout << s << " " << l + 1 << endl;
}

E 小月的栈（Easy）

知识点：状态压缩、二维 DP、前缀和

感觉 $\tt E$ 比 $\tt G$ 要难 —— mktx

固定取出第一堆前 $i$ 件、第二堆前 $j$ 件时，价值已经确定为前缀和 $A_i+B_j$，因此只需判断这种取法是否可行。

令 $\texttt{dp}_{i,j,0}$ 表示最后取出的物品来自第一堆，令 $\texttt{dp}_{i,j,1}$ 表示最后取出的物品来自第二堆。

若最后取第一堆的下一件物品，则前一步可以来自第二堆，也可以来自第一堆且前一件标记为 $0$：

$$\texttt{dp}_{i,j,0}=\texttt{dp}_{i-1,j,1}\lor\left(\texttt{dp}_{i-,j,0}\land c_{i-1}=0\right).$$

同理，取第二堆时有

$$\texttt{dp}_{i,j,1}=\texttt{dp}_{i,j-1,0}\lor\left(\texttt{dp}_{i,j-1,1}\land d_{j-1}=0\right).$$

初始状态 $(0,0)$ 可以从任意一堆开始，因此两个状态都置为真。枚举所有满足 $i+j=k$ 的可行状态，取最大前缀和；若不存在可行状态，则输出 $\texttt{IMPOSSIBLE}$。

时间复杂度 $\mathcal{O}(\min(n,k)\min(m,k))$。

constexpr int inf = 2e18 + 9;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n + 1), b(m + 1);
    vector<int> c(n + 1), d(m + 1);

    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> c[i], a[i] += a[i - 1];
    for (int i = 1; i <= m; ++i)
        cin >> b[i] >> d[i], b[i] += b[i - 1];

    int ans = -inf;
    m = min(m, k);

    vector<pii> dp(m + 1);

    for (int i = 0; i <= min(n, k); ++i) {
        vector<pii> ndp(m + 1);

        for (int j = 0; j <= min(m, k - i); ++j) {
            if (i == 0 && j == 0) {
                ndp[j] = {1, 1};
            } else {
                if (i > 0) ndp[j][0] = dp[j][1] || (dp[j][0] && c[i - 1] == 0);
                if (j > 0) ndp[j][1] = ndp[j - 1][0] || (ndp[j - 1][1] && d[j - 1] == 0);
            }
            if (i + j == k && (ndp[j][0] || ndp[j][1])) ans = max(ans, a[i] + b[j]);
        }

        dp.swap(ndp);
    }

    if (ans == -inf)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << ans << endl;
}

F 小月的川菜

知识点：排序、排列计数、容斥

将耐辣上限排序。先考虑只要求所有人都不喝奶的情况。

处理排序后的某位朋友时，设已经给前面的受限朋友分配了 $p$ 道菜，当前上限为 $a_i$。由于前面分配的菜都不超过 $a_i$，当前仍可选择的菜恰有

$$a_i-p$$

道。若该值不正，则这种分配不存在；否则将答案乘上 $a_i-p$。

定义 $F(u,v)$ 表示下标为 $u,v$ 的人暂时不受限制，其余人都必须不喝奶。去掉的人最后分配剩余菜品：

• 去掉 $0$ 个人，不需要额外乘法；
• 去掉 $1$ 个人，剩余菜品唯一确定；
• 去掉 $2$ 个人，剩余的 $2$ 道菜有 $2!$ 种分配。

固定恰好喝奶的人为 $i,j$ 时，先用 $F(i,j)$ 放宽这两人的限制，再用容斥去掉其中一人也不喝奶的情况：

$$F(i,j)-F(i)-F(j)+F(\varnothing).$$

最后枚举所有 $i<j$。每个恰好有 $2$ 位朋友喝奶的排列只会被对应的下标对统计一次。

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

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

    vector<int> a(n);
    for (auto &v : a) cin >> v;
    sort(a.begin(), a.end());

    auto count = [&](int u, int v) -> Z {
        Z r = 1;
        int p = 0;

        for (int i = 0; i < n; ++i) {
            if (i == u || i == v) continue;

            int c = a[i] - p;
            if (c <= 0) return 0;

            r *= c;
            ++p;
        }

        if (v != -1) r *= 2;
        return r;
    };

    Z af = count(-1, -1);

    vector<Z> f(n);
    for (int i = 0; i < n; ++i)
        f[i] = count(i, -1);

    Z ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            ans += count(i, j) - f[i] - f[j] + af;

    cout << ans << endl;
}

G 小月的栈（Hard）

知识点：前缀和、可行性判定、贪心构造

固定取出第一堆前 $i$ 件、第二堆前 $j$ 件。记价值前缀和与标记前缀和为

$$A_i=\sum_{t=1}^{i}a_t,\qquad B_j=\sum_{t=1}^{j}b_t,$$

$$C_i=\sum_{t=1}^{i}c_t,\qquad D_j=\sum_{t=1}^{j}d_t.$$

第一堆前 $i-1$ 件中每个标记为 $1$ 的物品，都必须在后面紧接着取一件第二堆物品，因此必须满足

$$C_{i-1}\le j.$$

同理，第二堆必须满足

$$D_{j-1}\le i.$$

各自最后一件物品不计入对应条件，因为其中一件可以作为整个序列的最后一次操作。上述两个条件也是充分的：可以从序列末尾递归选择一堆的末件删除，剩余前缀仍满足同样的不等式，直到构造出合法的交错顺序。

于是枚举 $i$，令 $j=k-i$，检查两个条件后最大化 $A_i+B_j$。若没有可行方案，则输出 $\texttt{IMPOSSIBLE}$。

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

constexpr int inf = 2e18 + 9;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n + 1), b(m + 1);
    vector<int> c(n + 1), d(m + 1);

    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> c[i],
        a[i] += a[i - 1],
        c[i] += c[i - 1];

    for (int i = 1; i <= m; ++i)
        cin >> b[i] >> d[i],
        b[i] += b[i - 1],
        d[i] += d[i - 1];

    int ans = -inf;

    for (int i = max(0LL, k - m); i <= min(n, k); ++i) {
        int j = k - i;

        if (i > 0 && c[i - 1] > j) continue;
        if (j > 0 && d[j - 1] > i) continue;

        ans = max(ans, a[i] + b[j]);
    }

    if (ans == -inf)
        cout << "IMPOSSIBLE" << endl;
    else
        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;
}

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