CSP-S 复赛

2019T1-P5657格雷码 ¶

给定位数 n 和从 0 开始的编号 k，
输出题目规定的反射构造中第 k 个格雷码，保留前导 0。

提示1-只找一个串

我先画出 2 位、3 位的排列。要求只有一个编号，还需要把前面的所有串都生成出来吗？

提示2-规模与整数边界

\(n\le 10\) 的 50% 数据可直接按定义生成 \(2^n\) 个串。\(k\le 5\times 10^6\) 的 80% 数据可以逐个算到 \(k\)，但 \(n\) 仍可能为 64，不能开 \(2^n\) 的数组。95% 数据用有符号 64 位数能存 \(k\)；最后 5% 需要 unsigned long long。\(k=0\) 时是全 0，但没有单独分值。

我先完成 \(n\le 10\) 的版本：写出反射生成过程，把得到的串按编号保存。这能拿到50分，也给我一个检查大算法的小工具。扩大范围时，我先问“为什么一定要保存前面的串”：只查询一个编号，就沿反射构造定位它；再观察编号的相邻二进制位，得到逐位计算。优化的是生成数量，不是把数组开得更大。

提示3-从反射看每一位

编号的二进制最高位不变，后面每位等于编号中相邻两位的异或。这与“后半段反向”一致：进入后半段后，剩余编号被逐位取反。于是整个数为 \(k\mathbin{\oplus}\lfloor k/2\rfloor\)，最后固定输出 \(n\) 位。不要计算 1ULL << 64。

提示4-自己动手检查

我会先列出 \(n=2\) 的全部答案，再检查每次只变一位。到 \(n=64\) 时，我专门检查读入类型和移位位数，而不只测普通编号。

代码-满分

时间 \(O(n)\)，空间 \(O(1)\)。移位的位数只在 0～63，\(n=64\)、\(k=2^{64}-1\) 也合法。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    unsigned long long k;
    cin >> n >> k;

    // 我先用小规模反射排列核对这一式；一致后才用它直接计算目标编号。
    unsigned long long gray = k ^ (k >> 1);
    for (int i = n - 1; i >= 0; i--) cout << ((gray >> i) & 1ULL);

    return 0;
}

2019T2-P5658括号树 ¶

每个树结点有一个括号。对每条根到结点的路径，
统计其中合法括号子串的数量 k_i，输出所有 i×k_i 的异或和。
子串按起止位置区分。

提示1-先做一条路径

我先把树画成一条链。追加一个右括号时，哪些合法子串是这次新出现的？它们一定以这个右括号结尾。

提示2-链与小树分别省掉什么

测试点1～7、11～14都是链，共55分：没有分支，可以直接用括号栈处理字符串。\(n\le 2000\) 的点1～10共50分，可以每个结点向祖先扫描，平衡值第一次变负就停止，平衡为0时计数，\(O(n^2)\)。两组覆盖有重叠，不能相加为105分。全数据 \(n\le 5\times 10^5\)，真正的危险是长链导致递归栈溢出。

我会先选链这个条件练习：把根路径当字符串，追加一个括号只更新以它结尾的答案。若还不会这一步，就先在 \(n\le 2000\) 时枚举每个右端点向前检查，拿50分。再对照不同结点的根路径，我发现公共前缀被反复扫描；把括号栈顶和路径答案保存成父亲的状态，就能让每条树边只参与一次更新。

提示3-匹配后还能接上哪些串

我设 \(\mathrm{end}[u]\) 为以 \(u\) 结尾的合法子串数。右括号 \(u\) 匹配左括号 \(v\) 时，先数从 \(v\) 到 \(u\) 的最短合法段；它还能接在任何以 \(\mathrm{parent}[v]\) 结尾的合法串后面。因此：

\[ \mathrm{end}[u]=\mathrm{end}[\mathrm{parent}[v]]+1. \]

路径总数只需在父亲的答案上加这次新出现的子串：

\[ \mathrm{sum}[u]=\mathrm{sum}[\mathrm{parent}[u]]+\mathrm{end}[u]. \]

提示4-把栈变成每个结点的状态

父亲编号小于儿子，可以按编号处理。\(\mathrm{top}[u]\) 记录这条路径最近的未匹配左括号；左括号入栈，匹配的右括号取 \(\mathrm{top}[\mathrm{parent}[u]]\) 并跳到它之前的栈顶。不同儿子读取同一份父状态，不会互相影响；没有可匹配左括号时 \(\mathrm{end}[u]=0\)。

提示5-自己动手检查

先用 ()() 和 (()) 手算以每个位置结尾的数量，再把同一父亲接两个不同孩子。我会检查一个孩子的匹配是否误改了另一个孩子的栈。

代码-满分

时间、空间均为 \(O(n)\)。路径计数及 \(i\,k_i\) 用 long long；最大乘积小于 \(2^{63}\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
int parent[N], top[N];
long long ending[N], total[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    for (int u = 2; u <= n; u++) cin >> parent[u];

    long long answer = 0;
    for (int u = 1; u <= n; u++) {
        int p = parent[u];
        top[u] = top[p];
        if (s[u] == '(') {
            top[u] = u;
        } else if (top[p] != 0) {
            int v = top[p];
            // 我先数最短的新合法段，再接上 v 前面的合法串，避免漏掉连续的 ()()。
            ending[u] = ending[parent[v]] + 1;
            top[u] = top[parent[v]];
        }
        total[u] = total[p] + ending[u];
        answer ^= 1LL * u * total[u];
    }

    cout << answer;

    return 0;
}

2019T3-P5659树上的数 ¶

树上放着 1～n，每个数出现一次。每条边恰好操作一次：
交换两个端点的数，然后删边。
输出按数字从小到大排列的最终位置，使这个排列字典序最小。

提示1-字典序先保住什么

我先只考虑数字 1 的最终位置。能把它放到最小编号后，再决定数字 2；但不能为了当前的小编号，让后面根本无解。

提示2-先看星形树

\(n\le 10\) 的点1～2共10分，可枚举 \((n-1)!\) 个删边顺序。星形树的点8～12共25分：按删边顺序，中心和所有叶子的数恰好构成一个大置换环，所以可逐个选最小终点，但最后一步前不能闭合小环。链的点3～7共25分，每点最多两条边，局部顺序只剩两种。一般树 \(n\le 2000\)，仍可每个数搜索整棵树，但不能枚举全局顺序。

面对一般树，我先缩到 \(n\le 10\)：枚举删边顺序，模拟交换，比较最终位置序列，争取10分。接着画星形树，交换全经过中心，问题变成构造一个大置换环，这条性质可拿25分。要扩展到一般树，我不再猜全局顺序，而是逐个记录数字走过的路径在各点留下什么局部先后要求；并查集只是用来检查这些要求还能否补成合法顺序。

提示3-路径把限制留在每个结点

数字从 \(s\) 移到 \(t\)，沿唯一路径移动。起点的第一条路径边须最先删除；中间点的入边和出边必须在该点的删边序列中相邻；终点的入边须最后删除。别的地方发生的操作可以插在中间，不要求全局相邻。

提示4-用一个虚拟端口统一三种限制

每个点的真实端口是邻边，另加虚拟端口，表示这个点本身。把“虚拟端口、从早到晚的邻边”视为一个环：起点限制是虚拟→出边，中转是入边→出边，终点是入边→虚拟。每个端口只能有一个前驱、一个后继；只能在覆盖该点全部端口后闭环。并查集记录已连成的链。树没有环，各点可行的局部邻边顺序可以扩展为全局删边顺序。

提示5-搜索与固定分开

从原位置的虚拟端口出发，沿能接上的端口搜索，找最小可结束的点；搜索时不修改限制，选定后再固定路径。以后保留这些限制，便不会破坏先前更小的数字。\(n>1\) 时不能回到原点：至少一次邻边操作会把原数移走，删边后不能走回原点。

提示6-自己动手检查

我会在三点链和四点星形树上枚举顺序，核对贪心结果。特别试“看似最小的终点会提前闭合小环”，观察为何必须拒绝它。

代码-25分

仅按星形树性质推导，覆盖点8～12。对原位置到终点连有向边，每点入度、出度至多1；最后一次之前用并查集禁止小环，时间 \(O(n^2\alpha (n))\)。这段代码不适用于一般树。

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;
int position[N], parent[N];
bool used[N];

int findRoot(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findRoot(parent[x]);
}

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> position[i];
            parent[i] = i;
            used[i] = false;
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
        }

        for (int value = 1; value <= n; value++) {
            int s = position[value];
            for (int t = 1; t <= n; t++) {
                // 我先检查会不会提前成小环：还没放完全部数字时，小环会堵住后续安排。
                if (!used[t] && (value == n || findRoot(s) != findRoot(t))) {
                    used[t] = true;
                    parent[findRoot(s)] = findRoot(t);
                    if (value > 1) cout << ' ';
                    cout << t;
                    break;
                }
            }
        }
        cout << '\n';
    }

    return 0;
}

代码-满分

端口总数为 \(3n-2\)，时间 \(O(Tn^2\alpha (n))\)，空间 \(O(n)\)。每次搜索用显式栈，不依赖树高的递归。局部链的并查集按大小合并。

#include <bits/stdc++.h>

using namespace std;

struct Solver {
    int n;
    vector<vector<int>> ports;
    vector<int> owner, opposite, nextPort, previousPort, parent, size;
    vector<int> position, arrived, from;

    int findRoot(int x) {
        if (parent[x] == x) return x;
        return parent[x] = findRoot(parent[x]);
    }

    bool canJoin(int a, int b) {
        if (nextPort[a] != 0) return nextPort[a] == b;
        if (previousPort[b] != 0) return false;
        int x = findRoot(a), y = findRoot(b);
        // 我把局部顺序画成一个环；只有端口全在同一条链上时，才能把首尾接起来。
        return x != y || size[x] == int(ports[owner[a]].size()) + 1;
    }

    void join(int a, int b) {
        nextPort[a] = b;
        previousPort[b] = a;
        int x = findRoot(a), y = findRoot(b);
        if (x == y) return;
        if (size[x] < size[y]) swap(x, y);
        parent[y] = x;
        size[x] += size[y];
    }

    void run() {
        cin >> n;
        int count = 3 * n + 1;
        ports.assign(n + 1, {});
        owner.assign(count, 0);
        opposite.assign(count, 0);
        nextPort.assign(count, 0);
        previousPort.assign(count, 0);
        parent.resize(count);
        size.assign(count, 1);
        position.resize(n + 1);
        arrived.resize(n + 1);
        from.resize(n + 1);
        for (int i = 0; i < count; i++) parent[i] = i;
        for (int i = 1; i <= n; i++) {
            cin >> position[i];
            owner[i] = i;
        }
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            int a = n + 1 + 2 * i, b = a + 1;
            owner[a] = u;
            owner[b] = v;
            opposite[a] = b;
            opposite[b] = a;
            ports[u].push_back(a);
            ports[v].push_back(b);
        }

        for (int value = 1; value <= n; value++) {
            int s = position[value], best = n + 1;
            vector<int> stack = {s};
            from[s] = 0;
            arrived[s] = s;
            while (!stack.empty()) {
                int u = stack.back();
                stack.pop_back();
                if (u != s && canJoin(arrived[u], u)) best = min(best, u);
                for (int p : ports[u]) {
                    int v = owner[opposite[p]];
                    if (v == from[u] || !canJoin(arrived[u], p)) continue;
                    from[v] = u;
                    arrived[v] = opposite[p];
                    stack.push_back(v);
                }
            }
            if (n == 1) best = 1;
            if (n > 1) {
                join(arrived[best], best);
                for (int v = best; v != s; v = from[v]) {
                    int u = from[v];
                    join(arrived[u], opposite[arrived[v]]);
                }
            }
            if (value > 1) cout << ' ';
            cout << best;
        }
        cout << '\n';
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        Solver solver;
        solver.run();
    }

    return 0;
}

2019T4-P5664Emiya家今天的饭 ¶

每种烹饪方法至多选一道菜，至少选一道。
同一种食材的菜不能超过总菜数的一半。
a[i][j] 是该方法、食材组合的不同菜数，求合法方案数模 998244353。

提示1-先去掉食材限制

我先只保留“每种方法最多一道”。一行可以不选，也可以从这一行的所有菜中选一道，方案数怎样相乘？

提示2-小列数的意义

\(n\le 10\) 的点1～8共32分，可枚举每行不选或选哪列，最后检查食材次数，并把各行 \(a_{i,j}\) 相乘。\(m=2\) 的点1、3、5、7、9～12共32分：两种食材都不超过一半，就必须一样多，状态只记两者数量差。\(m=3\) 不能只检查两列相等；\(a_{i,j}\) 小也不等于可把所有菜的子集枚举出来。全数据 \(n\le 100\)、\(m\le 2000\)，状态维数应跟行数走。

我先看 \(m=2\)：不能有一种超过一半，等价于两种数量相等，熟悉的差值DP就能拿32分。然后试三种各选一份：这提醒我不能把“数量相等”直接推广。我要保留差值状态，但改成“指定食材与其他所有食材”的差，只统计这一种超过一半的坏方案。这样每次仍是同一个简单DP，外层枚举食材就能处理一般数据。

提示3-坏方案不会重复扣

我先去掉限制，记第 \(i\) 行的菜数之和为 \(R_i=\sum_{j=1}^{m}a_{i,j}\)。每行“不选或选一道”的方案数是 \(1+R_i\)，所以非空方案总数为：

\[ \prod_{i=1}^{n}(1+R_i)-1. \]

若某食材超过一半，不可能另一个食材也超过一半。我从这个总数中分别减去每列的坏方案，不需要再处理交集。

提示4-用数量差代替总菜数

固定食材 \(j\)，我用 \(\mathrm{dp}[d]\) 表示已处理行中“选 \(j\) 的数量减选其他食材的数量”为 \(d\) 的加权方案数。第 \(i\) 行只有三种决定：

\[ \begin{aligned} \mathrm{next}[d] &\mathrel{+}=\mathrm{dp}[d] &&\text{不选},\\ \mathrm{next}[d+1] &\mathrel{+}=\mathrm{dp}[d]\,a_{i,j} &&\text{选食材 }j,\\ \mathrm{next}[d-1] &\mathrel{+}=\mathrm{dp}[d](R_i-a_{i,j}) &&\text{选其他食材}. \end{aligned} \]

全部行处理完，\(d>0\) 恰表示食材 \(j\) 超过一半。空方案的 \(d=0\)，不会被扣。每一步都对 \(998244353\) 取模。

提示5-自己动手检查

先手算一行时为什么答案必为0，再试两行、两列且四个菜数都为1。写出每一步差值的含义，检查空方案只减一次。

代码-32分

仅用于 \(m=2\)，覆盖点1、3、5、7、9～12，共32分。\(\mathrm{dp}[d]\) 表示已处理各行、两种食材数量差为 \(d\) 的方案数。每行可以不选、选第一种或选第二种；最后取差为0，减掉全不选的空方案。时间 \(O(n^2)\)，空间 \(O(n)\)。\(m>2\) 时两种食材一样多不再是合法性的充分条件。

#include <bits/stdc++.h>

using namespace std;

const int N = 205, MOD = 998244353, OFFSET = 100;
long long dp[N], nextDp[N];

int main() {
    int n, m;
    cin >> n >> m;
    dp[OFFSET] = 1;
    for (int i = 1; i <= n; i++) {
        long long first, second;
        cin >> first >> second;
        fill(nextDp, nextDp + N, 0);
        for (int d = -(i - 1); d <= i - 1; d++) {
            int j = d + OFFSET;
            nextDp[j] = (nextDp[j] + dp[j]) % MOD;
            nextDp[j + 1] = (nextDp[j + 1] + dp[j] * first) % MOD;
            nextDp[j - 1] = (nextDp[j - 1] + dp[j] * second) % MOD;
        }
        copy(nextDp, nextDp + N, dp);
    }
    // 我用两种数量相等筛合法方案，但全不选也相等，所以还要减去空方案。
    cout << (dp[OFFSET] - 1 + MOD) % MOD;

    return 0;
}

代码-满分

时间 \(O(mn^2)\)，空间 \(O(nm+n)\)。菜数按模数相乘，差值用偏移量映射到数组。

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 105, M = 2005, OFFSET = 105;
long long a[N][M], row[N], dp[215], nextDp[215];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    long long answer = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            row[i] = (row[i] + a[i][j]) % MOD;
        }
        answer = answer * (row[i] + 1) % MOD;
    }
    answer = (answer - 1 + MOD) % MOD;

    for (int j = 1; j <= m; j++) {
        memset(dp, 0, sizeof dp);
        dp[OFFSET] = 1;
        for (int i = 1; i <= n; i++) {
            memset(nextDp, 0, sizeof nextDp);
            long long other = (row[i] - a[i][j] + MOD) % MOD;
            for (int d = -(i - 1); d <= i - 1; d++) {
                int p = d + OFFSET;
                nextDp[p] = (nextDp[p] + dp[p]) % MOD;
                nextDp[p + 1] = (nextDp[p + 1] + dp[p] * a[i][j]) % MOD;
                nextDp[p - 1] = (nextDp[p - 1] + dp[p] * other) % MOD;
            }
            copy(nextDp, nextDp + 215, dp);
        }
        // 我检查坏方案的定义是严格超过一半，因此只扣正差值；两种食材不能同时超过一半。
        for (int d = 1; d <= n; d++) answer = (answer - dp[OFFSET + d] + MOD) % MOD;
    }

    cout << answer;

    return 0;
}

2019T5-P5665划分 ¶

将正整数序列切成连续的若干段，要求各段的和非递减。
最小化各段和的平方之和。type=1 时按题目给定规则生成序列。

提示1-不能见小数就单独切

我先试每个数单独一段。遇到下降就不合法；把它合并到左边或右边，影响也不同。例如 5、1、7，怎样得到不下降的段和？

提示2-每档范围对应什么

点1～3的 \(n\le 10\)，可枚举全部切点，共12分。点4～16的 \(n\le 5000\)，加上小数据共64分，可用 \(O(n^2)\) 的贪心动态规划。\(n\le 5\times 10^5\) 还需要减少枚举；最后 \(n\le 4\times 10^7\) 还要避免大量对象和重复数组。没有零数，前缀和严格递增；这不是无关条件，而是后面队列与贪心成立的基础。type=1 只是压缩输入，不能因此换一种算法。

我先在 \(n\le 10\) 枚举切点，拿12分，并用小序列记录最优划分。观察正数前缀和后，我尝试只保留末段最小的可行方案；先枚举所有前驱，完成 \(n\le 5000\) 的64分版本。还想提高时，我盯住内层扫描：某候选若更晚可用且末段更大，是否以后都无用？证明这个支配关系后才删候选，把二重循环换成单调队列。

提示3-保留末段最小的方案

我记 \(S_i\) 为前缀和，\(\mathrm{pre}[i]\) 为前 \(i\) 项划分的最后切点。若最后一段从 \(j+1\) 开始，要保证它的和不少于前一段：

\[ S_i-S_j\ge S_j-S_{\mathrm{pre}[j]}. \]

先枚举所有可行 \(j\)，再选最大的一个，末段和便最小。为什么这同时能使平方和最小，还需要下面的贪心理由，不能只凭样例决定。

这个结论不只是“多切几段更小”。比较两种合法切法，去掉公共前缀后，将交替的切点配对；把较靠后的可行切点作为最后切点，相当于把较大的段的一部分移给不更大的段。若大段为 \(x\)、小段为 \(y\)，移出 δ 且不越过平衡位置，平方和的变化为 \(-2\delta(x-y-\delta)\le0\)。对交错段依次调整，并用短前缀的结论归纳，就得到末段最小方案也最优。正数保证调整顺序不会倒退。若允许负数，这个结论不能照搬。

提示4-从枚举走到队列

\(j\) 能接 \(i\) 等价于 \(\mathrm{key}[j]=2S_j-S_{\mathrm{pre}[j]}\le S_i\)。对两个候选 \(j<k\)，若 \(\mathrm{key}[k]\le\mathrm{key}[j]\)，\(k\) 不但更早可用，还能给出更小末段，\(j\) 永远不会更优，可以从队尾删掉。队头前进到最大的可用候选，整个过程每个下标进出至多一次。最后沿 pre 回溯，求平方和。

提示5-自己动手检查

我会用 5、1、7 比较不同切法，再用全相等序列检查每个数能否单独成段。小规模枚举可核对贪心；大样例还要检查生成过程与平方和类型。

代码-满分

时间 \(O(n+m)\)，空间 \(O(n)\)。前缀和用 long long，最终平方和用 __int128（GCC/Clang 的128位整数扩展），否则生成数据可能溢出。三个主要数组约16n字节，\(n=4\times 10^7\) 时约610MiB，须使用原题的大内存限制；不能按普通256MiB题目配置运行。

#include <bits/stdc++.h>

using namespace std;

const long long MASK = (1LL << 30) - 1;
struct Block { int end; long long low, high; };

void printInteger(__int128 value) {
    if (value == 0) {
        cout << 0;
        return;
    }
    string s;
    while (value > 0) {
        s.push_back(char('0' + value % 10));
        value /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, type;
    cin >> n >> type;
    vector<long long> sum(n + 1);
    vector<int> pre(n + 1), queue(n + 1);
    if (type == 0) {
        for (int i = 1; i <= n; i++) {
            long long a;
            cin >> a;
            sum[i] = sum[i - 1] + a;
        }
    } else {
        long long x, y, z, b1, b2;
        int m;
        cin >> x >> y >> z >> b1 >> b2 >> m;
        vector<Block> blocks(m);
        for (Block &b : blocks) cin >> b.end >> b.low >> b.high;
        int block = 0;
        long long older = b1, newer = b2;
        for (int i = 1; i <= n; i++) {
            long long b;
            if (i == 1) b = b1;
            else if (i == 2) b = b2;
            else {
                b = (x * newer + y * older + z) & MASK;
                older = newer;
                newer = b;
            }
            while (i > blocks[block].end) block++;
            long long a = b % (blocks[block].high - blocks[block].low + 1) + blocks[block].low;
            sum[i] = sum[i - 1] + a;
        }
    }

    auto key = [&](int j) { return 2 * sum[j] - sum[pre[j]]; };
    int head = 0, tail = 0;
    queue[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (head < tail && key(queue[head + 1]) <= sum[i]) head++;
        pre[i] = queue[head];
        // 我先比较旧候选与 i 的启用门槛；旧候选又晚又差，以后也不可能更优。
        while (head < tail && key(queue[tail]) >= key(i)) tail--;
        queue[tail + 1] = i;
        tail++;
    }

    __int128 answer = 0;
    for (int i = n; i > 0; i = pre[i]) {
        __int128 length = sum[i] - sum[pre[i]];
        answer += length * length;
    }
    printInteger(answer);

    return 0;
}

2019T6-P5666树的重心 ¶

分别删除树的每一条边。每次产生两个连通块，
把两块所有重心的编号相加，再累加所有删边的贡献。
一块若有两个重心，两个都要计入。

提示1-先按定义检查一个块

删去一个候选重心后，最大连通块不能超过这块大小的一半。我先枚举断边并逐块算子树大小，怎样检查每个点？

提示2-链和完美二叉树

\(n\le 1999\) 的点1～8共40分，逐条断边后 \(O(n)\) 求两块重心，总计 \(O(n^2)\)。链的点9～11另有15分：按链顺序排点，断边后两段的重心就是中间一到两个位置，用编号前缀和可直接统计。完美二叉树的点12～15共20分，高度只有 \(O(\log n)\)，沿最大子树寻找重心很短；但点的原编号可被排列，不能用编号当层次。一般树可能退化成长链，需要跳跃。

我先按重心定义写一个 \(O(n^2)\) 版本，在 \(n\le 1999\) 的范围拿40分。遇到链时，把每块改成一段区间，重心就是中间位置，可另覆盖15分。再看满分的瓶颈：反复逐点沿最大分支移动。它让我想到倍增跳过同一方向的长路径；但断边会改块大小，我先选整树重心作根，让需要修改的一侧更容易分析。

提示3-先把整树重心当作根

我把整树重心 \(C\) 作为根。它的每个儿子分支至多 \(n/2\)。断去 \(v\) 的父边后，下方就是完整的 \(v\) 子树；上方删掉了 \(\mathrm{size}[v]\) 个点。包含 \(v\) 的根分支原来至多 \(n/2\)，删掉 \(\mathrm{size}[v]\) 后一定小于上方块的一半，因此上方重心若要离开 \(C\)，只会进入另一个未受影响的分支。

提示4-只沿重儿子走

对任意完整子树，若最大儿子大小大于总大小一半，重心一定在该儿子内。沿重儿子一直走到没有这样的儿子，便得到重心；若有儿子大小恰好一半，它也是重心。预处理重儿子倍增，就能快速找到停止位置。上方块先在 \(C\) 的分支中排除被删分支，再在剩下最大分支上使用相同跳跃。

提示5-自己动手检查

我先检查二点树：删边后两个单点都要计入。再检查四点链产生的两个重心，避免只记到一个；最后用长链检查有没有依赖深递归。

代码-满分

时间 \(O(Tn \log n)\)，空间 \(O(n \log n)\)。两次遍历都用显式顺序数组；累加用 long long。下面采用“整树重心作根”，避免换根时反复修改倍增表。

#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<vector<int>> graph(n + 1);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        vector<int> parent(n + 1), size(n + 1), heavy(n + 1), branch(n + 1), order;
        auto rootTree = [&](int root) {
            fill(parent.begin(), parent.end(), 0);
            order = {root};
            for (int i = 0; i < int(order.size()); i++) {
                int u = order[i];
                for (int v : graph[u]) if (v != parent[u]) {
                    parent[v] = u;
                    order.push_back(v);
                }
            }
            fill(size.begin(), size.end(), 1);
            size[0] = 0;
            fill(heavy.begin(), heavy.end(), 0);
            for (int i = n - 1; i >= 0; i--) {
                int u = order[i];
                for (int v : graph[u]) if (parent[v] == u) {
                    size[u] += size[v];
                    if (size[v] > size[heavy[u]]) heavy[u] = v;
                }
            }
        };
        rootTree(1);
        int center = 1;
        for (int u = 1; u <= n; u++) {
            if (max(n - size[u], size[heavy[u]]) * 2 <= n) {
                center = u;
                break;
            }
        }
        rootTree(center);
        for (int u : order) if (u != center) {
            branch[u] = parent[u] == center ? u : branch[parent[u]];
        }
        vector<array<int, LOG>> jump(n + 1);
        for (int u = 1; u <= n; u++) jump[u][0] = heavy[u];
        for (int j = 1; j < LOG; j++) {
            for (int u = 1; u <= n; u++) jump[u][j] = jump[jump[u][j - 1]][j - 1];
        }
        auto centroidSum = [&](int u, int total) {
            for (int j = LOG - 1; j >= 0; j--) {
                int v = jump[u][j];
                if (v && 2 * size[v] > total) u = v;
            }
            long long result = u;
            int v = heavy[u];
            if (v && 2 * size[v] == total) result += v;
            return result;
        };
        int first = 0, second = 0;
        for (int v : graph[center]) {
            if (size[v] > size[first]) {
                second = first;
                first = v;
            } else if (size[v] > size[second]) second = v;
        }

        long long answer = 0;
        for (int v = 1; v <= n; v++) if (v != center) {
            answer += centroidSum(v, size[v]);
            int total = n - size[v];
            int other = first == branch[v] ? second : first;
            // 我先排除被删点所在分支；只有完整保留的最大分支可能把上方重心拉过去。
            if (other && 2 * size[other] > total) answer += centroidSum(other, total);
            else {
                answer += center;
                if (other && 2 * size[other] == total) answer += other;
            }
        }
        cout << answer << '\n';
    }

    return 0;
}

2020T1-P7075儒略日 ¶

给定从公元前 4713 年 1 月 1 日起经过的整数天数，
按题目规定的儒略历、格里高利历规则输出日、月、年。
公元前加 BC；1582 年 10 月 4 日后直接到 10 月 15 日。

提示1-从零天开始检查

我先只处理第一年。\(r=0\) 对应起始日期，不是第二天；这年二月有多少天？跨过二月的边界怎样写？

提示2-小天数去掉了历法切换

点1的 \(r\le 365\) 共10分，都在公元前4713年，这是闰年；按月减天数即可。点2～4的 \(r\le 3\times 10^5\) 仍在公元前，没有历法切换，逐年模拟也能求解，但要把询问数乘进复杂度。全数据 \(Q\le 10^5\)、答案年份 \(\le10^9\)，逐年走不能通过。这里真正决定预处理大小的是切换历法前的固定天数，不是答案年份。

我先只写第一年的按月模拟，拿点1的10分，把 \(r=0\) 与月末边界写对。公元前的小天数仍可逐年模拟；扩大范围时，我发现难点集中在固定的历法切换前段，可以一次打表。后半段年份很大，但400年规则重复，于是我先除去整周期，再找周期内的位置，不必从第一年走到答案年份。

提示3-先把麻烦的前段打表

我用内部年份0表示公元前1年，−1表示公元前2年，因此初始为−4712，内部年份整除4就是儒略历闰年。这样“没有公元零年”只在输出时转换。打表到1600年之前，并在1582年10月5日跳到15日。

提示4-从1600年使用400年周期

1600年是格里高利历400年周期的起点，每周期146097天。先除出整周期，再在一个周期的年度前缀和里找所属年份，最后按月减天数。原材料的“前段打表、后段按周期跳过”保留；这里把逐年查询改成二分，避免十万次询问各扫描400年。

提示5-自己动手检查

我会连续检查二月最后一天与三月第一天，再检查1582年10月4日的下一天。输出公元前1年附近时，确认没有输出公元0年。

代码-10分

仅适用于点1的 \(0\le r\le365\)。起始年有366天，按月份扣除，每次询问 \(O(12)\)。超出第一年会越过月份数组。

#include <bits/stdc++.h>

using namespace std;

const int days[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int queries;
    cin >> queries;
    while (queries--) {
        int r;
        cin >> r;
        int month = 1;
        // 我先比较整月长度；只扣完整经过的月份，剩余量加1才是日期。
        while (r >= days[month]) {
            r -= days[month];
            month++;
        }
        cout << r + 1 << ' ' << month << " 4713 BC\n";
    }

    return 0;
}

代码-满分

固定前段约230万天；预处理 \(O(2.3\times10^6)\)，单次查询 \(O(\log400+12)\)，空间 \(O(2.3\times10^6)\)。\(r\)、周期对应年份用 long long。

#include <bits/stdc++.h>

using namespace std;

const long long CYCLE = 146097;
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int yearStart[401];
struct Date { int year, month, day; };

bool leap(long long year) {
    if (year <= 1582) return year % 4 == 0;
    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Date> early;
    early.reserve(2310000);
    int year = -4712, month = 1, day = 1;
    while (year < 1600) {
        early.push_back({year, month, day});
        day++;
        // 我先核对10月4日的下一天；这十天不存在，不能在表中给它们占位置。
        if (year == 1582 && month == 10 && day == 5) day = 15;
        int length = days[month] + (month == 2 && leap(year));
        if (day > length) {
            day = 1;
            month++;
            if (month == 13) {
                month = 1;
                year++;
            }
        }
    }
    for (int i = 0; i < 400; i++) yearStart[i + 1] = yearStart[i] + 365 + leap(1600 + i);

    int queries;
    cin >> queries;
    while (queries--) {
        long long r, resultYear;
        cin >> r;
        int resultMonth, resultDay;
        if (r < (long long)early.size()) {
            Date d = early[r];
            resultYear = d.year;
            resultMonth = d.month;
            resultDay = d.day;
        } else {
            r -= early.size();
            resultYear = 1600 + r / CYCLE * 400;
            int rest = r % CYCLE;
            int offset = int(upper_bound(yearStart, yearStart + 401, rest) - yearStart) - 1;
            resultYear += offset;
            rest -= yearStart[offset];
            resultMonth = 1;
            while (true) {
                int length = days[resultMonth] + (resultMonth == 2 && leap(resultYear));
                if (rest < length) break;
                rest -= length;
                resultMonth++;
            }
            resultDay = rest + 1;
        }
        cout << resultDay << ' ' << resultMonth << ' ';
        if (resultYear <= 0) cout << 1 - resultYear << " BC\n";
        else cout << resultYear << '\n';
    }

    return 0;
}

2020T2-P7076动物园 ¶

每个动物编号是 k 位二进制数。某些位为 1 时需要指定饲料。
加入一种新动物后，饲料清单不能增加。求还能加入多少种编号。
已有编号互不相同；要求中的饲料编号也互不相同。

提示1-先看一位的影响

我把已有编号按位取或。一位已经出现过1时，这一位对应的饲料还会因为加入动物而新增吗？

提示2-值域比饲料数重要

\(k\le 20\) 的40%数据可枚举 \(2^k\) 个编号，但不能对每个编号扫描所有动物与要求。\(k\le 30\) 的60%数据结果仍在普通整数范围；全数据 \(k\le 64\)，\(2^{64}\) 本身无法用 unsigned long long 表示。\(c\le 10^8\) 不适合按饲料编号开数组。\(n=0\)、\(m=0\)、\(k=0\) 都合法，没有单独分值，要认真处理。

我先在 \(k\le 20\) 时枚举所有编号，拿40%范围：预先把允许出现1的位算出来，逐个编号检查是否用了禁止位。放大 \(k\) 后，慢的是枚举 \(2^k\) 种组合；各位互不影响，每个自由位有两种选择，直接乘起来即可。\(c\) 很大没有关系，我只关心 \(k\) 个二进制位是否受限，而不是建立整个饲料值域的数组。

提示3-哪些位必须是0

若某位有饲料要求，却从未在已有动物里出现1，该位必须为0，否则会新增饲料。若已出现1，相关饲料都买过；若无要求，也可任选。\(q_i\) 互不相同保证不会用另一位购买的相同饲料绕过限制。

提示4-自由位计数与2的64次方

设自由位数为 \(f\)，可饲养编号共 \(2^f\) 种，已有 \(n\) 种全包含在内，答案 \(2^f-n\)。\(f=64\) 且 \(n=0\) 时直接输出 \(2^{64}\) 的十进制；\(n>0\) 时用无符号最大值减去 \((n-1)\)。移位永远不取64。

提示5-自己动手检查

我先试已有动物为空、要求为空、\(k=0\) 三种边界。然后把自由位数设成64，检查答案为 \(2^{64}\) 与 \(2^{64}-1\) 时怎样输出。

代码-满分

时间 \(O(n+m+k)\)，空间 \(O(k)\)。不需要按 \(c\) 开数组，也不需要存下全部已有编号。

#include <bits/stdc++.h>

using namespace std;

bool required[64];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, c, k;
    cin >> n >> m >> c >> k;
    unsigned long long seen = 0;
    for (int i = 0; i < n; i++) {
        unsigned long long x;
        cin >> x;
        seen |= x;
    }
    for (int i = 0; i < m; i++) {
        int p, q;
        cin >> p >> q;
        required[p] = true;
    }

    int freeBits = 0;
    for (int p = 0; p < k; p++) {
        if (!required[p] || ((seen >> p) & 1ULL)) freeBits++;
    }
    if (freeBits == 64) {
        // 我先检查自由位数是否为64；不能先移位算 2^64 再判断，因为那个移位本身不合法。
        if (n == 0) cout << "18446744073709551616";
        else cout << numeric_limits<unsigned long long>::max() - (n - 1);
    } else cout << (1ULL << freeBits) - n;

    return 0;
}

2020T3-P7077函数调用 ¶

函数分为单点加、全体乘、按顺序调用其他函数三种。
调用关系无递归，但函数可以重复调用。
按给定顺序执行后，输出数组，模 998244353。

提示1-为什么不能直接展开

我先照顺序执行函数。如果一个函数调用两个相同的函数，层层重复，展开次数是否仍与函数个数成正比？小图也可能展开成指数次操作。

提示2-特殊条件去掉哪种交互

点5～6、12～13不含乘法或不含加法，共20分。不含乘法时，单点加的贡献就是调用次数乘加数；不含加法时，只需求总乘数。点7、14没有复合调用，共10分，可以从后往前维护后缀乘积。调用树的点1～2、8～9、15～16共30分，没有子函数被多个父函数共享，可处理每次顶层调用，但仍要算 \(Q\) 的重复。全图真正规模是 \(n+m+Q+\sum_j C_j\)，最多约130万，不是展开次数。

我先选没有复合调用的10分数据，从序列末尾维护后缀乘积，观察一次加法最后被放大多少。没有乘法时更简单，只数加法被调用几次。推广到共享子函数的图后，直接展开会重复做同一段；我把“函数整体的乘数”和“加法的放大系数”分开保存，前者从孩子到父亲算，后者从父亲到孩子传。

提示3-先求每个函数的乘数

\(\mathrm{mul}[u]\) 只表示一次调用 \(u\) 会给已有数据乘多少倍：加法为1，乘法为 \(V\)，复合函数为所有子函数 mul 的乘积。调用图拓扑排序后逆序处理，孩子先计算。

提示4-加法最后会被放大多少

一个加法的贡献只受它后面的乘法影响。\(\mathrm{cnt}[u]\) 记录所有 \(u\) 调用携带的放大系数之和；复合函数从右往左看，第 \(j\) 个孩子得到 \(\mathrm{cnt}[u]\) 乘右侧孩子乘数积。顶层序列作为0号复合函数，\(\mathrm{cnt}[0]=1\)，再按拓扑序向下传播。乘数为0时仍正确，不用除法或逆元。

提示5-自己动手检查

我会手算“加、乘、加”和“乘、加、乘”，确认方向。再让一个子函数重复出现两次，并加入乘0，检查没有依赖除法。

代码-满分

时间、空间 \(O(n+m+Q+\sum_j C_j)\)。不展开重复调用；拓扑排序避免递归过深。

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    vector<vector<int>> calls(m + 1);
    vector<int> type(m + 1, 3), position(m + 1), indegree(m + 1);
    vector<long long> value(m + 1), mul(m + 1, 1), count(m + 1);
    for (int u = 1; u <= m; u++) {
        cin >> type[u];
        if (type[u] == 1) cin >> position[u] >> value[u];
        else if (type[u] == 2) cin >> value[u];
        else {
            int length;
            cin >> length;
            calls[u].resize(length);
            for (int &v : calls[u]) {
                cin >> v;
                indegree[v]++;
            }
        }
    }
    int q;
    cin >> q;
    calls[0].resize(q);
    for (int &v : calls[0]) {
        cin >> v;
        indegree[v]++;
    }
    queue<int> ready;
    vector<int> order;
    for (int u = 0; u <= m; u++) if (indegree[u] == 0) ready.push(u);
    while (!ready.empty()) {
        int u = ready.front();
        ready.pop();
        order.push_back(u);
        for (int v : calls[u]) {
            indegree[v]--;
            if (indegree[v] == 0) ready.push(v);
        }
    }
    for (int i = m; i >= 0; i--) {
        int u = order[i];
        if (type[u] == 2) mul[u] = value[u];
        for (int v : calls[u]) mul[u] = mul[u] * mul[v] % MOD;
    }
    count[0] = 1;
    for (int u : order) {
        long long suffix = 1;
        for (int i = int(calls[u].size()) - 1; i >= 0; i--) {
            int v = calls[u][i];
            // 我用“加后再乘”的小例子核对方向；这个加法只被它后面的调用放大。
            count[v] = (count[v] + count[u] * suffix) % MOD;
            suffix = suffix * mul[v] % MOD;
        }
    }
    for (int i = 1; i <= n; i++) a[i] = a[i] * mul[0] % MOD;
    for (int u = 1; u <= m; u++) if (type[u] == 1) {
        int p = position[u];
        a[p] = (a[p] + count[u] * value[u]) % MOD;
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << a[i];
    }

    return 0;
}

2020T4-P7078贪吃蛇 ¶

每轮最强蛇可吃最弱蛇，体力变为两者之差；也可停止游戏。
蛇先确保自己不会被吃，再尽量多吃。体力相同时编号大的更强。
多组数据依次修改初始体力，每组初始序列都已按体力不降排列。

提示1-吃得下不等于敢吃

我先试三条蛇。最强蛇吃完变成最弱时，下一条蛇会不会吃掉它？只有保证自己活下来，才会真的动口。

提示2-小规模与有序性质

\(n=3\) 的20%数据只需比较吃后是否会成为弱者；\(n\le 10\) 的40%可递归模拟最优决策，不能把“不吃”当随机分支。\(n\le 2000\) 的55%可每轮排序或顺序维护。大数据 \(n\le 10^6\)、\(T\le 10\)，输入已排序，修改完成后也保证排序，不用重排。体力为0和相同体力都合法，必须一起比较编号。

我先完成 \(n=3\) 的20%数据，逐个比较“吃后是否会被吃”，建立决策含义。再在 \(n\le 10\) 递归询问后面的最强蛇敢不敢吃，拿40%范围。做到 \(n\le 2000\) 时，可以先用排序维护；优化时，我观察题目给的初始有序性质，以及新产生的差值是否也有序，才把反复排序改成两个队列。决策规则与维护数据的方法分开改，方便定位错误。

提示3-不会变最弱就能放心吃

若吃后仍不是最弱，它暂时不会被吃。之后别的最强蛇吃掉更强的弱者，吃后的体力不会超过它；因此不会越过它去威胁它。可放心吃，直到一次吃后将变最弱。

提示4-危险阶段只问下一条敢不敢

吃后变最弱，当前蛇能吃当且仅当下一条最强蛇不敢吃它。如果下一条吃后又变最弱，就继续向后问；直到剩两条或某次吃后不再最弱，此时必吃。倒推时每个危险步骤把真假翻转，只有连续危险次数的奇偶性重要。首次危险时最多再发生一次真实进食，随后停止。

提示5-用两个有序队列维护

安全阶段的最大体力不增、最小体力不减，所以新产生的差值不增。原始蛇放一个升序双端队列，新蛇从另一个队列头部插入，取全局两端只需比较队首、队尾。危险阶段新产生的最弱蛇单独保存，只从两队列取最强蛇。

提示6-自己动手检查

我会同时测试零体力、相同体力但编号不同、连续多次吃后变最弱。多组修改时，确认改的是初始数组，而不是上一场游戏留下的数组。

代码-满分

时间 \(O(Tn+\sum k)\)，空间 \(O(n)\)。每组都从修改后的初始数组重新模拟，不把上一组游戏结束的体力拿来修改。

#include <bits/stdc++.h>

using namespace std;

using Snake = pair<long long, int>;

int solve(const vector<long long> &a) {
    int n = int(a.size()) - 1;
    deque<Snake> original, changed;
    for (int i = 1; i <= n; i++) original.push_back({a[i], i});
    auto smallest = [&]() {
        if (original.empty()) return changed.front();
        if (changed.empty()) return original.front();
        return min(original.front(), changed.front());
    };
    auto takeMin = [&]() {
        Snake s = smallest();
        if (!original.empty() && original.front() == s) original.pop_front();
        else changed.pop_front();
        return s;
    };
    auto takeMax = [&]() {
        Snake s;
        if (original.empty()) s = changed.back();
        else if (changed.empty()) s = original.back();
        else s = max(original.back(), changed.back());
        if (!original.empty() && original.back() == s) original.pop_back();
        else changed.pop_back();
        return s;
    };

    int alive = n;
    while (alive > 2) {
        Snake weak = takeMin(), strong = takeMax();
        strong.first -= weak.first;
        if (strong > smallest()) {
            changed.push_front(strong);
            alive--;
            continue;
        }
        int dangerous = 1;
        Snake currentMin = strong;
        // 我先询问下一条蛇敢不敢吃，再倒推当前决策；探查过程不算真实进食次数。
        while (original.size() + changed.size() > 1) {
            Snake next = takeMax();
            next.first -= currentMin.first;
            if (next > smallest()) break;
            dangerous++;
            currentMin = next;
        }
        return alive - (dangerous % 2 == 0);
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests, n;
    cin >> tests >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(a) << '\n';
    for (int t = 1; t < tests; t++) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            long long y;
            cin >> x >> y;
            a[x] = y;
        }
        cout << solve(a) << '\n';
    }

    return 0;
}

2021T1-P7913廊桥分配 ¶

把 n 个廊桥分给国内、国际两区。航班先到先得，
有空位就必须停靠，否则去远机位。求能停靠的最多航班数。

提示1-先固定一种分配

我先试给国内 \(x\) 个、国际 \(n-x\) 个，然后按到达时间模拟。不能为了后来的短航班而拒绝当前航班。

提示2-暴力覆盖与特殊输入

\(n\le100\)、\(m_1+m_2\le100\) 的20%数据适合反复模拟；两者均不超过 \(5000\) 的40%可枚举分配，并用小根堆维护离开时间。全数据各时刻互不相同，省掉了同时到达、离开的约定问题；这不是把长航班优先换成短航班的理由。给某区0个廊桥也是必须枚举的边界。

我先枚举国内分到的廊桥数，每次用小根堆模拟到达和离开，这就是40%范围的基础版本。接着比较容量 \(x\) 和 \(x+1\) 的两次模拟：若总挑最小空闲编号，前 \(x\) 个编号的状态是否会受第 \(x+1\) 个影响？按航班到达顺序证明不会后，我只模拟一次，再用前缀和回答所有容量，省掉重复模拟这一层。

提示3-一次模拟得到所有容量

保留原材料的关键观察：每架航班总取编号最小的空闲廊桥。先用 \(n\) 个廊桥模拟，分配到 \(1\sim x\) 号的航班数，恰好等于只有 \(x\) 个廊桥时的数量。按到达顺序归纳：只要前 \(x\) 个廊桥的占用状态一致，当前航班是否能进入它们也一致；用到更大编号的航班不会改变前 \(x\) 个的状态。

提示4-空闲编号与离开时间分别管理

一个小根堆放空闲编号，另一个放“离开时间、编号”。新航班来时先归还已经离开的廊桥，再选最小空闲编号。各编号计数做前缀和，两区各模拟一次，最后枚举 \(x\)。

提示5-自己动手检查

我会先把某区容量设为0，再安排连续不重叠航班与全部重叠航班。对小数据逐个容量重算，核对一次模拟得到的前缀和。

代码-40分

按 \(n\le5000\)、\(m_1+m_2\le5000\) 的范围推导，覆盖40%数据，时间 \(O(n(m_1+m_2)\log (n+1))\)。此处40分来自数据范围推导，未作在线提交验证。

#include <bits/stdc++.h>

using namespace std;

using Flight = pair<int, int>;

int simulate(const vector<Flight> &flights, int capacity) {
    priority_queue<int, vector<int>, greater<int>> busy;
    int count = 0;
    for (Flight f : flights) {
        while (!busy.empty() && busy.top() < f.first) busy.pop();
        // 我先归还已离开的廊桥；当前有空位就接航班，不按航班长短重新挑选。
        if (int(busy.size()) < capacity) {
            busy.push(f.second);
            count++;
        }
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<Flight> domestic(m1), international(m2);
    for (Flight &f : domestic) cin >> f.first >> f.second;
    for (Flight &f : international) cin >> f.first >> f.second;
    sort(domestic.begin(), domestic.end());
    sort(international.begin(), international.end());

    int answer = 0;
    for (int x = 0; x <= n; x++) {
        answer = max(answer, simulate(domestic, x) + simulate(international, n - x));
    }
    cout << answer;

    return 0;
}

代码-满分

时间 \(O((n+m_1+m_2)\log (n+m_1+m_2))\)，空间 \(O(n+m_1+m_2)\)。先保存堆顶编号再删除，避免原材料中删除 set 迭代器后继续解引用。

#include <bits/stdc++.h>

using namespace std;

using Flight = pair<int, int>;

vector<int> solve(vector<Flight> flights, int n) {
    sort(flights.begin(), flights.end());
    priority_queue<int, vector<int>, greater<int>> free;
    priority_queue<Flight, vector<Flight>, greater<Flight>> busy;
    for (int i = 1; i <= n; i++) free.push(i);
    vector<int> count(n + 1);
    for (Flight f : flights) {
        while (!busy.empty() && busy.top().first < f.first) {
            free.push(busy.top().second);
            busy.pop();
        }
        if (free.empty()) continue;
        int id = free.top();
        free.pop();
        // 我总用最小空闲编号，这样更大编号接的航班就不会改变前 x 个廊桥的状态。
        count[id]++;
        busy.push({f.second, id});
    }
    for (int i = 1; i <= n; i++) count[i] += count[i - 1];
    return count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<Flight> domestic(m1), international(m2);
    for (Flight &f : domestic) cin >> f.first >> f.second;
    for (Flight &f : international) cin >> f.first >> f.second;
    vector<int> a = solve(domestic, n), b = solve(international, n);

    int answer = 0;
    for (int x = 0; x <= n; x++) answer = max(answer, a[x] + b[n - x]);
    cout << answer;

    return 0;
}

2021T2-P7914括号序列 ¶

把 ? 改成左括号、右括号或星号，使序列符合题目递归规则。
星号段非空且长度不超过 k；空串不是合法序列。
求方案数模 1000000007，特别注意 (*()*) 不合法。

提示1-普通括号栈还够吗

我先判断没有问号的串。括号匹配正确之外，外层括号里面能同时有前导和后缀星号吗？看看 (())，不要只检查括号平衡。

提示2-规模与全问号性质

\(n\le 15\) 的点1～3共15分，可枚举所有 ?，再按规范判断；\(n\le 40\)、100 对应点1～8的40分、点1～13的65分，适合逐步降低区间DP常数。全数据 \(n\le 500\)，\(O(n^3)\) 可行。点14～15全是 ? 共10分，只省掉字符兼容判断，并没有去掉避免重复计数的困难。\(k=1\) 是很短的星号段，但嵌套仍可很深，没有单独分值。

我先在 \(n\le 15\) 枚举问号的三种替换，用题目递归规则核对，争取15分。再把串改成区间状态，但先问“同一串会不会因不同分点被算两次”，用 ()()() 检查。固定第一对最外层括号后，拆分才唯一；星号只加在规则允许的位置。全问号只去掉字符检查，不能省掉这些结构状态，所以我不会仅因字符相同就换成未证明的公式。

提示3-先让最外层拆分唯一

设 \(f[l][r]\) 为合法串数，\(g[l][r]\) 为“整个区间由一对最外层括号包住”的合法串数。合法串可唯一拆成第一个 \(g\)，后接空串、合法串，或“星号段+合法串”。不要按 AB 任意分点，这会重复计算 ()()()。

提示4-另外记录带一侧星号的状态

\(\mathrm{left}[l][r]\) 为非空星号段接合法串，\(\mathrm{right}[l][r]\) 为合法串接非空星号段。\(g\) 的内部只允许空串、纯星号、\(f\)、left、right，不能 left 再加后缀星号。先算短区间，再算 \(g\)、\(f\)、left、right；它们均有明确结构，不混入空串。

提示5-自己动手检查

请先按定义判断 ()、()、(())、(())、(()*)。我用这些最小结构检查状态是否混入空串或同时带两侧星号。

代码-满分

时间 \(O(n^3)\)，空间 \(O(n^2)\)。\(\mathrm{stars}[l][r]\) 表示该区间可全部改成星号且长度 \(\le k\)；空内部仅在长度2的括号对中单独加1。

#include <bits/stdc++.h>

using namespace std;

const int N = 505, MOD = 1000000007;
long long f[N][N], g[N][N], leftStar[N][N], rightStar[N][N];
bool stars[N][N];

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    s = " " + s;
    for (int l = 1; l <= n; l++) {
        bool ok = true;
        for (int r = l; r <= n; r++) {
            ok = ok && (s[r] == '*' || s[r] == '?');
            stars[l][r] = ok && r - l + 1 <= k;
        }
    }

    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (len >= 2 && (s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?')) {
                if (len == 2) g[l][r] = 1;
                else g[l][r] = (stars[l + 1][r - 1] + f[l + 1][r - 1]
                    + leftStar[l + 1][r - 1] + rightStar[l + 1][r - 1]) % MOD;
            }
            f[l][r] = g[l][r];
            for (int p = l + 1; p < r; p++) {
                // 我先固定第一对最外层括号；若任意选分点，()()() 会被多种拆法重复计数。
                f[l][r] = (f[l][r] + g[l][p] * ((f[p + 1][r] + leftStar[p + 1][r]) % MOD)) % MOD;
            }
            for (int p = l; p < r; p++) {
                if (stars[l][p]) leftStar[l][r] = (leftStar[l][r] + f[p + 1][r]) % MOD;
                if (stars[p + 1][r]) rightStar[l][r] = (rightStar[l][r] + f[l][p]) % MOD;
            }
        }
    }
    cout << f[1][n];

    return 0;
}

2021T3-P7915回文 ¶

长度为 2n 的序列中，1～n 各出现两次。
每次从左端或右端取一个数，依次组成回文序列。
输出字典序最小的 L/R 操作串，无解输出 −1。

提示1-第一步的另一半在哪里

我先假设第一步取左端。回文最后一个数必须等于它；这个数只出现两次，最后留下的位置就固定了。

提示2-小规模与相邻消除性质

\(n\le 10\) 的点1～7共28分，可按 \(L\) 优先搜索全部 \(2^{2n}\) 操作串；\(n\le 20\) 时已经不能这样穷举。点18～20共12分可相邻等值消空，说明配对可嵌套，但不等于直接消空顺序就是从两端取数的字典序最小答案。可以把它作为核对配对结构的线索，不能未经证明就跳过构造。全数据 \(\sum n\le 5\times 10^5\)，需线性构造。

我先在 \(n\le 10\) 按 \(L\) 优先枚举操作串，拿28分，并保存字典序最小答案。放大范围时，重复搜索的来源是匹配另一半；每个值只出现两次，第一步一旦确定，其另一份就必须留到最后。我把后半段倒着安排，剩下只需比较四个端点。相邻可消空的性质可帮助画配对，但仍要证明两端取数的操作顺序。

提示3-把最后留下的数看成中心

第一步取的数，其另一份所在位置 \(p\) 必须留到最后。未取区间分成 \(p\) 两侧。接下来回文前半段从外端取，后半段倒着安排，从靠近 \(p\) 的内端取匹配数。四种端点配对只有“两份相同数”才可用，不能把一个位置配给自己。

提示4-先尝试左侧再尝试右侧

每一轮先试左外端，再试右外端。同一个值只有唯一另一份，成功配对时不会有不同的匹配目标；剥去这对后剩余问题同形，所以先选 \(L\) 不会丢掉更好的可行方案。先构造首字符 \(L\) 的解，失败再试 \(R\)；最后剩单个位置取 \(L\)。

提示5-自己动手检查

我会用穷举结果核对四端点构造，特别检查取匹配数时还有没有两个不同位置。最后只有一个位置时，选 \(L\) 才能保持字典序最小。

代码-满分

时间 \(O(\sum n)\)，空间 \(O(n)\)。构造时同时填操作串首尾，而不是把配对顺序直接输出。

#include <bits/stdc++.h>

using namespace std;

string construct(const vector<int> &a, bool firstLeft) {
    int length = int(a.size()) - 1, n = length / 2;
    int first = firstLeft ? 1 : length, match = 0;
    for (int i = 1; i <= length; i++) if (i != first && a[i] == a[first]) match = i;
    int l1 = firstLeft ? 2 : 1, r1 = match - 1;
    int l2 = match + 1, r2 = firstLeft ? length : length - 1;
    string answer(length, 'L');
    answer[0] = firstLeft ? 'L' : 'R';
    answer[length - 1] = 'L';

    for (int i = 1; i < n; i++) {
        char front, back;
        if (l1 < r1 && a[l1] == a[r1]) {
            front = 'L'; back = 'L'; l1++; r1--;
        } else if (l1 <= r1 && l2 <= r2 && a[l1] == a[l2]) {
            front = 'L'; back = 'R'; l1++; l2++;
        } else if (l1 <= r1 && l2 <= r2 && a[r2] == a[r1]) {
            front = 'R'; back = 'L'; r2--; r1--;
        } else if (l2 < r2 && a[r2] == a[l2]) {
            front = 'R'; back = 'R'; r2--; l2++;
        } else return "";
        // 我先把答案画成首尾配对；后半段要倒着安排，不能直接按本轮取数顺序输出。
        answer[i] = front;
        answer[length - 1 - i] = back;
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<int> a(2 * n + 1);
        for (int i = 1; i <= 2 * n; i++) cin >> a[i];
        string answer = construct(a, true);
        if (answer.empty()) answer = construct(a, false);
        cout << (answer.empty() ? "-1" : answer) << '\n';
    }

    return 0;
}

2021T4-P7916交通规划 ¶

给网格点染黑白色。网格外围有颜色固定的附加点，
只计算两端异色的边权，求最小总和。
每次询问独立，射线按题目规定沿外围顺时针编号。

提示1-从两个附加点开始

我先只留两个附加点。同色时全网格同色即可；异色时需要一条分界线把它们隔开，线经过的边权就是代价。

提示2-局部规模决定询问总量

\(n,m\le 5\) 的点1～2共10分可按行状态DP；不能枚举 \(2^{25}\) 种后还忽略询问数。\(k\le 2\) 的点3～5、9～10、13～16共45分，可求一次分界最短路。所有询问的 \(\sum k\le 50\)，比 \(T\le 50\) 更有用：满分也只需至多50次最短路。边权可为0，不能假设分界线必须唯一。

我先抓 \(k\le 2\) 的45分条件：只有一条异色分界线要找，原问题变成对偶图最短路，先把边界射线编号画对。增加附加点后，困难是多条分界线怎样配对；我保留原来的最短路，把端点的组合另交给区间DP。这里真正限制工作量的是所有询问的 \(\sum k\le 50\)，不是单独看询问个数。

提示3-把格子空隙作为点

分界线在格子之间走。每个内格子建一个对偶点，跨过原边的代价是该边权。附加点射线把外面分成 \(k\) 个扇区，也各建点；附加边连接相邻两个扇区。原网格边位于边界时，连接内格子与对应外扇区。相邻附加点异色的扇区是分界线端点。

提示4-多条分界线做不交叉配对

异色变化次数一定为偶数。最优分界线把这些端点两两连接；内部不会凭空终止，多余闭环可删。相交路径可交换尾段而不增加费用，所以存在不交叉配对。先算端点两两最短路，再用区间DP配对：\(l\) 连 \(j\) 后，内部 \(l+1\sim j-1\) 和右侧 \(j+1\sim r\) 独立。同色扇区也必须建点，最短路可能经过它。

提示5-自己动手检查

我会在小网格枚举所有染色，核对对偶图答案。附加点全同色应得0；首尾扇区相邻，不能漏掉环绕边界。

代码-满分

时间 \(O(\sum k\cdot nm \log (nm)+\sum k^3+Tnm)\)，空间 \(O(nm+k^2)\)。下面 ray 表示原边落在第 ray 与 ray+1 条射线之间；二分找到所属外扇区，处理首尾绕回。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 4000000000000000000LL;
struct Edge { int to, weight; };
struct Border { int inside, ray, weight; };
struct Extra { int ray, weight, color; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, tests;
    cin >> n >> m >> tests;
    // 我把分界线能经过的格子空隙建成点，跨过一条原边就支付它的权值。
    int cells = (n - 1) * (m - 1);
    auto cell = [&](int r, int c) { return (r - 1) * (m - 1) + c - 1; };
    vector<vector<Edge>> base(cells);
    vector<Border> border;
    auto connectBase = [&](int u, int v, int w) {
        base[u].push_back({v, w});
        base[v].push_back({u, w});
    };
    for (int r = 1; r < n; r++) {
        for (int c = 1; c <= m; c++) {
            int w;
            cin >> w;
            if (c == 1) border.push_back({cell(r, 1), 2 * m + n + n - r, w});
            else if (c == m) border.push_back({cell(r, m - 1), m + r, w});
            else connectBase(cell(r, c - 1), cell(r, c), w);
        }
    }
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c < m; c++) {
            int w;
            cin >> w;
            if (r == 1) border.push_back({cell(1, c), c, w});
            else if (r == n) border.push_back({cell(n - 1, c), m + n + m - c, w});
            else connectBase(cell(r - 1, c), cell(r, c), w);
        }
    }

    while (tests--) {
        int k;
        cin >> k;
        vector<Extra> extra(k);
        for (Extra &e : extra) cin >> e.weight >> e.ray >> e.color;
        sort(extra.begin(), extra.end(), [](Extra a, Extra b) { return a.ray < b.ray; });
        vector<int> rays;
        for (Extra e : extra) rays.push_back(e.ray);
        vector<vector<Edge>> graph = base;
        graph.resize(cells + k);
        auto connect = [&](int u, int v, int w) {
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        };
        for (Border b : border) {
            int sector = int(upper_bound(rays.begin(), rays.end(), b.ray) - rays.begin()) - 1;
            if (sector < 0) sector = k - 1;
            connect(b.inside, cells + sector, b.weight);
        }
        vector<int> ends;
        for (int i = 0; i < k; i++) {
            connect(cells + (i + k - 1) % k, cells + i, extra[i].weight);
            if (extra[i].color != extra[(i + 1) % k].color) ends.push_back(cells + i);
        }
        int count = ends.size();
        vector<vector<long long>> distance(count, vector<long long>(count));
        for (int s = 0; s < count; s++) {
            vector<long long> d(graph.size(), INF);
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> queue;
            d[ends[s]] = 0;
            queue.push({0, ends[s]});
            while (!queue.empty()) {
                auto current = queue.top();
                queue.pop();
                int u = current.second;
                if (current.first != d[u]) continue;
                for (Edge e : graph[u]) if (d[e.to] > d[u] + e.weight) {
                    d[e.to] = d[u] + e.weight;
                    queue.push({d[e.to], e.to});
                }
            }
            for (int t = 0; t < count; t++) distance[s][t] = d[ends[t]];
        }
        vector<vector<long long>> dp(count, vector<long long>(count));
        for (int len = 2; len <= count; len += 2) {
            for (int l = 0; l + len <= count; l++) {
                int r = l + len - 1;
                dp[l][r] = INF;
                for (int j = l + 1; j <= r; j += 2) {
                    long long value = distance[l][j];
                    if (j > l + 1) value += dp[l + 1][j - 1];
                    if (j < r) value += dp[j + 1][r];
                    dp[l][r] = min(dp[l][r], value);
                }
            }
        }
        cout << (count == 0 ? 0 : dp[0][count - 1]) << '\n';
    }

    return 0;
}

2022T1-P8817假期计划 ¶

从家 1 出发，依次游玩四个互不相同的景点，再回家。
每段最多转车 k 次，即经过至多 k+1 条边。
转车途中可以重复经过任意点，最大化四个景点的分数和。

提示1-先分清游玩与经过

我先尝试四重枚举景点。检查一段行程时，中途经过另一个景点算不算已经游玩？题目允许转车经过任何点，不能用不重复的整条路径限制它。

提示2-k=0与小图

\(n\le 20\) 的点1～8共40分，可以先求可达性，再枚举四景点。\(k=0\) 的点1～3、9～11、15～17共45分，每段必须直接相邻，不用求最短路；但大图的四重枚举仍很慢。全数据 \(n\le 2500\)、\(m\le 10000\)，所有起点BFS约 \(O(n(n+m))\) 可行。分数 \(\le10^{18}\)，四数之和 \(\le4\times10^{18}\)，用 long long。

我先在 \(n\le 20\) 求每两点能否到达，再枚举四景点，拿40分。\(k=0\) 时可达性就是是否有边，省掉最短路，但四重枚举仍未优化。要提高分数，我固定中间两个点，看左右最优候选为何不能直接各取第一名：它们可能撞到同一个点。最多排除两个候选这个特点，让我把每侧候选压到前三名。

提示3-先固定中间两站

固定 \(B\)、\(C\) 后，左侧 \(A\) 必须从家可达且能到 \(B\)，右侧 \(D\) 同理。左右各自最优，只被“景点互不相同”打断。对 \(B\) 记录满足两段可达的候选 \(A\)，按分数留前几名。

提示4-为什么只留前三名

在 \(B\) 的候选中，最多要排除 \(C\) 和选定的 \(D\) 两个点，前三名总有一个不被排除；对 \(C\) 的候选同理。保留前三个，枚举 \(B\)、\(C\) 后最多检查9对，仍可得到某组最优四景点。候选本身已排除家和对应中间点。

提示5-自己动手检查

我会设计左右第一名恰是同一点的例子，检查是否能改用第二、第三名。中转路过已游玩的景点仍合法，不要误删可达关系。

代码-满分

时间 \(O(n(n+m)+n^2)\)，空间 \(O(n^2+m)\)。BFS距离只用于判断距离是否 \(\le k+1\)；存布尔可达矩阵即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2505;
bool reachable[N][N];
long long score[N];
int best[N][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) cin >> score[i];
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int s = 1; s <= n; s++) {
        vector<int> distance(n + 1, -1), queue = {s};
        distance[s] = 0;
        for (int head = 0; head < int(queue.size()); head++) {
            int u = queue[head];
            reachable[s][u] = true;
            if (distance[u] == k + 1) continue;
            for (int v : graph[u]) if (distance[v] == -1) {
                distance[v] = distance[u] + 1;
                queue.push_back(v);
            }
        }
    }
    for (int b = 2; b <= n; b++) {
        for (int a = 2; a <= n; a++) if (a != b && reachable[1][a] && reachable[a][b]) {
            int candidate = a;
            for (int j = 0; j < 3; j++) {
                if (score[candidate] > score[best[b][j]]) swap(candidate, best[b][j]);
            }
        }
    }

    long long answer = 0;
    for (int b = 2; b <= n; b++) {
        for (int c = 2; c <= n; c++) if (b != c && reachable[b][c]) {
            for (int a : best[b]) for (int d : best[c]) {
                // 我先留每侧前三名，再逐对排除重复点；每侧最优不等于两侧能同时选。
                if (a && d && a != c && d != b && a != d) {
                    answer = max(answer, score[a] + score[b] + score[c] + score[d]);
                }
            }
        }
    }
    cout << answer;

    return 0;
}

2022T2-P8818策略游戏 ¶

每次给定 A、B 的两个区间。小 L 先选 A 中一个数，
小 Q 看见选择后选 B 中一个数；得分为两数乘积。
L 想最大化、Q 想最小化，输出双方最优时的得分。

提示1-固定先手后再看后手

我先固定一个 \(a\)。\(a\) 为正时，\(Q\) 会选 \(B\) 里的最小值；\(a\) 为负时，还选最小值吗？用 \((-2)\times(-3)\) 与 \((-2)\times4\) 对比。

提示2-特殊性质真的简化了符号

全为正数的点1～2、6～8、13～15共40分，答案就是 \(\max(A)\times\min(B)\)，区间最值即可。一个区间只有单点的点1、3、6、9～10、13、16～17共40分：若 \(A\) 单点直接求最坏乘积，若 \(B\) 单点按其正负选 \(A\) 最值。两性质重叠15分，合起来65分。\(n,m,q\le 200\) 的点1～5共25分可逐对枚举；全数据 \(n,m,q\le10^5\)，只能预处理区间信息。

我先做全为正数的40分数据，只需区间最大值乘区间最小值，熟悉的区间最值算法就够了。出现负数后，我固定先手选值，用正、负、零三种例子重新判断后手会选哪端。优化不再是增加枚举速度，而是缩小先手候选：每个符号区间上的最坏得分都是一次函数，只需保留该类两端。

提示3-先手只需要几种候选

\(B\) 的最小、最大值足够计算任意 \(a\) 的最坏得分 \(\min(aB_{\min},aB_{\max})\)。对 \(a\ge 0\)、\(a<0\) 分别看，这是各自区间上的一次函数，因此每类只需最小和最大值；0自然放到非负类。不能只保留 \(A\) 的整体最值，接近0的数有时反而最优。

提示4-缺失符号不能拿哨兵相乘

我用线段树维护整体最小、最大以及两类各自的最值。缺失的一类用标记值跳过，不让无穷大参与乘法。乘积最大绝对值 \(10^{18}\)，用 long long。

提示5-自己动手检查

我会测试 \(A\) 全负、\(B\) 跨零、\(A\) 含0，以及某种符号完全缺失。先手接近0有时更优，不能只用整个 \(A\) 区间的最大与最小。

代码-满分

时间 \(O(n+m+q \log (n+m))\)，空间 \(O(n+m)\)。静态区间也可使用稀疏表；这里复用同一个线段树写法。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 4000000000000000000LL;
struct Node {
    long long low = INF, high = -INF;
    long long positiveLow = INF, positiveHigh = -INF;
    long long negativeLow = INF, negativeHigh = -INF;
};

Node mergeNode(Node a, Node b) {
    return {min(a.low, b.low), max(a.high, b.high),
        min(a.positiveLow, b.positiveLow), max(a.positiveHigh, b.positiveHigh),
        min(a.negativeLow, b.negativeLow), max(a.negativeHigh, b.negativeHigh)};
}

struct SegmentTree {
    int size = 1;
    vector<Node> tree;
    SegmentTree(const vector<long long> &a) {
        while (size < int(a.size())) size *= 2;
        tree.resize(size * 2);
        for (int i = 0; i < int(a.size()); i++) {
            Node &t = tree[size + i];
            t.low = t.high = a[i];
            if (a[i] >= 0) t.positiveLow = t.positiveHigh = a[i];
            else t.negativeLow = t.negativeHigh = a[i];
        }
        for (int i = size - 1; i > 0; i--) tree[i] = mergeNode(tree[i * 2], tree[i * 2 + 1]);
    }
    Node query(int l, int r) {
        Node answer;
        for (l += size, r += size; l <= r; l /= 2, r /= 2) {
            if (l % 2 == 1) { answer = mergeNode(answer, tree[l]); l++; }
            if (r % 2 == 0) { answer = mergeNode(answer, tree[r]); r--; }
        }
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<long long> a(n), b(m);
    for (long long &x : a) cin >> x;
    for (long long &x : b) cin >> x;
    SegmentTree first(a), second(b);
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        Node x = first.query(l1 - 1, r1 - 1), y = second.query(l2 - 1, r2 - 1);
        long long answer = -INF;
        for (long long value : {x.positiveLow, x.positiveHigh, x.negativeLow, x.negativeHigh}) {
            if (value == INF || value == -INF) continue;
            // 我固定先手候选，先让后手取最小乘积；再比较先手能保证的最大分数。
            answer = max(answer, min(value * y.low, value * y.high));
        }
        cout << answer << '\n';
    }

    return 0;
}

2022T3-P8819星战 ¶

有向图支持删除或恢复一条边，或某点的全部入边。
每次操作后，判断是否所有点恰有一条可用出边，
且从任意点都能一直沿边走下去。

提示1-两个条件是否独立

我先只检查每点出度为1。在有限个点上一直沿唯一出边走，会不会最终重复经过某个点？因此不需要另外找环。

提示2-操作改的是入边，要求看的是出边

\(n\le 1000\)、\(m\le 10000\)、\(q\le 1000\) 的点1～8共40分可逐条修改入边，维护出度。没有整点操作的点9～10另有10分，单边改动 \(O(1)\)，两类组合覆盖50分。没有恢复整点入边的点11～12可把连续的整点删除摊到单边删除或恢复上，但单边仍可能来回切换，不是“每条边只处理一次”。一般数据 \(n,m,q\le 5\times 10^5\)，反复扫描大入边表会慢。

我先维护每个点的出度及“出度不是1”的点数，单边操作只改一个点；小规模和无整点操作可拿50分。整点删除慢在哪里？它一次改变许多起点的出度，而输入按终点给操作。我先确认模拟的瓶颈，再用可加权值把一组边的贡献整体替换。这里采用随机化加速，必须把碰撞风险与确定性部分分的保证区分开。

提示3-把出度向量变成可加的信息

我给每个起点随机权值 \(h_u\)，一条可用边 \(u\to v\) 贡献 \(h_u\)。正确状态的总和应为 \(\sum_{u=1}^{n}h_u\)。对每个终点维护当前入边贡献和与初始贡献和：整点删除改为0，整点恢复改为初始和，都可 \(O(1)\) 更新。单边按其起点权值加减。

提示4-随机化的边界必须讲清

权值和相等只是概率判断，不是数学上的充要条件。使用两组独立64位权值，并额外检查可用边数为 \(n\)，可以大幅降低误判概率，但不能宣称绝对不会碰撞。需要确定性结果时用前面的出度维护方法，代价是一般数据整点操作可能超时。下面的完整范围方案明确采用随机化；不将它当作确定性证明。

提示5-自己动手检查

我会先用确定性版本核对随机化版本的操作结果。整点删除后再恢复、单边删除后整点恢复，都要检查贡献有没有重复加减。

代码-50分

确定性模拟：覆盖小规模点1～8与无整点操作的点9～10，共50分。整点操作时间等于该点入度，最坏 \(O(mq)\)，一般大数据不保证时限。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> incoming(n + 1);
    vector<int> degree(n + 1);
    vector<bool> active(m, true);
    map<pair<int, int>, int> id;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        id[{u, v}] = i;
        incoming[v].push_back({u, i});
        degree[u]++;
    }
    int bad = 0;
    for (int u = 1; u <= n; u++) if (degree[u] != 1) bad++;
    // 我只在边的状态真正变化时修改出度，避免重复删除或恢复影响计数。
    auto change = [&](int u, int edge, bool want) {
        if (active[edge] == want) return;
        if (degree[u] != 1) bad--;
        degree[u] += want ? 1 : -1;
        if (degree[u] != 1) bad++;
        active[edge] = want;
    };
    int q;
    cin >> q;
    while (q--) {
        int type, u, v;
        cin >> type >> u;
        if (type == 1 || type == 3) {
            cin >> v;
            change(u, id[{u, v}], type == 3);
        } else {
            for (auto edge : incoming[u]) change(edge.first, edge.second, type == 4);
        }
        cout << (bad == 0 ? "YES" : "NO") << '\n';
    }

    return 0;
}

代码-满分

随机化算法，支持完整输入范围；时间 \(O(n+m+q)\)，空间 \(O(n)\)。双权值在模 \(2^{64}\) 下自然溢出，无符号运算是定义良好的；判YES存在极小碰撞风险，判NO不会漏掉正确状态。本地对拍不能替代这一概率说明。

#include <bits/stdc++.h>

using namespace std;

using ULL = unsigned long long;
struct Sum {
    ULL first = 0, second = 0;
    long long edges = 0;
};
Sum operator+(Sum a, Sum b) { return {a.first + b.first, a.second + b.second, a.edges + b.edges}; }
Sum operator-(Sum a, Sum b) { return {a.first - b.first, a.second - b.second, a.edges - b.edges}; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    mt19937_64 random(chrono::steady_clock::now().time_since_epoch().count());
    vector<Sum> weight(n + 1), initial(n + 1), current(n + 1);
    Sum target, total;
    for (int u = 1; u <= n; u++) {
        weight[u] = {random(), random(), 1};
        target = target + weight[u];
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        initial[v] = initial[v] + weight[u];
        total = total + weight[u];
    }
    current = initial;
    int q;
    cin >> q;
    while (q--) {
        int type, u, v;
        cin >> type >> u;
        if (type == 1 || type == 3) {
            cin >> v;
            if (type == 1) {
                current[v] = current[v] - weight[u];
                total = total - weight[u];
            } else {
                current[v] = current[v] + weight[u];
                total = total + weight[u];
            }
        } else {
            // 我先减去这组当前贡献，再加目标贡献；这是省掉大入边表扫描的地方。
            total = total - current[u];
            current[u] = type == 2 ? Sum{} : initial[u];
            total = total + current[u];
        }
        bool ok = total.edges == n && total.first == target.first && total.second == target.second;
        cout << (ok ? "YES" : "NO") << '\n';
    }

    return 0;
}

2022T4-P8820数据传输 ¶

树上每个点有正的处理费用。两点距离不超过 k 时可以直接传输，
传输经过的每个主机都要付费，包括起点、终点。
对多次起终点询问求最小费用，1≤k≤3。

提示1-k=1先变成什么

我先把 \(k\) 设为1。只能沿原树边走，树上唯一路径的点权和就是答案，怎样用根路径和及LCA快速得到它？

提示2-部分分与随机树性质

\(k=1\) 的点6～7、12～13共16分，LCA路径和即可。\(n\le 2000\) 的点1～11共44分，可以把距离 \(\le k\) 的点连边，对询问跑最短路；注意星形树会产生 \(O(n^2)\) 条边。特殊性质是随机生成父亲，并不保证树高短或度数小，不能当作链或平衡树。全数据 \(n,Q\le 2\times 10^5\)，费用 \(\le10^9\)，不能每次遍历全图。

我先锁定 \(k=1\) 的16分数据：不能跳点，LCA加根路径和就是熟悉的树上路径查询。小图也可以把距离 \(\le k\) 的点连边跑最短路，作为44分范围的起点。放大后不能开这张稠密图，我先尝试路径上DP；\(k=3\) 的旁支低价点反例提醒我补充状态。最后才用小矩阵和重链剖分合并已经写清楚的转移，而不是先套模板。

提示3-k=3不能只看原路径

\(k=2\) 时，离开路径再回来不会比直接跨过去更好；\(k=3\) 时可能选路径旁边的低价点。例如路径费用1、100、100、100、100、1，在第二个100旁接费用1的点，起终点都能经它跳3步，总费3。只做链上“最近 \(k\) 项”DP会漏解。偏离路径两层以上的点可以投影、删去或被一次直接跳跃替代，正费用保证不用这些绕路。

提示4-用三个状态记短距离信息

我按起点到终点的顺序给路径编号。\(X_i\) 表示以第 \(i\) 个路径点为末次主机的最小费用；\(N_i\) 表示以它的某个邻点为末次主机的最小费用，\(b_i\) 是该点最小邻点费用。

当 \(k=3\) 时，我把信息压成三个状态：\(Y_i=\min(X_{i-1},N_i)\)，\(Z_i=Y_{i-1}\)。转移为：

\[ \begin{aligned} X_i&=\min(X_{i-1},Y_{i-1},Z_{i-1})+v_i,\\ Y_i&=\min(X_{i-1},Y_{i-1}+b_i),\\ Z_i&=Y_{i-1}. \end{aligned} \]

我理解 \(Y_i\) 的第一项时，会检查直接跨过邻点是否可行：省掉一次不必要的正费用，同时保留下一步需要的距离信息。\(Z_i\) 再保存上一轮的 \(Y\)，就能表示再多跨一步。

提示5-把转移连乘并注意方向

我先把相邻两次转移手动合并，发现只用“加费用、取最小”。于是定义小矩阵乘法：

\[ C_{i,j}=\min_t(A_{i,t}+B_{t,j}). \]

这种乘法满足结合律，转移顺序仍不能倒。重链剖分把路径拆成区间，线段树同时存正向、反向乘积。起点状态是 \((v_s,\infty,\infty)\)，只处理其余路径点，最后取 \(X_t\)。我用“起终点相同”的情况检查端点费用没有漏算或重算。

提示6-自己动手检查

先令起点等于终点，再测一条高低费用交替的链。\(k=3\) 时在路径旁加一个低价点，检查算法是否允许从它中转。

代码-16分

仅用于 \(k=1\)，覆盖点6～7、12～13，共16分。正费用保证绕路不会更便宜，直接计算树上唯一路径和。\(\mathrm{sum}[u]\) 包含根到 \(u\) 的全部点权，答案为 \(\mathrm{sum}[u]+\mathrm{sum}[v]-2\mathrm{sum}[\operatorname{LCA}(u,v)]+v_{\operatorname{LCA}(u,v)}\)。时间 \(O((n+q)\log n)\)，空间 \(O(n \log n)\)。\(k\ge 2\) 时可以跳过高价点，路径和不再是最小费用。

#include <bits/stdc++.h>

using namespace std;

const int N = 200005, LOG = 20;
int ancestor[N][LOG], depth[N];
long long value[N], sum[N];
vector<int> graph[N];

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int difference = depth[u] - depth[v];
    for (int j = 0; j < LOG; j++) if ((difference >> j) & 1) u = ancestor[u][j];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) {
        if (ancestor[u][j] != ancestor[v][j]) {
            u = ancestor[u][j];
            v = ancestor[v][j];
        }
    }
    return ancestor[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q, k;
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) cin >> value[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> order = {1};
    sum[1] = value[1];
    for (int head = 0; head < n; head++) {
        int u = order[head];
        for (int v : graph[u]) if (v != ancestor[u][0]) {
            ancestor[v][0] = u;
            depth[v] = depth[u] + 1;
            sum[v] = sum[u] + value[v];
            for (int j = 1; j < LOG; j++) ancestor[v][j] = ancestor[ancestor[v][j - 1]][j - 1];
            order.push_back(v);
        }
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        int w = lca(u, v);
        // 我画两条根路径核对重复部分；公共祖先被减了两次，需要补回一次费用。
        cout << sum[u] + sum[v] - 2 * sum[w] + value[w] << '\n';
    }

    return 0;
}

代码-满分

矩阵维数为 \(k\le 3\)。预处理 \(O(nk^3)\)，查询 \(O(k^3\log ^2n)\)，空间 \(O(nk^2)\)。重链剖分的两次遍历用迭代顺序，矩阵与区间递归深度仅 \(O(\log n)\)。邻点包括所有相邻点，不只儿子。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 4000000000000000000LL;
int dimension;
struct Matrix {
    long long a[3][3];
    Matrix(bool identity = false) {
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) a[i][j] = identity && i == j ? 0 : INF;
    }
};
Matrix multiply(const Matrix &a, const Matrix &b) {
    Matrix c;
    for (int i = 0; i < dimension; i++) for (int t = 0; t < dimension; t++) {
        for (int j = 0; j < dimension; j++) c.a[i][j] = min(c.a[i][j], a.a[i][t] + b.a[t][j]);
    }
    return c;
}
struct Node { Matrix forward, backward; };
Node mergeNode(const Node &a, const Node &b) {
    return {multiply(a.forward, b.forward), multiply(b.backward, a.backward)};
}
struct SegmentTree {
    int size = 1;
    vector<Node> tree;
    SegmentTree(const vector<Matrix> &a) {
        while (size < int(a.size())) size *= 2;
        tree.assign(size * 2, {Matrix(true), Matrix(true)});
        for (int i = 0; i < int(a.size()); i++) tree[size + i] = {a[i], a[i]};
        for (int i = size - 1; i > 0; i--) tree[i] = mergeNode(tree[i * 2], tree[i * 2 + 1]);
    }
    Matrix query(int l, int r, bool reverse) {
        Node left{Matrix(true), Matrix(true)}, right = left;
        for (l += size, r += size; l <= r; l /= 2, r /= 2) {
            if (l % 2 == 1) { left = mergeNode(left, tree[l]); l++; }
            if (r % 2 == 0) { right = mergeNode(tree[r], right); r--; }
        }
        Node result = mergeNode(left, right);
        return reverse ? result.backward : result.forward;
    }
};
struct Piece { int left, right; bool reverse; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q >> dimension;
    vector<long long> value(n + 1), neighbor(n + 1, INF);
    for (int u = 1; u <= n; u++) cin >> value[u];
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        neighbor[u] = min(neighbor[u], value[v]);
        neighbor[v] = min(neighbor[v], value[u]);
    }
    vector<int> parent(n + 1), depth(n + 1), size(n + 1, 1), heavy(n + 1), top(n + 1), dfn(n + 1), order = {1};
    size[0] = 0;
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (int v : graph[u]) if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            order.push_back(v);
        }
    }
    for (int i = n - 1; i > 0; i--) {
        int u = order[i], p = parent[u];
        size[p] += size[u];
        if (size[u] > size[heavy[p]]) heavy[p] = u;
    }
    vector<pair<int, int>> stack = {{1, 1}};
    vector<Matrix> transitions(n);
    int timer = 0;
    while (!stack.empty()) {
        auto item = stack.back();
        stack.pop_back();
        for (int u = item.first; u != 0; u = heavy[u]) {
            top[u] = item.second;
            dfn[u] = timer;
            Matrix a;
            for (int j = 0; j < dimension; j++) a.a[j][0] = value[u];
            if (dimension >= 2) a.a[0][1] = 0;
            if (dimension == 3) { a.a[1][1] = neighbor[u]; a.a[1][2] = 0; }
            transitions[timer] = a;
            timer++;
            for (int v : graph[u]) if (parent[v] == u && v != heavy[u]) stack.push_back({v, v});
        }
    }
    SegmentTree tree(transitions);
    while (q--) {
        int s, t;
        cin >> s >> t;
        int u = s, v = t;
        vector<Piece> left, right;
        while (top[u] != top[v]) {
            if (depth[top[u]] >= depth[top[v]]) {
                left.push_back({dfn[top[u]], dfn[u], true});
                u = parent[top[u]];
            } else {
                right.push_back({dfn[top[v]], dfn[v], false});
                v = parent[top[v]];
            }
        }
        if (depth[u] >= depth[v]) left.push_back({dfn[v], dfn[u], true});
        else right.push_back({dfn[u], dfn[v], false});
        reverse(right.begin(), right.end());
        left.insert(left.end(), right.begin(), right.end());
        // 我先让状态包含起点费用，再去掉起点那次转移，避免同一个端点收费两次。
        if (left[0].reverse) left[0].right--;
        else left[0].left++;
        array<long long, 3> dp = {value[s], INF, INF};
        for (Piece p : left) if (p.left <= p.right) {
            Matrix a = tree.query(p.left, p.right, p.reverse);
            array<long long, 3> next = {INF, INF, INF};
            for (int i = 0; i < dimension; i++) for (int j = 0; j < dimension; j++) next[j] = min(next[j], dp[i] + a.a[i][j]);
            dp = next;
        }
        cout << dp[0] << '\n';
    }

    return 0;
}

2023T1-P9752密码锁 ¶

五个拨圈各有 0～9。正确密码转动一个拨圈，
或把两个相邻拨圈同时转动相同幅度，得到记录中的状态。
记录状态都不等于正确密码，求能解释全部记录的密码数。

提示1-从记录倒着转

我先用第一条记录猜密码。操作是可逆的，能否只枚举从这条记录转一次得到的密码，而不是检查全部十万个密码？

提示2-值域与特殊性质

全数据 \(n\le 8\)，密码只有 \(10^5\) 种，直接枚举检查也可行。\(n=1\) 的点1～3共30分，\(5\times9+4\times9=81\) 种候选，互不重复。性质 \(A\) 的点6～8另有30分，正确密码都能只改一个拨圈得到记录，去掉了相邻双圈的判断；不能把 \(A\) 理解为记录中所有密码只差同一个位置。通用枚举已足够，不必另写重复代码。

我先做 \(n=1\) 的30分条件，倒着转动一次，列出81个可能密码。多条记录并没有增加密码的位数，困难只变成“一个候选能否解释全部记录”。我可以先枚举十万个密码逐条检查，再优化为每条记录的81个候选取交集。性质 \(A\) 省掉双圈操作，但通用枚举已经足够快，不需要为它另写一份相同代码。

提示3-不要允许不转动

幅度按模10计，枚举1～9，不能枚举0，否则会把记录本身当正确密码。两个相邻位置的增量必须相同，不能独立选择。对每条记录生成候选集合，再统计交集；重复记录不改变交集。

提示4-自己动手检查

我会检查前导0、重复记录和9转到0。尝试把双圈分别转不同幅度，确认这种候选必须被排除。

代码-满分

每条记录生成81个候选。时间 \(O(10^5+81n)\)，空间 \(O(10^5)\)，前导0通过五个数字保留。

#include <bits/stdc++.h>

using namespace std;

const int LIMIT = 100000;
int countCode[LIMIT];

int encode(const array<int, 5> &a) {
    int value = 0;
    for (int x : a) value = value * 10 + x;
    return value;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        array<int, 5> a;
        for (int &x : a) cin >> x;
        set<int> candidates;
        for (int p = 0; p < 5; p++) {
            for (int d = 1; d <= 9; d++) {
                auto b = a;
                b[p] = (b[p] + d) % 10;
                candidates.insert(encode(b));
                if (p < 4) {
                    // 我先检查操作条件是同时转相同幅度，因此第二个拨圈沿用 d，不能另枚举幅度。
                    b[p + 1] = (b[p + 1] + d) % 10;
                    candidates.insert(encode(b));
                }
            }
        }
        for (int code : candidates) countCode[code]++;
    }
    int answer = 0;
    for (int code = 0; code < LIMIT; code++) if (countCode[code] == n) answer++;
    cout << answer;

    return 0;
}

2023T2-P9753消消乐 ¶

字符串只含小写字母，可反复删去两个相邻相同字符。
统计能被删成空串的非空连续子串数量。

提示1-先固定一个左端点

我先枚举左端点，向右扫描，用栈删除相邻相同字符。每次栈变空，就找到了一个可消除子串。先把 \(O(n^2)\) 的方法写清楚。

提示2-二字符和随机数据

\(n\le 8000\) 的点1～10共50分可增量维护每个左端点的栈。随机字符串点11～12共10分，并不保证栈短，随机不能代替复杂度证明。仅 \(a\)、\(b\) 的点13～14共10分：消完后的串一定交替，状态可由起始字符与长度描述，甚至映射成整数线上的位置；这确实省掉了保存整串。一般 \(n\le 2\times 10^6\)，答案约 \(n^2/2\)，必须用 long long。

我先按左端点枚举，用栈增量消除，完成 \(n\le 8000\) 的50分版本。看到只含 \(a\)、\(b\)，我画出约简后的交替串，把状态放到一条数轴上，可单独拿10分。推广到26种字符后，一条线放不下所有状态，但“相同前缀状态之间可消空”的判断仍可保留；我用状态树给完整栈编号，优化的是重复表示和重复扫描。

提示3-两个前缀什么时候等价

每个前缀消除后的栈是唯一的：相邻消除规则即使顺序不同，重叠只可能是xxx，删左右任一对都剩 \(x\)；继续消除得到相同结果。两个前缀的消除栈相同，当且仅当夹在中间的子串能消空。这也可从“每个字符是自己的逆”的拼接、消除规则证明。

提示4-栈状态不能只记长度

ab和ac长度相同，内容不同。我用一棵状态树保存所有不同的消除栈：节点表示完整栈，父亲表示弹出栈顶；压入字符时按“父节点编号、字符”找唯一子节点。相同状态共享编号，按编号统计前缀次数。普通哈希表存精确整数键，碰撞会比较键，不是用字符串哈希猜相等。

提示5-自己动手检查

我会比较ab与ac，提醒自己长度相同不等于状态相同。先计空前缀，再查询旧次数、增加新次数，避免把空子串算进答案。

代码-10分

仅用于只含 \(a\)、\(b\) 的点13～14，共10分。消除相邻相同字符后的串必然交替；可以把 \(a\)、\(b\) 看作数轴上交替的两类边。从状态 \(x\) 出发，\(a\) 在偶数位置向右、奇数位置向左，\(b\) 反过来。同一字符连续走两次会原路返回；约简后的非空交替串不会回到原位置。因此两个前缀状态相等当且仅当中间可消空。记录状态出现次数，时间、空间 \(O(n)\)。第三种字符出现后，一条数轴不能再表示所有约简状态，需要满分代码中的栈状态。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;
    vector<int> count(2 * n + 1);
    int state = 0;
    long long answer = 0;
    count[n] = 1;
    for (char c : s) {
        bool even = state % 2 == 0;
        // 我用 aa、bb 核对数轴方向：连续相同字符必须原路返回，才能对应消除。
        if ((c == 'a') == even) state++;
        else state--;
        answer += count[state + n];
        count[state + n]++;
    }
    cout << answer;

    return 0;
}

代码-50分

适用于 \(n\le 8000\)，覆盖点1～10。时间 \(O(n^2)\)，空间 \(O(n)\)。每个左端点只清空一次栈，并在延长区间时继续更新。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;
    long long answer = 0;
    vector<char> stack;
    // 我固定左端点后持续更新同一个栈，省掉重新检查每个子串的重复工作。
    for (int l = 0; l < n; l++) {
        stack.clear();
        for (int r = l; r < n; r++) {
            if (!stack.empty() && stack.back() == s[r]) stack.pop_back();
            else stack.push_back(s[r]);
            if (stack.empty()) answer++;
        }
    }
    cout << answer;

    return 0;
}

代码-满分

哈希表期望时间 \(O(n)\)，空间 \(O(n)\)，状态相等的判断是精确的。先计入空前缀；读到一个状态时把此前次数加到答案，再增加次数，确保子串非空。

#include <bits/stdc++.h>

using namespace std;

struct State { int parent; char top; long long count; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;
    vector<State> states;
    states.reserve(n + 1);
    states.push_back({0, 0, 1});
    unordered_map<long long, int> child;
    child.reserve(n);
    int current = 0;
    long long answer = 0;
    for (char c : s) {
        if (current != 0 && states[current].top == c) current = states[current].parent;
        else {
            long long key = 26LL * current + c - 'a';
            auto it = child.find(key);
            if (it == child.end()) {
                int id = states.size();
                child[key] = id;
                states.push_back({current, c, 0});
                current = id;
            } else current = it->second;
        }
        // 我用 ab 和 ac 提醒自己：长度相同仍是不同栈，必须用完整状态的编号计数。
        answer += states[current].count;
        states[current].count++;
    }
    cout << answer;

    return 0;
}

2023T3-P9754结构体 ¶

模拟基本类型与结构体的内存布局。
支持定义类型、定义变量、查询点号成员地址、反查地址对应的基本成员。
成员之间及结构体末尾都要对齐，落在空隙中输出 ERR。

提示1-地址为什么不能直接累加

我先画 short、int、short 的布局。int前需要补空隙，最后的short后是否也要补？类型大小与实际成员字节总和不是同一个量。

提示2-不要被地址值域吓住

\(n,k\le 100\)，但地址可到 \(10^{18}\)，不能逐字节开数组；局部规模是成员总数和嵌套深度。性质 \(A\) 无结构体定义，点1～3共15分，只需排基本变量；\(B\) 只有一个结构体定义，点4～8共25分，没有结构体嵌套；\(C\) 成员均为基本类型，点9～13共25分，也可一层查找。\(D\) 只有long，点1、4～5、9～10、14～16共40分，所有大小、偏移均是8的倍数，省掉对齐空隙，但嵌套仍需处理。各性质重叠，不能相加。

我先选性质 \(A\) 的15分数据，只排列四种基本类型变量，把向上对齐函数写对。然后加一层结构体，先完成 \(B\) 或 \(C\) 的范围；观察嵌套结构体与普通成员的共同点：外层只需要内层的大小和对齐要求。这样我把一层扫描改成逐层查询，而不是按巨大地址空间逐字节模拟。\(D\) 去掉空隙，但不会去掉嵌套层次。

提示3-类型保存相对地址

我对每种类型保存大小、对齐要求及成员列表。成员先把当前偏移向上对齐到它的要求，再记录偏移并加上大小；全部成员结束后再按最大对齐要求补齐。定义变量才在全局地址上分配空间，定义类型不占空间。

提示4-两个查询沿同一棵类型树

点号查询从变量开始逐层找成员，累加偏移。反查地址先找包含它的变量，再逐层找包含当前偏移的成员；若某层没有成员覆盖，就是空隙。只有到基本类型才输出名字，不能把结构体尾部填充误认为某个成员。

提示5-自己动手检查

我先画一个byte后接int的空隙，再画结构体末尾的空隙。反查这些地址都应输出ERR；同一类型定义两次变量时，相对偏移应保持一致。

代码-满分

按层扫描成员即可，单次查询 \(O(\text{嵌套深度}\times \text{每层成员数})\)，在100次操作范围内足够。long long 存地址和大小。查询用循环，不展开结构体的所有基本成员。

#include <bits/stdc++.h>

using namespace std;

struct Member { string name; int type; long long offset; };
struct Type { long long size, alignment; vector<Member> members; };
struct Variable { string name; int type; long long address; };
vector<Type> types;
vector<Variable> variables;
map<string, int> typeId;

long long alignTo(long long address, long long alignment) {
    return (address + alignment - 1) / alignment * alignment;
}

int main() {
    for (auto item : vector<pair<string, int>>{{"byte", 1}, {"short", 2}, {"int", 4}, {"long", 8}}) {
        typeId[item.first] = types.size();
        types.push_back({item.second, item.second, {}});
    }
    int operations;
    cin >> operations;
    long long endAddress = 0;
    while (operations--) {
        int op;
        cin >> op;
        if (op == 1) {
            string name;
            int k;
            cin >> name >> k;
            Type current{0, 1, {}};
            for (int i = 0; i < k; i++) {
                string t, member;
                cin >> t >> member;
                int id = typeId[t];
                current.size = alignTo(current.size, types[id].alignment);
                current.members.push_back({member, id, current.size});
                current.size += types[id].size;
                current.alignment = max(current.alignment, types[id].alignment);
            }
            // 我把两个同类型变量挨着画，发现末尾也要补齐，下一份的成员才能继续对齐。
            current.size = alignTo(current.size, current.alignment);
            typeId[name] = types.size();
            types.push_back(current);
            cout << current.size << ' ' << current.alignment << '\n';
        } else if (op == 2) {
            string t, name;
            cin >> t >> name;
            int id = typeId[t];
            endAddress = alignTo(endAddress, types[id].alignment);
            variables.push_back({name, id, endAddress});
            cout << endAddress << '\n';
            endAddress += types[id].size;
        } else if (op == 3) {
            string path;
            cin >> path;
            vector<string> names;
            string name;
            stringstream stream(path);
            while (getline(stream, name, '.')) names.push_back(name);
            int id = 0;
            long long address = 0;
            for (Variable v : variables) if (v.name == names[0]) { id = v.type; address = v.address; break; }
            for (int i = 1; i < int(names.size()); i++) {
                for (Member member : types[id].members) if (member.name == names[i]) {
                    address += member.offset;
                    id = member.type;
                    break;
                }
            }
            cout << address << '\n';
        } else {
            long long address;
            cin >> address;
            int id = -1;
            string path;
            for (Variable v : variables) {
                if (v.address <= address && address - v.address < types[v.type].size) {
                    id = v.type;
                    path = v.name;
                    address -= v.address;
                    break;
                }
            }
            while (id >= 4) {
                int next = -1;
                for (Member member : types[id].members) {
                    if (member.offset <= address && address - member.offset < types[member.type].size) {
                        address -= member.offset;
                        path += "." + member.name;
                        next = member.type;
                        break;
                    }
                }
                id = next;
            }
            cout << (id == -1 ? "ERR" : path) << '\n';
        }
    }

    return 0;
}

2023T4-P9755种树 ¶

每天种一个与已种地块相邻的地块，第1天只能种根1。
第 x 天第 i 棵树长高 max(b_i+x×c_i,1)，种下当天也长高。
每棵达到目标 a_i，求最早全部完成的天数。

提示1-种树日和任务日别混淆

我先假设总共 \(T\) 天。第 \(i\) 棵若第 \(t\) 天种下，生长量要加第 \(t\sim T\) 天的增长，不是从第 \(1\sim T-t+1\) 天的增长；\(c_i\) 可负，增长不能小于1。

提示2-固定增长与特殊树形

\(c_i=0\) 的点1、5～8共25分，生长量为 \(b_i(T-t+1)\)，最晚种植日为 \(T-\left\lceil\frac{a_i}{b_i}\right\rceil+1\)。这去掉了分段增长，只剩带父子先后限制的期限排序。固定链点9～10共10分，种植顺序被唯一确定；度数 \(\le2\) 的点11～13共15分若根在中间仍有两条链，不能强行用输入编号顺序。星形树点14～16共15分，除根外只需按最晚日期排序。\(n\le 20\) 可枚举可种地块，但一般 \(n\le 10^5\)，先二分总天数。

我先选 \(c_i=0\) 的25分数据，用“目标高度÷每天增长”求所需天数，难题先变成树上期限调度。收紧父亲期限，再检查到期任务数，先把这部分写通。遇到一般增长函数时，我只替换“如何求期限”，保留同一套调度检查；负斜率降到1后要分段。外层二分总天数、内层二分单树种植日，各自的单调性要分别说清楚。

提示3-为每个地块求最后期限

每日增长都至少1，种得更早不会更差，所以存在每天不空闲、前 \(n\) 天全部种完的方案。固定 \(T\) 后，二分每棵树在 \(1\sim n\) 内的最晚种植日 \(d_i\)；超过 \(n\) 的期限统一截为 \(n\)。正斜率用等差和，负斜率先算增长 \(\ge1\) 的部分，再加后面的每天1。

提示4-把父子顺序压入期限

孩子必须晚于父亲。我从叶子向根更新 \(d_{\mathrm{parent}}=\min(d_{\mathrm{parent}},d_{\mathrm{child}}-1)\)。更新后按期限从小到大安排，父亲期限严格更小，自然排在孩子之前。若第 \(j\) 个期限小于 \(j\)，无论怎样排列都无法让这些最早到期的任务全部准时；反之期限序就是可行顺序。期限值域 \(1\sim n\)，用计数数组检查，不必每次排序。

提示5-自己动手检查

我会先检查单棵树种下当天就计增长，再测试负增长降到1的交界日。把树画成长链时，父亲必须早一天，不能让父子同日种植。

代码-25分

仅用于所有 \(c_i=0\)，覆盖点1、5～8，共25分。树 \(u\) 需要 \(\left\lceil\frac{a_u}{b_u}\right\rceil\) 天生长，所以最晚种植日可直接计算，不再二分单棵树的日期。父亲期限收紧到孩子期限减1后，所有父亲都排在孩子之前；按期限排序，只需检查前 \(d\) 天到期的树不超过 \(d\) 棵。时间 \(O(n \log 10^9)\)，空间 \(O(n)\)。\(c_i\ne 0\) 时每天生长量不同，这个直接除法就不成立。

#include <bits/stdc++.h>

using namespace std;

struct Tree { long long need, base, change; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Tree> trees(n + 1);
    for (int i = 1; i <= n; i++) cin >> trees[i].need >> trees[i].base >> trees[i].change;
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> parent(n + 1), order = {1};
    for (int i = 0; i < n; i++) for (int v : graph[order[i]]) if (v != parent[order[i]]) {
        parent[v] = order[i];
        order.push_back(v);
    }
    auto feasible = [&](long long finish) {
        if (finish < n) return false;
        vector<int> deadline(n + 1), count(n + 1);
        for (int u = 1; u <= n; u++) {
            long long days = (trees[u].need + trees[u].base - 1) / trees[u].base;
            long long lastDay = finish - days + 1;
            if (lastDay < 1) return false;
            deadline[u] = min<long long>(n, lastDay);
        }
        for (int i = n - 1; i > 0; i--) {
            int u = order[i];
            // 我先收紧孩子的期限，再让父亲至少早一天；这样按期限排序就自然满足父子顺序。
            deadline[parent[u]] = min(deadline[parent[u]], deadline[u] - 1);
        }
        for (int u = 1; u <= n; u++) {
            if (deadline[u] < 1) return false;
            count[deadline[u]]++;
        }
        int tasks = 0;
        for (int day = 1; day <= n; day++) {
            tasks += count[day];
            if (tasks > day) return false;
        }
        return true;
    };

    long long low = n, high = 1000000000LL;
    while (low < high) {
        long long mid = (low + high) / 2;
        if (feasible(mid)) high = mid;
        else low = mid + 1;
    }
    cout << low;

    return 0;
}

代码-满分

外层二分 \(T\le 10^9\)；每次判断 \(O(n \log n)\)，总计 \(O(n \log n \log 10^9)\)，空间 \(O(n)\)。等差和用 __int128，避免增长总量超过64位。子树期限传播按迭代遍历的逆序进行。

#include <bits/stdc++.h>

using namespace std;

struct Tree { long long need, base, change; };

__int128 growth(const Tree &tree, long long first, long long last) {
    if (first > last) return 0;
    long long end = last;
    if (tree.change < 0) end = min(last, (tree.base - 1) / (-tree.change));
    __int128 answer = 0;
    if (end >= first) {
        answer = (__int128)(end - first + 1) * (2 * (__int128)tree.base + (__int128)tree.change * (first + end)) / 2;
    }
    if (tree.change < 0) answer += max(0LL, last - max(first, end + 1) + 1);
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Tree> trees(n + 1);
    for (int i = 1; i <= n; i++) cin >> trees[i].need >> trees[i].base >> trees[i].change;
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> parent(n + 1), order = {1};
    for (int i = 0; i < n; i++) for (int v : graph[order[i]]) if (v != parent[order[i]]) {
        parent[v] = order[i];
        order.push_back(v);
    }
    auto feasible = [&](long long finish) {
        if (finish < n) return false;
        vector<int> deadline(n + 1), count(n + 1);
        for (int u = 1; u <= n; u++) {
            if (growth(trees[u], 1, finish) < trees[u].need) return false;
            int low = 1, high = n;
            while (low < high) {
                int mid = (low + high + 1) / 2;
                if (growth(trees[u], mid, finish) >= trees[u].need) low = mid;
                else high = mid - 1;
            }
            deadline[u] = low;
        }
        for (int i = n - 1; i > 0; i--) {
            int u = order[i];
            // 我先收紧孩子的期限，再让父亲至少早一天；这样按期限排序就自然满足父子顺序。
            deadline[parent[u]] = min(deadline[parent[u]], deadline[u] - 1);
        }
        for (int u = 1; u <= n; u++) {
            if (deadline[u] < 1) return false;
            count[deadline[u]]++;
        }
        int tasks = 0;
        for (int day = 1; day <= n; day++) {
            tasks += count[day];
            if (tasks > day) return false;
        }
        return true;
    };

    long long low = n, high = 1000000000LL;
    while (low < high) {
        long long mid = (low + high) / 2;
        if (feasible(mid)) high = mid;
        else low = mid + 1;
    }
    cout << low;

    return 0;
}

2024T1-P11231决斗 ¶

每张卡的攻击力、防御力相同。每卡最多攻击一次，
只能击败严格比自己弱的卡。决定攻击顺序，使最后剩余数量最小。

提示1-被击败前能先攻击吗

我先看1、2、3三张卡。能否让2先击败1，再让3击败2？这提醒我，一张卡被击败前的那次攻击仍然有用。

提示2-两种值与随机性质

\(n\le 10\) 的点1～4共20分可以搜索状态，但并非必须。\(r\le 2\) 的点5～10共30分，只有2能消灭1，最多消灭 \(\min(\text{1的数量},\text{2的数量})\)。随机数据点11～15共25分不保证没有重复，不能直接输出1。全数据 \(n,r\le 10^5\)，值域允许直接计数。

我先只看攻击力1、2，写出能消灭多少张1，这能理解 \(r\le 2\) 的30分范围。再加入3，我尝试让2先攻击1、3再攻击2，发现攻击可以串成链。于是我把“搜索攻击顺序”换成“分成多少条严格递增链”：重复值给出下界，按值分组放入不同链能达到下界，直接计频次就覆盖全数据。

提示3-把有效攻击画成链

每次有效攻击把更大的数连向更小的数。每张卡至多攻击一次、至多被击败一次，所以形成若干条严格递增的链，不能形成环。每条链从小到大执行攻击，只留下最大值。相同数不能放同一链，因此出现最多的那个数至少需要这么多条链。

提示4-这个下界能达到

设最大重复次数为 \(M\)，准备 \(M\) 条空链。按数值从小到大，每组相同值分别放入不同的链；所有链都保持严格递增。每条链依次让更大数消灭前一个数，恰留下 \(M\) 张。答案就是最大频次，无须模拟攻击。

提示5-自己动手检查

我会手算全相同、全互异和1、1、2、3三组数据。画出各条链，再按从小到大的顺序执行，检查每卡是否只攻击一次。

代码-满分

时间 \(O(n+\text{值域})\)，空间 \(O(\text{值域})\)。\(r\le 2\) 时的答案也包含在这个计数方法中，不重复给代码。

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
int countValue[N];

int main() {
    int n;
    cin >> n;
    int answer = 0;
    for (int i = 0; i < n; i++) {
        int strength;
        cin >> strength;
        countValue[strength]++;
        // 我把相同值分别放到不同链，最多的重复次数既是下界，也是可构造的链数。
        answer = max(answer, countValue[strength]);
    }
    cout << answer;

    return 0;
}

2024T2-P11232超速检测 ¶

车从位置 d 以速度 v、加速度 a 前进，至道路末端或速度0离开。
测速仪只在车经过时检测，速度严格大于 V 才超速。
求全部开启时被检出的车数，以及仍检出这些车时最多可关闭的仪器数。

提示1-先分清超速与被检出

我先找一辆车的超速路段。路段内没有测速仪时，这辆车不能计入第一问，也不需要在第二问保证它被检出。

提示2-三种加速度条件

\(n,m\le 20\) 的点1～2共20分可枚举保留仪器集合。\(a=0\) 的点3～4共20分，每辆超速车对应从 \(d\) 到 \(L\) 的后缀，有仪器能检测就能被最后一个仪器检测，只需保留最后一个。\(a>0\) 的点5～6共20分也形成后缀，所以同样只需最后一个。\(a<0\) 且不到 \(L\) 的点7～8共20分形成有不同左右端点的前段，已需要区间选点；停车限制不是删去所有这些车的理由。

我先选 \(a=0\) 的20分条件：一辆车是否超速不再变化。再看 \(a>0\) 的另20分：可检测仪器依旧是一个后缀，同一个最后仪器即可保住全部被检出的车。\(a<0\) 时，这个后缀结论失效，我才把一辆车表示成一般区间。求出各区间后，第二问就变成熟悉的最少选点覆盖区间。

提示3-用速度平方判断

位置 \(p\ge d\) 时，速度平方是 \(v^2+2a(p-d)\)。与 \(V^2\) 比较即可，不开根号，没有边界浮点误差。\(a>0\) 时从不超速到超速；\(a<0\) 时从超速到不超速；\(a=0\) 直接判断。二分得到能检测该车的仪器编号区间 \([l,r]\)。负加速度车在停车后表达式为负，当然不能检出超速。

提示4-为什么选最早结束区间的右端

按右端点排序。当前区间没有已选仪器时，选它最右的仪器：必须在这里选一个，选得越右越可能兼顾后面右端更大的区间。只保留非空区间，第一问为区间数，第二问为 \(m\) 减所选数。

提示5-自己动手检查

我会先试速度恰好等于 \(V\)、车起点恰好在仪器处和所有仪器都在车后方。减速车停车后的负速度平方不能当作超速。

代码-40分

仅用于所有车 \(a\ge 0\)，覆盖 \(a=0\) 的点3～4及 \(a>0\) 的点5～6，共40分。每辆车的可检测仪器都是后缀，因此只检查最后一个仪器：若它也检不出，就没有其他仪器能检出；有被检出的车时保留它一个即可，否则全部关闭。时间 \(O(n+m)\)，空间 \(O(n+m)\)。负加速度时可检测区间不再是后缀，此代码失效。

#include <bits/stdc++.h>

using namespace std;

struct Car { long long start, speed, acceleration; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        long long length, limit;
        cin >> n >> m >> length >> limit;
        vector<Car> cars(n);
        for (Car &c : cars) cin >> c.start >> c.speed >> c.acceleration;
        vector<long long> position(m);
        for (long long &p : position) cin >> p;

        int caught = 0;
        for (Car c : cars) {
            long long last = position.back();
            if (last < c.start) continue;
            if (c.speed * c.speed + 2 * c.acceleration * (last - c.start) > limit * limit) caught++;
        }
        // 我先确认每辆车的检测区间都是后缀，才用最后一个仪器同时覆盖；减速车不能这样做。
        cout << caught << ' ' << m - (caught > 0) << '\n';
    }

    return 0;
}

代码-满分

时间 \(O(n \log m+n \log n)\)，空间 \(O(n+m)\)。仪器已排序，速度平方用 long long，判定严格大于；位置 \(d\) 和 \(L\) 处的仪器都按规则检测。

#include <bits/stdc++.h>

using namespace std;

struct Car { long long start, speed, acceleration; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        long long length, limit;
        cin >> n >> m >> length >> limit;
        vector<Car> cars(n);
        for (Car &c : cars) cin >> c.start >> c.speed >> c.acceleration;
        vector<long long> position(m);
        for (long long &p : position) cin >> p;
        vector<pair<int, int>> intervals;
        for (Car c : cars) {
            int first = lower_bound(position.begin(), position.end(), c.start) - position.begin();
            if (first == m) continue;
            auto speeding = [&](int i) {
                return c.speed * c.speed + 2 * c.acceleration * (position[i] - c.start) > limit * limit;
            };
            int l = first, r = m - 1;
            if (c.acceleration >= 0) {
                if (!speeding(r)) continue;
                int low = first, high = m - 1;
                while (low < high) {
                    int mid = (low + high) / 2;
                    if (speeding(mid)) high = mid;
                    else low = mid + 1;
                }
                l = low;
            } else {
                if (!speeding(l)) continue;
                int low = first, high = m - 1;
                while (low < high) {
                    int mid = (low + high + 1) / 2;
                    if (speeding(mid)) low = mid;
                    else high = mid - 1;
                }
                r = low;
            }
            intervals.push_back({r, l});
        }
        sort(intervals.begin(), intervals.end());
        int kept = 0, last = -1;
        for (auto interval : intervals) {
            if (last < interval.second) {
                // 我必须在当前区间选一个，选右端既覆盖它，也给后面的区间留下最多机会。
                last = interval.first;
                kept++;
            }
        }
        cout << intervals.size() << ' ' << m - kept << '\n';
    }

    return 0;
}

2024T3-P11233染色 ¶

把正整数序列染成红蓝两色。一个位置左侧最近的同色数
若与它相等，该位置得分为自己的值，否则得0。
求最大总得分，多组数据。

提示1-颜色名字重要吗

我先处理前缀。最后一个数一定是某种颜色的末尾；红蓝可以整体交换，因此只需记“另一种颜色最后的值”，不用为颜色名字加一维。

提示2-值域小会减少状态

\(n\le 15\) 的点1～4共20分可枚举 \(2^n\) 种染色。\(n\le 2000\) 的点1～10共50分，可用 \(O(n^2)\) 的前缀DP。\(A_i\le 10\) 的点13～15另有15分，状态只需记另一颜色末值 \(0\sim10\)，\(O(10n)\)，两档合起来65分。全数据 \(n\le 2\times 10^5\)、\(A_i\le 10^6\)，不宜每一步遍历所有值；总得分可能超过int。

我先在 \(n\le 15\) 枚举染色，拿20分，核对得分究竟找哪一个同色前驱。接着用“另一颜色的末值”做DP，\(n\le 2000\) 或值域不超过 \(10\) 可覆盖65分。扩大值域时，我发现多数状态做完全相同的加法，只有换色后的一个状态特殊；把公共加法放进 offset、保存全局最大值，就省掉逐状态遍历。值域小的代码也是检查满分优化的工具。

提示3-每次只有一个状态需要特殊更新

我设 \(\mathrm{dp}[x]\) 为当前最后一个数属于一色、另一色末值为 \(x\) 时的最大得分；\(x=0\) 表示另一色还没用过。设旧末值为 \(p\)，新值为 \(z\)，旧状态最大值为 \(M\)。

若沿用当前末尾颜色，每个状态统一加：

\[ g=\begin{cases}z,&z=p,\\0,&z\ne p.\end{cases} \]

若换成另一色，新的“另一色末值”都变成 \(p\)。旧状态 \(x=z\) 能额外得 \(z\) 分，其他状态不能，因此换色最优收益是：

\[ \max\bigl(M,\mathrm{dp}[z]+z\bigr). \]

不存在的 \(\mathrm{dp}[z]\) 不能当作 \(0\)。我先用逐状态DP实现这两类决定，再观察哪里可以省掉遍历。

提示4-统一加用偏移量保存

我给所有状态共同的加数设 offset，数组只存 \(\mathrm{dp}[x]-\mathrm{offset}\)。每次先用旧状态计算换色收益，再增加 offset，最后只更新旧末值对应的一个状态。全局最大值也同步更新。没有出现过的状态设为负无穷，不能默认0而假装另一色用过某个值。

提示5-自己动手检查

我会先比较1、2、1与1、1、1，确认跳过异色位置后仍能得分。更新时先计算换色收益再改 offset，检查有没有把新收益重复加上。

代码-65分

确定性逐状态DP。覆盖 \(n\le 2000\) 的点1～10与值域不超过 \(10\) 的点13～15，共65分。map 只保存已出现的末值，时间 \(O(n\cdot \text{不同值数}+n \log n)\)，空间 \(O(\text{不同值数})\)，一般大值域会慢。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, last;
        cin >> n >> last;
        map<int, long long> dp;
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            int x;
            cin >> x;
            // 我先枚举旧状态算换色收益，再给所有状态加同色收益，避免相互覆盖。
            long long switchBest = 0;
            for (auto state : dp) switchBest = max(switchBest, state.second + (state.first == x ? x : 0));
            int gain = x == last ? x : 0;
            for (auto &state : dp) state.second += gain;
            auto it = dp.find(last);
            if (it == dp.end()) dp[last] = switchBest;
            else it->second = max(it->second, switchBest);
            last = x;
        }
        long long answer = 0;
        for (auto state : dp) answer = max(answer, state.second);
        cout << answer << '\n';
    }

    return 0;
}

代码-满分

时间 \(O(n+\text{值域})\)，空间 \(O(\text{值域})\)，每组重置状态。offset、dp 和答案均用 long long。

#include <bits/stdc++.h>

using namespace std;

const int V = 1000005;
const long long NEG = -4000000000000000000LL;
long long dp[V];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        fill(dp, dp + V, NEG);
        dp[0] = 0;
        int n, last;
        cin >> n >> last;
        long long offset = 0, answer = 0;
        for (int i = 1; i < n; i++) {
            int x;
            cin >> x;
            long long switchBest = answer;
            if (dp[x] != NEG) switchBest = max(switchBest, dp[x] + offset + x);
            int gain = x == last ? x : 0;
            // 我先算换色时的旧得分，再改公共加数；若顺序颠倒，会把本次收益重复算进去。
            offset += gain;
            dp[last] = max(dp[last], switchBest - offset);
            answer = max(answer + gain, switchBest);
            last = x;
        }
        cout << answer << '\n';
    }

    return 0;
}

2024T4-P11234擂台游戏 ¶

前 c 位选手已报名，其余补到最小的2的幂，补充者能力可任取。
第 R 轮擂主能力≥R就赢，否则对手赢；擂主由固定抽签决定。
求所有可能冠军的编号和，包括补充者；对各询问按序号乘积取异或。
多组能力由原数组与 X[i mod 4] 异或生成，抽签和询问共用。

提示1-先做没有补充者的一场

我先把 \(c\) 设成2的幂。所有能力都确定，按比赛树从底往上模拟，只会有一个冠军。普通强者胜出的规则在这里不适用：只看擂主能力与轮数。

提示2-哪些限制减少不确定性

点1～3人数不超过 \(8\) 共12分，可枚举补充者能力 \(0\sim K\)，超过 \(K\) 的能力没有区别。性质 \(A\) 的点4～5、11～12共16分，询问都是2的幂，可一次模拟比赛树后直接取对应子树冠军。性质 \(B\) 的点6～8、13～15共24分，擂主全在左侧，只省掉左右分支选择，不代表所有补充者都能获胜。一般 \(T\le 256\)，必须复用抽签条件，并把每组复杂度降为 \(O(n+m)\)。

我先取询问人数为2的幂，比赛没有补充者，底向上模拟即可拿性质 \(A\) 的16分。小人数的12分条件还可枚举补充者能力，观察未知子树怎样主动输赢。一般询问重复模拟太慢，我转而记录：报名人数增长时，一个确定的强擂主从哪天开始挡住另一侧？每个比赛结点只会首次确定一次，这个特点才支持每组线性更新。

提示3-不确定冠军可以主动让路

一个子树的冠军若还没被唯一固定，它一定存在补充者当冠军的方案，且可以让其能力为这棵子树高度。下一轮高度多1，它就能作为擂主主动输给另一侧。这可按比赛树归纳：补充者若需要守住某轮，能力取该轮高度已足够；固定选手若挡住它，子树冠军就已固定。

提示4-记录什么时候对手开始挡路

按编号逐个报名。每个叶子及比赛结点的确定冠军能力只会从未知变为确定一次。一个擂主子树确定且能力不小于当前轮数时，另一侧从这一天开始就不可能晋级；给另一侧记上限“报名人数不超过当天减 \(1\)”。把这些上限从根往叶传播，就得到每个选手被对手限制的最大人数。

提示5-自身守擂另行处理

已报名者还必须有足够能力通过自己担任擂主的轮次。这些轮次只取决于抽签，可以在所有测试组之前预处理：若能力不足以守第 \(R\) 轮，比赛人数最多 \(2^{R-1}\)。选手还未报名时是补充者，不受其真实能力限制，因此自身上限至少为 \(i-1\)。编号 \(i\) 的参与下限是刚能把总人数扩到包含它的前缀；最终贡献是一个人数区间，差分加 \(i\) 即可。

提示6-自己动手检查

我会检查补充者编号也能成为冠军，以及能力不足者在尚未报名时仍可获胜。再用只有一轮的比赛逐种比较左右擂主，核对截断日期。

代码-满分

抽签条件预处理 \(O(n \log n)\)，每组 \(O(n+m)\)，空间 \(O(n \log n)\)。比赛树补到 \(N=2^K\)；编号 \(n+1\sim N\) 同样参与冠军统计。下面迭代更新与下传，避免为每个询问重算。

#include <bits/stdc++.h>

using namespace std;

const int MAXK = 17;
int x[4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> original(n + 1), queries(m + 1);
    for (int i = 1; i <= n; i++) cin >> original[i];
    for (int i = 1; i <= m; i++) cin >> queries[i];
    int size = 1, height = 0;
    while (size < n) { size *= 2; height++; }
    vector<int> host(size * 2), round(size * 2), lower(size + 1);
    for (int r = 1; r <= height; r++) {
        string bits;
        cin >> bits;
        int first = size >> r;
        for (int g = 0; g < int(bits.size()); g++) {
            host[first + g] = bits[g] - '0';
            round[first + g] = r;
        }
    }
    lower[1] = 1;
    for (int block = 1; block < size; block *= 2) {
        for (int i = block + 1; i <= block * 2; i++) lower[i] = block + 1;
    }
    vector<array<int, MAXK + 1>> ownLimit(n + 1);
    for (int i = 1; i <= n; i++) {
        array<bool, MAXK + 1> mustHold{};
        int u = size + i - 1;
        for (int r = 1; r <= height; r++) {
            int p = u / 2;
            mustHold[r] = host[p] == u % 2;
            u = p;
        }
        int firstFailure = height + 1;
        ownLimit[i][height] = n;
        for (int power = height - 1; power >= 0; power--) {
            if (mustHold[power + 1]) firstFailure = power + 1;
            ownLimit[i][power] = firstFailure > height ? n : (1 << (firstFailure - 1));
        }
    }

    int tests;
    cin >> tests;
    while (tests--) {
        for (int &v : x) cin >> v;
        vector<int> ability(n + 1), fixedPower(size * 2, -1), limit(size * 2, n);
        for (int i = 1; i <= n; i++) {
            ability[i] = original[i] ^ x[i % 4];
            int u = size + i - 1;
            fixedPower[u] = ability[i];
            while (u > 1) {
                int p = u / 2;
                if (fixedPower[p] != -1) break;
                int h = p * 2 + host[p], other = h ^ 1;
                if (fixedPower[h] == -1) break;
                if (fixedPower[h] >= round[p]) {
                    // 我先确认擂主已固定且守得住这一轮，才截断另一侧；未知补充者仍可能主动让路。
                    limit[other] = min(limit[other], i - 1);
                    fixedPower[p] = fixedPower[h];
                } else {
                    if (fixedPower[other] == -1) break;
                    fixedPower[p] = fixedPower[other];
                }
                u = p;
            }
        }
        for (int u = 1; u < size; u++) {
            limit[u * 2] = min(limit[u * 2], limit[u]);
            limit[u * 2 + 1] = min(limit[u * 2 + 1], limit[u]);
        }
        vector<long long> difference(n + 2);
        for (int i = 1; i <= size; i++) {
            int l = lower[i], r = limit[size + i - 1];
            if (i <= n && ability[i] < height) r = min(r, max(i - 1, ownLimit[i][ability[i]]));
            if (l <= r) {
                difference[l] += i;
                difference[r + 1] -= i;
            }
        }
        for (int i = 1; i <= n; i++) difference[i] += difference[i - 1];
        long long answer = 0;
        for (int i = 1; i <= m; i++) answer ^= 1LL * i * difference[queries[i]];
        cout << answer << '\n';
    }

    return 0;
}

2025T1-P14361社团招新 ¶

把偶数 n 名新成员分到三个部门，每部门至多 n/2 人。
每人对三个部门有非负满意度，求分配后的最大总满意度。
有多组测试数据。

提示1-先去掉人数限制

我先把每个人分到最满意的部门。只有三个部门，最多有几个部门的人数能超过 \(n/2\)？

提示2-零值条件变成排序

\(n=2\)、4、10 的点1～4共20分可枚举 \(3^n\) 种分配。性质 \(A\) 点12共5分，只有部门1有收益，选满意度最高的 \(n/2\) 个人给它。性质 \(B\) 点9、13～14共15分，部门3收益为0，非负收益保证可把所有人放在1、2部门并各占 \(n/2\)，按 \(a_1-a_2\) 排序选择部门1。\(A\) 也满足 \(B\)，所以这条路径覆盖20分。随机满意度的点15～16共10分没有严格简化，不凭概率忽略人数限制。

我先在小 \(n\) 时枚举三部门分配，拿20分，并保存最优结果。若部门3收益全0，题目变成两组各半的排序分配，性质 \(A\)、\(B\) 这条路径也覆盖20分。一般数据我先让每个人去最满意处，检查只有一个部门可能超额；另外两部门总人数的上界说明转去任意一个都不超限，于是只需选移走损失最小的人。

提示3-只修正唯一超额部门

若贪心结果合法，它已达到每人最大值的上界。否则只有一个超额部门 \(h\)；必须从中移走人数超出的那部分。移走的人改去两个其他部门中更满意的一个，损失=原收益−次优收益。

提示4-为什么最小损失能独立选择

把 \(h\) 人数减到 \(n/2\) 后，其余两个部门总人数也只有 \(n/2\)，因此不管这些人各自选哪个部门，都不会超限。各人的损失独立，选最小的若干个即可。平局任意选部门，损失为0的调整也包含在排序中。

提示5-自己动手检查

我会先测所有收益0、最大收益并列、全部人最喜欢同一部门。每次调整都同时核对部门人数与损失，避免只看总收益。

代码-20分

仅适用于 \(a[i][3]=0\)，覆盖 \(B\) 的15分及 \(A\) 的5分；不要与小 \(n\) 测试点擅自相加。所有收益非负，可让部门1、2各收 \(n/2\) 人。时间 \(O(n \log n)\)。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<int> difference;
        long long answer = 0;
        for (int i = 0; i < n; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            answer += b;
            difference.push_back(a - b);
        }
        sort(difference.begin(), difference.end(), greater<int>());
        // 我先全放部门2作为基准，再按改去部门1的增益排序，取恰好一半而非只取正增益。
        for (int i = 0; i < n / 2; i++) answer += difference[i];
        cout << answer << '\n';
    }

    return 0;
}

代码-满分

时间 \(O(n \log n)\)，空间 \(O(n)\)。总满意度用 long long；全为0、并列最大值及 \(n=2\) 均可处理。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<vector<int>> loss(3);
        long long answer = 0;
        for (int i = 0; i < n; i++) {
            array<int, 3> a;
            for (int &x : a) cin >> x;
            int best = 0;
            for (int j = 1; j < 3; j++) if (a[j] > a[best]) best = j;
            int second = 0;
            for (int j = 0; j < 3; j++) if (j != best) second = max(second, a[j]);
            answer += a[best];
            loss[best].push_back(a[best] - second);
        }
        for (int department = 0; department < 3; department++) {
            int excess = int(loss[department].size()) - n / 2;
            if (excess <= 0) continue;
            sort(loss[department].begin(), loss[department].end());
            // 我先算必须移走多少人，再挑损失最小的；其余两部门总人数不超过一半，转入不会超限。
            for (int i = 0; i < excess; i++) answer -= loss[department][i];
        }
        cout << answer << '\n';
    }

    return 0;
}

2025T2-P14362道路修复 ¶

原有城市间道路已损坏，付费可修复。
可选择若干乡镇，支付启用费后，再付费连到原有城市。
求使原有城市全部连通的最低总费用，费用可以为0。

提示1-没有乡镇时是什么题

我先设 \(k=0\)。只需把原城市连通，非负费用下保留一棵树就够，这是最小生成树；全修复通常不是最优。

提示2-乡镇少比道路少更重要

\(k=0\) 的点1～4共16分直接Kruskal。\(k\le 5\) 的多档允许枚举至多32种启用集合；全数据 \(k\le 10\)，至多1024种，但 \(m\le 10^6\)，不能每种都重复扫描百万原边。性质 \(A\) 的点5～6、9～10、13～14、17～18共32分，启用费为0且每个乡镇有一条0费用连接：全部启用并用0边附着原城不会增加费用，所以只跑一次增广图MST。一般有启用费则不成立。

我先设 \(k=0\)，完成Kruskal，拿16分。\(k\) 很小让我想到枚举启用集合，但原边有百万条，重跑1024次太慢；我先证明原图的一棵MST能替代所有原边，再复用一次排序的短边表。性质 \(A\) 中全部启用无害，可单独拿32分；有启用费时，这个特殊结论就不能沿用。

提示3-先扔掉不会必需的原边

求原图的一棵MST，只保留它的 \(n-1\) 条边。原来的非树边 \(e\)，其树路径上的每条边费用均不超过 \(e\)；即使加入乡镇，若最优树使用了 \(e\)，删 \(e\) 后树路径总有一条跨越该切割的边可替换，费用不增。因此同一棵原图MST足以应对所有乡镇集合。

提示4-枚举启用集合再求MST

保留原MST与 \(kn\) 条乡镇连接边，一次排序。每个集合初始化并查集，只扫描属于已启用乡镇或原树的边；要连通原有城市及所有已启用乡镇，费用加启用费。最优方案中实际用到的乡镇都在同一连通块里；多启用而不用的乡镇没有好处，所以枚举不会漏解。\(n=1\) 时可不启用任何乡镇，答案0。

提示5-自己动手检查

我会先用零费用、重复边和多个同权MST核对。枚举一个乡镇集合时，既要加启用费，也要把该乡镇当作必须连接的点。

代码-满分

时间 \(O(m \log m+kn \log (kn+n)+2^k(kn+n)\alpha (n))\)，空间 \(O(m+kn)\)。性质 \(A\) 只枚举全集，\(k=0\) 只枚举空集；一般枚举全部集合。重边由Kruskal自然处理。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 4000000000000000000LL;
struct Edge { int u, v, cost, town; };
struct DSU {
    vector<int> parent, size;
    DSU(int n) : parent(n + 1), size(n + 1, 1) {
        for (int i = 0; i <= n; i++) parent[i] = i;
    }
    int findRoot(int x) {
        if (parent[x] == x) return x;
        return parent[x] = findRoot(parent[x]);
    }
    bool join(int u, int v) {
        u = findRoot(u); v = findRoot(v);
        if (u == v) return false;
        if (size[u] < size[v]) swap(u, v);
        parent[v] = u;
        size[u] += size[v];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<Edge> original(m), edges;
    for (Edge &e : original) { cin >> e.u >> e.v >> e.cost; e.town = -1; }
    auto cheaper = [](Edge a, Edge b) { return a.cost < b.cost; };
    sort(original.begin(), original.end(), cheaper);
    // 我先用原图的MST压缩边集，再枚举乡镇，省掉重复扫描百万条原边。
    DSU initial(n);
    for (Edge e : original) if (initial.join(e.u, e.v)) edges.push_back(e);
    vector<Edge>().swap(original);
    vector<long long> activation(k);
    bool freeTowns = true;
    for (int j = 0; j < k; j++) {
        cin >> activation[j];
        bool hasZero = false;
        for (int i = 1; i <= n; i++) {
            int cost;
            cin >> cost;
            hasZero = hasZero || cost == 0;
            edges.push_back({i, n + j + 1, cost, j});
        }
        freeTowns = freeTowns && activation[j] == 0 && hasZero;
    }
    sort(edges.begin(), edges.end(), cheaper);
    long long answer = INF;
    int firstMask = freeTowns ? (1 << k) - 1 : 0;
    for (int mask = firstMask; mask < (1 << k); mask++) {
        DSU dsu(n + k);
        long long cost = 0;
        int required = n - 1;
        for (int j = 0; j < k; j++) if (mask >> j & 1) { cost += activation[j]; required++; }
        for (Edge e : edges) {
            if (required == 0) break;
            if (e.town >= 0 && !(mask >> e.town & 1)) continue;
            if (dsu.join(e.u, e.v)) { cost += e.cost; required--; }
        }
        answer = min(answer, cost);
    }
    cout << answer;

    return 0;
}

2025T3-P14363谐音替换 ¶

给定若干等长字符串替换规则 (s₁,s₂)。
把询问串 t₁ 中一个匹配 s₁ 的子串替换为 s₂，得到 t₂。
求方法数；规则编号或替换位置不同都算不同，t₁与t₂本来不同。

提示1-长度和不同位置先告诉我什么

我先比较 \(t_1\)、\(t_2\)。规则不改变长度，所以不同长立即无解；如果最左、最右不同位置为 \(l\)、\(r\)，替换范围必须覆盖整个 \([l,r]\)。

提示2-单询问和特别字符串

点1～5的总长度不超过 \(2000\) 共25分，可逐规则、逐位置匹配。性质 \(A\) \(q=1\) 的点6～8、13～14共25分，少了重复询问，但一长串与许多规则反复匹配仍会慢。性质 \(B\) 的点6、9～10、15～16共25分，每串只有一个 \(b\)：非平凡替换对应 \(b\) 的位移，共同的 \(a\) 前后缀限制变成两个长度不等式，可分组离线计数。\(A\) 与 \(B\) 重叠点6，不能重复算。全数据字典与询问各总长度 \(\le5\times10^6\)，复杂度应跟总长度而不是nq走。

我先在总长度不超过 \(2000\) 的25分数据逐规则、逐位置替换，再比较结果，先把方法数的定义弄清楚。\(q=1\) 只省询问次数，不能消除单次匹配很长的瓶颈；只有一个 \(b\) 的性质才真正把匹配变成位置和长度约束。一般串我同时比较替换前后字符，组合成一个字符对模式；再用最左、最右差异位置过滤匹配长度，避免重复做整串比较。

提示3-两个串一起匹配

我把同一位置的两个字符作为一个字符对，共 \(26^2\) 种符号。规则变成一个模式串，询问也变成一个文本串；匹配这个模式串，就同时保证替换前后内容都吻合。用AC自动机扫描文本，不需要字符串哈希猜相等。

提示4-长度筛选保证覆盖不同区间

扫描到位置 \(i\ge r\) 时，匹配规则长度必须 \(\ge i-l+1\)，才能从 \(l\) 或更左开始。所有以 \(i\) 结尾的匹配模式位于当前状态的 fail 祖先链上；祖先深度递减，可以倍增找到最后一个长度仍够的祖先，用终止标记前缀和相减。重复规则的终止标记累计，不去重。

提示5-676种转移别全部开数组

每个节点开676个儿子会占数GB。我用稀疏字典建 Trie；构造 fail 时用可持久化线段树保存676项转移，继承 fail 状态的转移后只修改真实儿子。每次查转移 \(O(\log 676)\)，无需反复沿 fail 回退建边，内存也跟真实字典长度成正比。

提示6-自己动手检查

我会测试重复规则、相同规则在多个位置出现、询问长度不同，以及两个相距很远的差异位置。规则必须覆盖全部差异，不能只匹配某一个变化处。

代码-满分

时间 \(O(L_1\log 676+L_2(\log 676+\log L_1))\)，空间 \(O(L_1(\log 676+\log L_1))\)，适配原题2048MiB限制。此实现对匹配结果精确；unordered_map 只索引精确整数键，哈希碰撞不会误判规则相等。递归只用于676项线段树，深度不超过 \(10\)。

#include <bits/stdc++.h>

using namespace std;

const int ALPHABET = 676, LOG = 22;
struct Transition { int left = 0, right = 0, value = 0; };
vector<Transition> transitions(1);

int modify(int old, int l, int r, int position, int value) {
    int id = transitions.size();
    transitions.push_back(transitions[old]);
    if (l == r) { transitions[id].value = value; return id; }
    int mid = (l + r) / 2;
    if (position <= mid) transitions[id].left = modify(transitions[old].left, l, mid, position, value);
    else transitions[id].right = modify(transitions[old].right, mid + 1, r, position, value);
    return id;
}
int nextState(int root, int position) {
    int l = 0, r = ALPHABET - 1;
    while (root && l < r) {
        int mid = (l + r) / 2;
        if (position <= mid) { root = transitions[root].left; r = mid; }
        else { root = transitions[root].right; l = mid + 1; }
    }
    return transitions[root].value;
}
struct State {
    int fail = 0, depth = 0, terminal = 0, sum = 0, version = 0;
    vector<pair<int, int>> children;
};
int symbol(char a, char b) { return (a - 'a') * 26 + b - 'a'; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<State> trie(1);
    unordered_map<long long, int> child;
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        int u = 0;
        for (int j = 0; j < int(a.size()); j++) {
            int c = symbol(a[j], b[j]);
            long long key = 1LL * u * ALPHABET + c;
            auto it = child.find(key);
            if (it != child.end()) u = it->second;
            else {
                int v = trie.size(), depth = trie[u].depth + 1;
                trie.push_back(State{});
                trie[v].depth = depth;
                trie[u].children.push_back({c, v});
                child[key] = v;
                u = v;
            }
        }
        trie[u].terminal++;
    }
    unordered_map<long long, int>().swap(child);
    transitions.reserve(trie.size() * 11);
    vector<array<int, LOG>> ancestor(trie.size());
    vector<int> queue = {0};
    for (int head = 0; head < int(queue.size()); head++) {
        int u = queue[head], f = trie[u].fail;
        trie[u].sum = trie[u].terminal + (u ? trie[f].sum : 0);
        if (u) {
            ancestor[u][0] = f;
            for (int j = 1; j < LOG; j++) ancestor[u][j] = ancestor[ancestor[u][j - 1]][j - 1];
        }
        int version = u ? trie[f].version : 0;
        for (auto edge : trie[u].children) version = modify(version, 0, ALPHABET - 1, edge.first, edge.second);
        trie[u].version = version;
        for (auto edge : trie[u].children) {
            trie[edge.second].fail = u ? nextState(trie[f].version, edge.first) : 0;
            queue.push_back(edge.second);
        }
    }

    while (q--) {
        string a, b;
        cin >> a >> b;
        if (a.size() != b.size()) { cout << 0 << '\n'; continue; }
        int first = 0, last = int(a.size()) - 1;
        while (a[first] == b[first]) first++;
        while (a[last] == b[last]) last--;
        int u = 0;
        long long answer = 0;
        for (int i = 0; i < int(a.size()); i++) {
            u = nextState(trie[u].version, symbol(a[i], b[i]));
            int required = i - first + 1;
            if (i < last || trie[u].depth < required) continue;
            int v = u;
            // 我先定位全部差异的左右端点，再筛匹配长度；只覆盖其中一个差异不能完成替换。
            for (int j = LOG - 1; j >= 0; j--) {
                int p = ancestor[v][j];
                if (trie[p].depth >= required) v = p;
            }
            answer += trie[u].sum - trie[trie[v].fail].sum;
        }
        cout << answer << '\n';
    }

    return 0;
}

2025T4-P14364员工招聘 ¶

决定 n 人的面试顺序。第 i 天题目容易则录用，难则拒绝。
若此前未录用人数已不少于某人的耐心 c，他会直接放弃，
放弃也算未录用。求能录用至少 m 人的排列数，模 998244353。

提示1-先做一遍真实模拟

我先枚举小排列，记录已失败人数 \(j\)。判断耐心必须用 \(c>j\)，等于 \(j\) 也会放弃；当天拒绝后，\(j\) 才增加。\(n\le 10\) 的点1～2共8分可枚举 \(n!\)；\(n\le 18\) 的点3～5另有12分可按已处理人员集合DP，录用人数还需作为状态，不能只记mask。

提示2-简单条件仍要检查耐心0

\(m=n\) 的点15共4分，只有全是容易题且所有 \(c>0\) 时，全部 \(n!\) 种排列可行。\(m=1\) 的点12～14共12分，可用总排列减去一个都不录用：容易题的第 \(i\) 天只能放 \(c\le i-1\) 的人，难题日随便放，按允许耐心上限排序求匹配数。全是容易题的性质 \(A\) 点6～8、16～17共20分也不等于答案 \(n!\)，\(c=0\) 仍会导致失败并影响后人。最多18个容易题的 \(B\) 点18～21共16分可枚举成功日集合，但不能枚举全部 \(n\) 个人的集合。

我先在 \(n\le 10\) 枚举面试排列，拿8分，逐日按失败人数判断是否放弃。\(m=1\) 时改成总排列减“全不录用”，只剩允许耐心上限的匹配，可拿12分。一般情况我尝试按天数、失败数DP，但剩余耐心分布没有被记住；为减少状态，我观察高耐心者当前作用相同，先留空位，等失败数达到其耐心时再分配姓名。优化前先解释清楚哪些人可以暂时不区分。

提示3-人太多，先留没填名字的位置

普通DP若只记“已过 \(i\) 天、失败 \(j\) 人”，不知道还剩哪些耐心。我的状态再记 \(k\) 个空位：这些已面试位置属于耐心 \(>j\) 的人，但暂时没指定具体名字；耐心 \(\le j\) 的人则已经填了具体名字。只要失败数没变，这些高耐心人在未来转移中完全同类，可以延迟分配。

提示4-失败增加时，给一组人填名字

我记 \(\mathrm{cnt}[t]\) 为耐心恰为 \(t\) 的人数，\(S_j\) 为耐心不超过 \(j\) 的人数。当失败数由 \(j\) 增至 \(j+1\) 时，这一组人不再与高耐心者同类，要分配具体姓名。

从 \(k\) 个空位挑 \(\ell\) 个，再挑出 \(\ell\) 个耐心恰为 \(j+1\) 的人，并排列姓名，方案系数为：

\[ \binom{k}{\ell}\binom{\mathrm{cnt}[j+1]}{\ell}\ell!,\qquad 0\le\ell\le\min(k,\mathrm{cnt}[j+1]). \]

我把“选位置、选人、排列”分别数一遍，检查没有遗漏，也没有提前给其他高耐心者分配姓名。

提示5-两种日子的转移

容易题日：选低耐心人有 \(S_j-(i-k)\) 种，失败增1并按上一条填名字；选高耐心人就成功，增加一个空位，不乘高耐心总人数，姓名留到以后算。难题日：先填 \(l\) 个刚变成低耐心的人，再从剩余低耐心人中选当天的人，或留一个高耐心空位。最后 \(i=n\)，必须有 \(k=n-S_j\)，把剩余高耐心人以 \(k!\) 方式填入；只累加 \(j\le n-m\)。每一组人的姓名恰算一次。

提示6-自己动手检查

我会先测耐心0、耐心恰等于已失败人数、全容易题和全难题。两人耐心相同仍是不同人，组合与阶乘必须保留姓名分配数。

代码-12分

仅用于 \(m=1\)，覆盖点12～14。把不录用的排列数从 \(n!\) 中减去。容易题日的耐心上限为 \(i-1\)，难题日设为 \(n\)；按上限升序，允许的人集合嵌套，每次用“可选人数−已选人数”。时间 \(O(n^2)\)。

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 998244353;

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> patience(n), limits(n);
    for (int &x : patience) cin >> x;
    for (int i = 0; i < n; i++) limits[i] = s[i] == '1' ? i : n;
    sort(limits.begin(), limits.end());
    long long all = 1, none = 1;
    for (int i = 1; i <= n; i++) all = all * i % MOD;
    for (int i = 0; i < n; i++) {
        // 我按上限从小到大处理，已选的人都在当前允许集合里，才可以直接减去 i。
        int eligible = 0;
        for (int x : patience) if (x <= limits[i]) eligible++;
        none = none * max(0, eligible - i) % MOD;
    }
    cout << (all - none + MOD) % MOD;

    return 0;
}

代码-满分

时间 \(O(n^3)\)，空间 \(O(n^2)\)，滚动掉天数维。不是 \(O(n^4)\)：对所有 \(j\) 累加 \(\mathrm{cnt}[j+1]\) 仅为 \(n\)，\(l\) 循环总量受耐心分组数量限制。剪掉失败数 \(>n-m\) 或空位数超过可用高耐心人数的状态。

#include <bits/stdc++.h>

using namespace std;

const int N = 505, MOD = 998244353;
int choose[N][N], factorial[N], countPatience[N], prefix[N];
int dp[N][N], nextDp[N][N];

void add(int &target, long long value) {
    target = (target + value) % MOD;
}

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        countPatience[c]++;
    }
    factorial[0] = 1;
    for (int i = 0; i <= n; i++) {
        choose[i][0] = choose[i][i] = 1;
        for (int j = 1; j < i; j++) choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % MOD;
        if (i) factorial[i] = 1LL * factorial[i - 1] * i % MOD;
        prefix[i] = countPatience[i] + (i ? prefix[i - 1] : 0);
    }
    dp[0][0] = 1;
    for (int day = 0; day < n; day++) {
        memset(nextDp, 0, sizeof nextDp);
        for (int failed = 0; failed <= min(day, n - m); failed++) {
            int highCount = n - prefix[failed];
            for (int slots = 0; slots <= min(day, highCount); slots++) {
                long long ways = dp[failed][slots];
                if (!ways) continue;
                if (s[day] == '1' && slots < highCount) add(nextDp[failed][slots + 1], ways);
                if (failed == n - m) continue;
                for (int filled = 0; filled <= min(slots, countPatience[failed + 1]); filled++) {
                    long long coefficient = 1LL * choose[slots][filled] * choose[countPatience[failed + 1]][filled] % MOD;
                    coefficient = coefficient * factorial[filled] % MOD * ways % MOD;
                    int leftSlots = slots - filled;
                    int available = (s[day] == '1' ? prefix[failed] : prefix[failed + 1] - filled) - (day - slots);
                    if (available > 0) add(nextDp[failed + 1][leftSlots], coefficient * available % MOD);
                    // 我先留高耐心人的位置，姓名在分组填位时统一计数；现在再乘人数会重复计算。
                    if (s[day] == '0' && leftSlots < n - prefix[failed + 1]) add(nextDp[failed + 1][leftSlots + 1], coefficient);
                }
            }
        }
        memcpy(dp, nextDp, sizeof dp);
    }
    long long answer = 0;
    for (int failed = 0; failed <= n - m; failed++) {
        int slots = n - prefix[failed];
        answer = (answer + 1LL * dp[failed][slots] * factorial[slots]) % MOD;
    }
    cout << answer;

    return 0;
}