CSP2025提高组题解

T1【贪心、排序】社团招新 / club

题意概括

给定 $t$ 组数据。每组 $n$ ($n$ 为偶数) 个人，每个人 $i$ 分配到部门 $j \in \{1, 2, 3\}$ 有满意度 $a_{i,j}$。求一种分配方案 $d_i \in \{1, 2, 3\}$，使得总满意度 $\sum_{i=1}^{n} a_{i,d_i}$ 最大，且满足 $\forall j \in \{1, 2, 3\}$，分配到部门 $j$ 的人数 $c_j \le n/2$。 数据范围：$1 \le t \le 5$, $2 \le n \le 10^5$, $0 \le a_{i,j} \le 2 \times 10^4$。

题目分析

这是一个带约束的最优化问题。首先，注意到 $n$ 为偶数，且 $\sum_{j=1}^3 c_j = n$。若存在某个部门 $k$ 使得 $c_k > n/2$，则对于任意 $l \ne k$，必有 $c_l \le n - c_k < n - n/2 = n/2$。因此，至多只有一个部门的人数会超过 $n/2$ 的限制。

我们可以采用一种反悔贪心策略。首先，不考虑 $c_j \le n/2$ 的限制，让每个人 $i$ 都选择使其满意度最大的部门。设 $p_{i,1} = \max_j a_{i,j}$ 为其最大满意度（假设在部门 $k$ 取到），$p_{i,2} = \max_{j \ne k} a_{i,j}$ 为其次大满意度。计算初始总满意度 $S = \sum_{i=1}^n p_{i,1}$，并统计每个部门 $j$ 的选择人数 $c_j$。

若 $\forall j, c_j \le n/2$，则 $S$ 即为最优解。

若存在某个部门 $k$ 使得 $c_k > n/2$（由上述分析，这样的 $k$ 至多一个），我们必须从部门 $k$ 中移出 $c_k - n/2$ 个人到他们的次优选择。为了使总满意度损失最小，我们应选择那些 "反悔代价" 最小的人。对于每个最初选择了部门 $k$ 的人 $i$，其反悔代价（即移到次优部门的满意度损失）定义为 $\Delta_i = p_{i,1} - p_{i,2}$。我们将所有最初选择 $k$ 的人的 $\Delta_i$ 收集起来，进行升序排序。然后，从 $S$ 中减去最小的 $c_k - n/2$ 个 $\Delta_i$ 值。 即 $S_{ans} = S - \sum \Delta_{\min(c_k - n/2)}$。 最终 $S_{ans}$ 即为所求的最大满意度。

时间复杂度：$O(t \cdot n \log n)$（主要瓶颈在于排序）。 空间复杂度：$O(n)$（用于存储反悔代价）。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    // v[i] 存储所有首选部门为 i 的人的 "反悔代价"
    // (即 p_1 - p_2)
    vector<int> v[3];
    ll sum = 0; // 总满意度

    for (int i = 0; i < n; ++i) {
        pair<int, int> p[3]; // {满意度, 部门编号}
        for (int j = 0; j < 3; ++j) {
            cin >> p[j].first;
            p[j].second = j;
        }

        // 按满意度降序排序
        sort(p, p + 3, greater<pair<int, int>>());

        sum += p[0].first; // 累加最大满意度
        int bst = p[0].second; // 最佳部门
        int rgt = p[0].first - p[1].first; // 反悔代价

        v[bst].push_back(rgt);
    }

    for (int k = 0; k < 3; ++k) {
        int siz = v[k].size();
        if (siz > n / 2) {
            // 该部门人数超过 n/2
            sort(v[k].begin(), v[k].end()); // 按反悔代价升序排序

            int dif = siz - n / 2; // 需要移出的人数
            for (int i = 0; i < dif; ++i) {
                sum -= v[k][i]; // 减去最小的 k 个反悔代价
            }
        }
    }

    cout << sum << '\n';
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        sol();
    }
    return 0;
}

T2【最小生成树、状态压缩、Kruskal】 道路修复 / road

题意概括

给定一个 $n$ 个点 $m$ 条边的无向图，边 $i$ 连接 $u_i, v_i$，修复代价 $w_i$。保证原图 $n$ 个点连通。 另有 $k$ 个乡镇，选择激活第 $j$ 个乡镇需 $c_j$ 代价，激活后可建边 $(j, i)$（$i \in [1, n]$），代价 $a_{j,i}$。 目标是选择激活哪些乡镇（可不选），并修复/新建哪些边，使得 $n$ 个原城市点集 $[1, n]$ 连通，且总代价最小。 数据范围：$1 \le n \le 10^4$, $1 \le m \le 10^6$, $0 \le k \le 10$。代价 $\le 10^9$。

题目分析

本题的核心是求解一个图的最小生成树 (MST) 问题，但图中包含 $k$ 个可选的 "Steiner 点"（乡镇）。$k \le 10$ 这一关键约束提示我们可以采用 $O(2^k)$ 的状态压缩或枚举。

我们枚举 $k$ 个乡镇是否激活的所有 $2^k$ 种状态。 设 $S$ 为当前枚举的被激活乡镇的集合。 当 $S = \emptyset$ 时，问题退化为在原图 $G_0 = (\{1..n\}, E_m)$ 上求 MST。我们使用 Kruskal 算法求出 $G_0$ 的 MST $T_0$，其代价 $W_0 = \text{cost}(T_0)$ 是一个答案的初始上界。

当 $S \ne \emptyset$ 时，我们构建一个新图 $G_S$。$G_S$ 的点集 $V_S = \{1, \ldots, n\} \cup \{n+j \mid j \in S\}$。$G_S$ 的边集 $E_S$ 包含 $m$ 条原图的边，以及所有 $j \in S$ 对应的 $n$ 条乡镇-城市边 $(n+j, i)$（代价 $a_{j,i}$）。 我们要求 $G_S$ 的 MST，设其代价为 $M_S$。则当前状态 $S$ 的总代价为 $(\sum_{j \in S} c_j) + M_S$。 最终答案为 $\min_{S \subseteq \{1..k\}} \{ (\sum_{j \in S} c_j) + \text{cost}(\text{MST}(G_S)) \}$。

直接 $2^k$ 次执行 Kruskal，每次涉及 $M' = O(m + nk)$ 条边，总复杂度为 $O(2^k \cdot M' \log M')$，无法通过。

优化： 我们利用 MST 的一个关键性质（Cut Property / Kruskal's Algorithm Correctness）：$\text{MST}(E_m \cup E_S)$ 包含的 $E_m$ 中的边，一定是 $\text{MST}(E_m)$ 的子集。即 $\text{MST}(E_m \cup E_S) \subseteq \text{MST}(E_m) \cup E_S$。 证明：任何不在 $\text{MST}(E_m)$ 中的边 $e \in E_m$，在 $\text{MST}(E_m)$ 中存在一条路径 $P$ 连接 $e$ 的两端，且 $P$ 中所有边的权值 $\le w(e)$。由于 $P \subseteq E_m \subseteq E_m \cup E_S$，当 Kruskal 算法（在 $E_m \cup E_S$ 上）考虑到 $e$ 时，$e$ 的两端必已连通，故 $e$ 不会被选。

优化后算法：

1. 计算原图 $G_0$ 的 MST $T_0$，得到 $n-1$ 条边 $E_0 = \text{edges}(T_0)$ 和初始答案 $ans = \text{cost}(T_0)$。复杂度 $O(m \log m)$。
2. 构建一个总边集 $E_{all} = E_0 \cup \bigcup_{j=1}^k \bigcup_{i=1}^n \{(i, n+j)\}$。$|E_{all}| = O(n-1 + nk) = O(nk)$。
3. 对 $E_{all}$ 按边权排序。复杂度 $O(nk \log(nk))$。
4. 枚举 $s \in [1, 2^k - 1]$（所有非空激活子集）： a. 计算激活代价 $C_S = \sum_{j \in S} c_j$。 b. 初始化 $n+k$ 个点的并查集。 c. 模拟 Kruskal：遍历排序后的 $E_{all}$。设当前边 $e=(u,v)$： i. 若 $e \in E_0$（$u,v \le n$），则该边可用。 ii. 若 $e$ 是乡镇边 $(i, n+j)$，当 $j \in S$ (即 $s$ 的 $j-1$ 位为 1) 时，该边可用。 iii. 若 $e$ 可用且 $u, v$ 不连通，则合并 $u, v$，并 $M_S += w(e)$。 d. 更新 $ans = \min(ans, C_S + M_S)$。
5. 输出 $ans$。

总时间复杂度：$O(m \log m + nk \log(nk) + 2^k \cdot nk \cdot \alpha(n+k))$。 空间复杂度：$O(m + nk)$。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 边结构体
struct edg {
    int u, v;
    ll w;

    // 排序比较
    bool operator<(const edg& o) const {
        return w < o.w;
    }
};

int n, m, k;
ll c[15]; // 乡镇激活代价
ll a[15][10005]; // 乡镇-城市建边代价
int f[20005]; // 并查集

vector<edg> e1; // 存储 m 条原始边
vector<edg> e0; // 存储 n-1 条原图 MST 边
vector<edg> es; // 存储 n-1 + nk 条总边集

// 查找根节点 (路径压缩)
int F(int x) {
    return f[x] == x ? x : f[x] = F(f[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        e1.push_back({u, v, w});
    }

    for (int j = 0; j < k; ++j) {
        cin >> c[j];
        for (int i = 1; i <= n; ++i) {
            cin >> a[j][i];
        }
    }

    // 1. 计算原图 MST (S = 空集)
    sort(e1.begin(), e1.end());
    for (int i = 1; i <= n; ++i) f[i] = i;

    ll ans = 0; // 初始答案
    int cnt = 0;
    for (auto& e : e1) {
        int x = F(e.u), y = F(e.v);
        if (x != y) {
            f[x] = y;
            ans += e.w;
            e0.push_back(e); // 保存 MST 边
            cnt++;
        }
    }
    
    // 2. 构建 O(nk) 的总边集 es
    es = e0;
    for (int j = 0; j < k; ++j) {
        for (int i = 1; i <= n; ++i) {
            // (城市 i, 乡镇 n+j+1)
            es.push_back({i, n + j + 1, a[j][i]});
        }
    }

    // 3. 排序总边集
    sort(es.begin(), es.end());

    // 4. 枚举 2^k - 1 种非空子集
    for (int s = 1; s < (1 << k); ++s) {
        ll cst = 0; // 激活代价
        ll mst = 0; // MST 代价

        // 初始化并查集 (n 个城市 + k 个乡镇)
        for (int i = 1; i <= n + k; ++i) f[i] = i;

        for (int j = 0; j < k; ++j) {
            if ((s >> j) & 1) {
                cst += c[j]; // 累加激活代价
            }
        }

        // 模拟 Kruskal
        for (auto& e : es) {
            int u = e.u, v = e.v;
            ll w = e.w;

            bool ok = false;
            if (v <= n) { // 是 e0 中的边 (u,v <= n)
                ok = true;
            } else {
                // 是乡镇边 (u <= n, v = n+j+1)
                int j = v - n - 1; // 乡镇编号 (0-based)
                if ((s >> j) & 1) { // 检查乡镇 j 是否在集合 S 中
                    ok = true;
                }
            }

            if (ok) {
                int x = F(u), y = F(v);
                if (x != y) {
                    f[x] = y;
                    mst += w;
                }
            }
        }
        ans = min(ans, cst + mst);
    }

    cout << ans << '\n';

    return 0;
}

T3【字符串哈希、字典树】谐音替换 / replace

题意概括

给定 $n$ ( $n \le 2 \times 10^5$ ) 对替换规则 $(s_{i,1}, s_{i,2})$，满足 $|s_{i,1}| = |s_{i,2}|$。给定 $q$ ( $q \le 2 \times 10^5$ ) 组询问 $(t_{j,1}, t_{j,2})$，满足 $t_{j,1} \neq t_{j,2}$。 一次替换定义为：若 $t_{j,1} = x + y + z$ 且 $y = s_{i,1}$，则 $s' = x + s_{i,2} + z$。 对每次询问，求有多少对 $(i, \text{pos})$（$i$ 为规则编号，$\text{pos}$ 为 $y$ 在 $t_{j,1}$ 中的起始位置）使得替换后 $s' = t_{j,2}$。 设 $L_1 = \sum (|s_{i,1}| + |s_{i,2}|) \le 5 \times 10^6$， $L_2 = \sum (|t_{j,1}| + |t_{j,2}|) \le 5 \times 10^6$。

题目分析

一个规则 $(s_1, s_2)$ 在 $t_1$ 的 $\text{pos}$ 处替换能得到 $t_2$，当且仅当 $t_1$ 和 $t_2$ 在 $[\text{pos}, \text{pos} + |s_1| - 1]$ 区间外完全相同，且在该区间内 $t_1$ 的子串为 $s_1$，$t_2$ 的子串为 $s_2$。 首先，若 $|t_{j,1}| \neq |t_{j,2}|$，则答案必为 $0$。 对于规则 $(s_{i,1}, s_{i,2})$，我们找到其最长公共前缀 (LCP) $p_i$ 和最长公共后缀 (LCS) $q_i$。设 $s_{i,1} = p_i + m_{i,1} + q_i$，$s_{i,2} = p_i + m_{i,2} + q_i$。如果 $s_{i,1} = s_{i,2}$ (即 $m_{i,1}=m_{i,2}$)，则该规则无效，因为 $t_{j,1} \neq t_{j,2}$。 对于询问 $(t_{j,1}, t_{j,2})$，我们也找到其 LCP $P_j$ 和 LCS $Q_j$。设 $t_{j,1} = P_j + M_{j,1} + Q_j$，$t_{j,2} = P_j + M_{j,2} + Q_j$。 一个规则 $i$ 能在 $\text{pos}$ 处产生贡献，当且仅当：

1. 核心差异部分完全匹配：$m_{i,1} = M_{j,1}$ 且 $m_{i,2} = M_{j,2}$。
2. LCP $p_i$ 匹配 $t_1$ 在 $M_{j,1}$ 之前的部分：$p_i$ 是 $P_j$ 的后缀。
3. LCS $q_i$ 匹配 $t_1$ 在 $M_{j,1}$ 之后的部分：$q_i$ 是 $Q_j$ 的前缀。 并且 $\text{pos}$ 必须满足 $\text{pos} = |P_j| - |p_i|$。 问题转化为：对每个询问 $j$，计数有多少规则 $i$ 满足 $(m_{i,1}, m_{i,2}) = (M_{j,1}, M_{j,2})$ 且 $p_i$ 是 $P_j$ 的后缀 且 $q_i$ 是 $Q_j$ 的前缀。 我们使用字符串哈希（双哈希）来标识核心串 $(m_{i,1}, m_{i,2})$。将所有规则和询问按此哈希值 $h$ 分组。 对每个哈希组 $h$，我们处理该组的所有规则 $S_h = \{(\text{rev}(p_i), q_i)\}$ 和所有询问 $T_h = \{(j, \text{rev}(P_j), Q_j)\}$。 问题变为：对每个询问 $j \in T_h$，求 $S_h$ 中有多少 $(\text{rev}(p_i), q_i)$ 满足 $\text{rev}(p_i)$ 是 $\text{rev}(P_j)$ 的前缀，且 $q_i$ 是 $Q_j$ 的前缀。 这是一个二维前缀匹配问题。我们可以离线处理：
4. 对该组 $h$，建立一个 TrieP 存储所有 $\text{rev}(p_i)$。
5. 用 std::map 或 TrieQ 离散化所有 $q_i$ 和 $Q_j$ 的所有前缀。设 $q_i$ 对应 $v_i$， $Q_j$ 的第 $k$ 个前缀对应 $v_{j,k}$。
6. 将规则 $i$ 的 $v_i$ 挂在 TrieP 中 $\text{rev}(p_i)$ 对应的节点 $u_i$ 上 ( w[u_i].push_back(v_i) )。
7. 将询问 $(j, v_{j,k})$ 挂在 $\text{rev}(P_j)$ 在 TrieP 上能走到的最深节点 $U_j$ 上 ( q[U_j].push_back({j, v_{j,k}}) )。
8. 在 TrieP 上进行 DFS。维护一个桶 cnt[]，cnt[v] 记录 $q$-Trie 节点 $v$ 在当前 DFS 路径上出现的次数。
9. dfs(u): a. for (v : w[u]) cnt[v]++; b. for ((j, v) : q[u]) ans[j] += cnt[v]; c. for (child c : u) dfs(c); d. for (v : w[u]) cnt[v]--; 遍历所有组，即可得到所有答案。 时间复杂度：$O(L_1 + L_2 + (n+q)\log(n+q))$ (使用 std::map 分组和离散化) 或 $O(L_1+L_2)$ (使用 unordered_map)。 空间复杂度：$O(L_1 + L_2)$ (Trie 和辅助数组)。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5000005; // 字符串总长
const int QN = 200005; // 询问数
const ll B1 = 131;
const ll M1 = 1000000007;
const ll B2 = 13331;
const ll M2 = 1000000009;

int n, q;
ll ans[QN];

// 哈希
pair<ll, ll> hsh(string s) {
    ll h1 = 0, h2 = 0;
    for (char c : s) {
        h1 = (h1 * B1 + c) % M1;
        h2 = (h2 * B2 + c) % M2;
    }
    return {h1, h2};
}

// 哈希 pair，用于 unordered_map
struct HSH {
    size_t operator()(const pair<ll, ll>& p) const {
        return p.first * 31 + p.second;
    }
};

// 规则
unordered_map<pair<ll, ll>, vector<pair<string, string>>, HSH> dat;
unordered_map<pair<ll, ll>, vector<tuple<int, string, string>>, HSH> qry;

// TrieP
int cp[N][26], tidp;
vector<int> w[N];
vector<pair<int, int>> qv[N];
// TrieQ (虚拟)
int cnt[N];

// 插入 TrieP
int insP(string s) {
    int u = 0;
    for (char x : s) {
        int &v = cp[u][x - 'a'];
        if (!v) v = ++tidp;
        u = v;
    }
    return u;
}

// 查找 TrieP
int wlkP(string s) {
    int u = 0;
    for (char x : s) {
        if (!cp[u][x - 'a']) return u;
        u = cp[u][x - 'a'];
    }
    return u;
}

void dfs(int u) {
    for (int v : w[u]) {
        cnt[v]++;
    }
    for (auto [j, v] : qv[u]) {
        ans[j] += cnt[v];
    }
    for (int i = 0; i < 26; i++) {
        if (cp[u][i]) {
            dfs(cp[u][i]);
        }
    }
    for (int v : w[u]) {
        cnt[v]--;
    }
}

// 获取子串
string gss(string& s, int l, int r) {
    if (l > r) return "";
    return s.substr(l, r - l + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    for (int i = 0; i < n; i++) {
        string s, t;
        cin >> s >> t;
        if (s == t) continue;

        int l = 0, r = s.length() - 1;
        while (l < s.length() && s[l] == t[l]) l++;
        while (r >= 0 && s[r] == t[r]) r--;

        string p = gss(s, 0, l - 1);
        string q = gss(s, r + 1, s.length() - 1);
        string m1 = gss(s, l, r);
        string m2 = gss(t, l, r);

        reverse(p.begin(), p.end());
        dat[hsh(m1 + "#" + m2)].push_back({p, q});
    }

    for (int j = 0; j < q; j++) {
        string s, t;
        cin >> s >> t;
        if (s.length() != t.length()) {
            ans[j] = 0;
            continue;
        }

        int l = 0, r = s.length() - 1;
        while (l < s.length() && s[l] == t[l]) l++;
        while (r >= 0 && s[r] == t[r]) r--;

        string p = gss(s, 0, l - 1);
        string q = gss(s, r + 1, s.length() - 1);
        string m1 = gss(s, l, r);
        string m2 = gss(t, l, r);

        reverse(p.begin(), p.end());
        qry[hsh(m1 + "#" + m2)].push_back({j, p, q});
    }

    set<pair<ll, ll>> keys;
    for (auto const& [key, val] : dat) keys.insert(key);
    for (auto const& [key, val] : qry) keys.insert(key);

    // 按组处理
    for (auto const& h : keys) {
        if (dat.find(h) == dat.end()) continue;

        tidp = 0;
        map<string, int> qid;
        int vcnt = 0;
        qid[""] = vcnt++; // 空前缀

        for (auto& [rp, qs] : dat[h]) {
            if (qid.find(qs) == qid.end()) {
                qid[qs] = vcnt++;
            }
        }
        if (qry.find(h) != qry.end()) {
            for (auto& [j, rp, qs] : qry[h]) {
                for (int k = 0; k <= qs.length(); k++) {
                    string pre = qs.substr(0, k);
                    if (qid.find(pre) == qid.end()) {
                        qid[pre] = vcnt++;
                    }
                }
            }
        }

        for (auto& [rp, qs] : dat[h]) {
            int u = insP(rp);
            int v = qid[qs];
            w[u].push_back(v);
        }

        if (qry.find(h) != qry.end()) {
            for (auto& [j, rp, qs] : qry[h]) {
                int u = wlkP(rp);
                for (int k = 0; k <= qs.length(); k++) {
                    string pre = qs.substr(0, k);
                    int v = qid[pre];
                    qv[u].push_back({j, v});
                }
            }
        }

        dfs(0);

        // 清理当前组的 Trie
        for (int i = 0; i <= tidp; i++) {
            memset(cp[i], 0, sizeof(cp[i]));
            w[i].clear();
            qv[i].clear();
        }
        // cnt 已经在 dfs 中清零
    }

    for (int j = 0; j < q; j++) {
        cout << ans[j] << "\n";
    }

    return 0;
}

T4【动态规划、组合计数】 员工招聘 / employ

题意概括

有 $n$ ($n \le 500$) 天，$n$ 个人，需要招聘 $\ge m$ 人。 每天 $i$ 的难度 $s_i \in \{0, 1\}$。$s_i=0$ 必拒绝，$s_i=1$ 必录用。 第 $i$ 个人 $p_i$ 的耐心 $c_{p_i}$ ($0 \le c_i \le n$)。 小 Z 安排 $n$ 天的面试顺序 $p$。 第 $i$ 天，面试 $p_i$。设 $j$ 为 $p_1 \dots p_{i-1}$ 中被拒绝或放弃的人数。 若 $j \ge c_{p_i}$， $p_i$ 放弃。 若 $j < c_{p_i}$ 且 $s_i=0$， $p_i$ 被拒绝。 若 $j < c_{p_i}$ 且 $s_i=1$， $p_i$ 被录用。 求录用 $\ge m$ 人的 $p$ 排列总数，模 $998244353$。

题目分析

我们按天 $i=1 \dots n$ 进行动态规划。核心是跟踪 "失败人数 $j$"，以及 $p_1 \dots p_i$ 中 $c_p$ 相对 $j$ 的分布。 定义 $dp[i][j][k]$ 为：

• $i$：已处理完前 $i$ 天的面试 ($p_1 \dots p_i$)。
• $j$：前 $i$ 天共产生了 $j$ 次失败 (拒绝或放弃)。
• $k$：在前 $i$ 天安排的 $i$ 个人中，有 $k$ 个人的 $c_p > j$。 $dp[i][j][k]$ 存储的是 $i-k$ 个 $c_p \le j$ 的人的排列方案数，以及 $k$ 个 $c_p > j$ 的位置安排方案数。 $c_p > j$ 的 $k$ 个人的具体排列将在最后 $fac[k]$ 计算。

记 $c[v]$ 为 $c_p = v$ 的人数，$pre[v]$ 为 $c_p \le v$ 的总人数。 状态 $dp[i-1][j][k]$ ( $i-1$ 天, $j$ 失败, $k$ 人 $c_p > j$ 已使用)

• 可用 $c_p \le j$: $A = pre[j] - (i-1-k)$
• 可用 $c_p \le j+1$: $A' = pre[j+1] - (i-1-k+t)$ ( $t$ 是 $k$ 个 $c_p>j$ 中 $c_p=j+1$ 的人)
• $com = C(c[j+1], t) \times P(k, t)$ ( $t$ 个 $c_p = j+1$ 的人插入 $k$ 个 $c_p > j$ 的位置)

转移 $dp[i-1][j][k] \to dp[i][\dots][\dots]$ (第 $i$ 天)：

1. $s_i = '1'$ (录用日):

   • 1.1. 安排 $p_i$ ( $c_p > j$ ) (占位符)。 $j$ 不变, $k \to k+1$。 $dp[i][j][k+1] \leftarrow dp[i-1][j][k]$
   • 1.2. 安排 $p_i$ ( $c_p \le j$ ) ( $A$ 种选择)。 $j \to j+1$ (放弃)。$k \to k-t$。 $dp[i][j+1][k-t] \leftarrow dp[i-1][j][k] \times com \times A$

2. $s_i = '0'$ (失败日): $j \to j+1$。

   • 2.1. 安排 $p_i$ ( $c_p \le j+1$ ) ( $A'$ 种选择)。 $k \to k-t$。 $dp[i][j+1][k-t] \leftarrow dp[i-1][j][k] \times com \times A'$
   • 2.2. 安排 $p_i$ ( $c_p > j+1$ ) (占位符)。 $k \to k-t+1$。 $dp[i][j+1][k-t+1] \leftarrow dp[i-1][j][k] \times com$

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 505;
const ll MOD = 998244353;

int n, m;
char s[N];
int c[N]; 
int pre[N]; 
ll dp[N][N][N]; // dp[i][j][k]: i 天, j 失败, k 人 c_p > j 已使用
ll C[N][N], P[N][N], fac[N];

ll qp(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return qp(a, MOD - 2);
}

void preC(int sz) {
    fac[0] = 1;
    for (int i = 1; i <= sz; i++) fac[i] = (fac[i - 1] * i) % MOD;

    C[0][0] = 1;
    for (int i = 1; i <= sz; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }

    for (int i = 0; i <= sz; i++) {
        P[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            P[i][j] = (P[i][j - 1] * (i - j + 1)) % MOD;
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> (s + 1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        c[x]++;
    }

    for (int i = 0; i <= n; i++) {
        pre[i] = (i == 0 ? c[0] : pre[i - 1] + c[i]);
    }

    preC(n); // 预处理

    dp[0][0][0] = 1; // 0 天, 0 失败, 0 人 c_p > 0 已使用

    for (int i = 1; i <= n; i++) { // 第 i 天
        for (int j = 0; j < i; j++) { // j 失败 (0...i-1)
            for (int k = 0; k < i; k++) { // k 人 c_p > j 已使用 (在 p_1...p_{i-1} 中)
                if (dp[i - 1][j][k] == 0) continue;

                ll v = dp[i - 1][j][k];
                int nxt = c[j + 1]; // N_{j+1}

                // A: Avail c_p <= j
                ll A = pre[j] - (i - 1 - k);
                
                if (s[i] == '1') { // 录用日
                    // 1.1. Pick B (c_p > j) -> 录用 (占位符)
                    // B = (n - pre[j]) - k
                    if ((n - pre[j]) - k > 0) {
                         dp[i][j][k + 1] = (dp[i][j][k + 1] + v) % MOD;
                    }
                   
                    // 1.2. Pick A (c_p <= j) -> 放弃 -> j+1
                    if (A > 0) {
                        for (int t = 0; t <= min(k, nxt); t++) {
                            ll com = (C[nxt][t] * P[k][t]) % MOD;
                            if (com == 0 && (k > 0 || nxt > 0) && t > 0) continue;
                            dp[i][j + 1][k - t] = (dp[i][j + 1][k - t] + v * A % MOD * com) % MOD;
                        }
                    }
                } else { // '0' 失败日 -> j+1
                    for (int t = 0; t <= min(k, nxt); t++) {
                        ll com = (C[nxt][t] * P[k][t]) % MOD;
                        if (com == 0 && (k > 0 || nxt > 0) && t > 0) continue;

                        // A': Avail c_p <= j+1
                        ll Ap = pre[j + 1] - (i - 1 - k + t);
                        // B': Avail c_p > j+1
                        ll Bp = (n - pre[j + 1]) - (k - t);

                        // 2.1. Pick A' (c_p <= j+1)
                        if (Ap > 0) {
                            dp[i][j + 1][k - t] = (dp[i][j + 1][k - t] + v * Ap % MOD * com) % MOD;
                        }
                        // 2.2. Pick B' (c_p > j+1) (占位符)
                        if (Bp > 0) {
                            dp[i][j + 1][k - t + 1] = (dp[i][j + 1][k - t + 1] + v * com) % MOD;
                        }
                    }
                }
            }
        }
    }

    ll ans = 0;
    for (int j = 0; j <= n - m; j++) { // j 失败
        int k = n - pre[j]; // 最终 k = n - pre[j] (所有 c_p > j 都用了)
        if (k < 0) continue;
        
        ans = (ans + dp[n][j][k] * fac[k]) % MOD;
    }

    cout << ans << "\n";

    return 0;
}

CSP-S 2025 题解

T1

省流

有 $n$ 个人（$n \le 10^5$ 且 $n$ 为偶数），需将每人分配到三个组（编号1, 2, 3）中的一个。将第 $i$ 个人分到第 $j$ 组的权值为 $a_{i,j}$。要求在每个组的人数都不能超过 $n/2$ 的前提下，求所有分配方案中权值总和的最大值。

思路

此问题为带约束的最优化问题。

首先，若不考虑“每组人数不超过 $n/2$”的约束，最优解显然是让每个人都选择使其权值最大的组。设此初始方案下形成的三组为 $A, B, C$，并按人数从多到少排序。

1. 最优情况: 如果 $|A| \le n/2$，那么此方案满足所有约束，必然是全局最优解，因为已经实现了个体最优的累加。

2. 调整情况: 如果 $|A| > n/2$，则此方案不合法，必须进行调整。此时，至少需要将 $|A| - n/2$ 个人从A组移出。

   核心引理: 在最终的最优解中，最多只有一个初始最优组（即A、B、C中的一个）的人数会少于其初始人数。

   简要论证: 假设在最优解中，某个初始组 $X$（例如B组）失去了一个本应属于它的成员 $u$（即 $u$ 的最优选择是 $X$）。除非 $X$ 组的人数已达到上限 $n/2$，否则将 $u$ 移回 $X$ 组必然会使总权值增加（或不变），从而得到一个更优（或等价）的解。因此，成员只会从人数超限的组（即A组）移出，而B组和C组在此过程中只会接收来自A组的成员，其自身初始成员不会流失。

基于此引理，算法策略变得清晰：当 $|A| > n/2$ 时，只需从A组中选择一部分人移动到B组或C组，以满足人数限制。为了使总权值损失最小，应当采取贪心策略。

算法流程

1. 对每个人 $i$，确定其最优分组（即令 $a_{i,j}$ 最大的组 $j$），并计算初始总权值。根据此分配，将人员划分为 $A, B, C$ 三组，并按人数降序排序。
2. 若 $|A| \le n/2$，当前方案即为最优解，输出总权值。
3. 若 $|A| > n/2$，需要从A组中移出 $|A| - n/2$ 个人。
   • 对于A组中的每个人，计算将其移动到其“次优”组（即B或C中对他权值较大的那个）所带来的权值损失。
   • 使用一个最小堆（优先队列）来维护A组所有成员的权值损失。
   • 重复执行 $|A| - n/2$ 次：从堆中取出权值损失最小的成员，将其从A组移动到对应的次优组，并从总权值中减去该损失。
4. 最终得到的总权值即为答案。

时间复杂度: $O(n \log n)$，瓶颈在于排序或优先队列的操作。

---

T2

省流

给定一张包含 $n$ 个点（$n \le 10^4$）和 $m$ 条边（$m \le 10^6$）的图。此外，还有 $k$ 个额外点（$k \le 10$）。每个额外点都与原图中的所有 $n$ 个点有边相连。所有边都具有非负整数权值。若方案中使用了某个额外点（即选择了与它相连的至少一条边），则需支付该点的额外非负整数点权。求使原图 $n$ 个点连通的最小总权值（边权和 + 额外点权和）。

思路

该问题是最小生成树（MST）的变体。当 $k=0$ 时，问题即为标准的MST问题。

由于 $k$ 的值非常小，自然联想到枚举与额外点相关的决策。我们可以暴力枚举所有 $2^k$ 种选择额外点的子集。

对于每个选定的额外点子集：

1. 将这些额外点及其连接到原图 $n$ 个点的所有边加入图中。
2. 计算此时新图的最小生成树。
3. 该方案的总成本为 MST 的权值加上所选额外点的点权之和。 全局最优解即为所有 $2^k$ 种方案中的最小成本。

直接对每种选择都运行一次完整的MST算法（如Kruskal）效率较低。可以进行优化：

• 边集优化: 任何不在原图（仅包含 $n$ 个点和 $m$ 条边）的MST中的边，只有当它的两个端点在MST中被权值更大的边连接时才可能有用。因此，我们可以预先计算原图的一个MST，在后续计算中，原图的边只需考虑构成该MST的 $n-1$ 条边即可。

算法流程

1. 预处理:

   • 对原图的 $m$ 条边运行Kruskal或Prim算法，求出其最小生成树 $T_0$。保留构成 $T_0$ 的 $n-1$ 条边。
   • 将这 $n-1$ 条边和每个额外点所带的 $n$ 条边分别进行排序，以便后续高效合并。

2. 枚举:

   • 遍历 $2^k$ 个额外点的子集。
   • 对于每一个子集 $S$： a. 计算 $S$ 中所有额外点的点权之和 cost_S。 b. 构建一个新图，包含原图的 $n$ 个点、子集 $S$ 中的额外点、原图MST ($T_0$) 的边以及 $S$ 中每个点到原图 $n$ 个点的所有边。 c. 在该新图上运行MST算法（如Kruskal或Prim），得到MST权值 mst_weight。 d. 更新全局最小总权值：min_total_cost = min(min_total_cost, cost_S + mst_weight)。

3. MST计算优化: 在每次迭代中，可以采用线性归并的方式合并已排序的边集，然后运行Kruskal算法。复杂度为 $O(SORT + 2^k \cdot kn \cdot \alpha(kn))$，其中 $SORT$ 是预处理排序的开销。

4. 增量式优化: 还可以通过动态规划或增量式构造的思想，在枚举额外点集时，基于一个小子集的MST结果，通过加入一个新额外点及其相关的 $n$ 条边来更新MST。这可以将每次迭代的复杂度从 $O(kn \log)$ 级别降低到 $O(n)$ 级别。

最终时间复杂度:

• Kruskal实现: $O(m\log m + kn\log n + 2^k kn\alpha(kn))$
• 增量式Prim实现: $O(m\log m + kn\log n + 2^k n)$

---

T3

省流

给定 $n$ ($n\le 2\times 10^5$) 对等长的字符串 $(s_{i,1}, s_{i,2})$ 作为替换规则。有 $q$ ($q\le 2\times 10^5$) 次询问，每次询问给出一对字符串 $(t_{1}, t_{2})$，要求计算有多少个规则 $j$，能通过在 $t_1$ 中找到某次出现的子串 $s_{j,1}$，并将其原地替换为 $s_{j,2}$ 后，恰好得到字符串 $t_2$。规定替换操作只能进行一次，且保证询问的 $t_1 \ne t_2$。所有 $s$ 相关字符串和 $t$ 相关字符串的总长度分别不超过 $5\times 10^6$。

解题思路与算法

一个规则 $(s_{j,1}, s_{j,2})$ 能够将 $t_1$ 转换为 $t_2$ 当且仅当存在一个前缀字符串 $P$ 和一个后缀字符串 $S$，使得：

• $t_1 = P + s_{j,1} + S$
• $t_2 = P + s_{j,2} + S$

这意味着 $t_1$ 和 $t_2$ 的差异完全由 $s_{j,1}$ 替换为 $s_{j,2}$ 解释。

核心问题转化： 对于一个询问 $(t_1, t_2)$，我们可以先找到它们的最长公共前缀 (LCP) 和最长公共后缀 (LCS)。

• $t_1 = \text{LCP}(t_1, t_2) + t'_1 + \text{LCS}(t_1, t_2)$
• $t_2 = \text{LCP}(t_1, t_2) + t'_2 + \text{LCS}(t_1, t_2)$

问题转化为：计算有多少个规则 $(s_{j,1}, s_{j,2})$，使得存在前缀 $P'$ 和后缀 $S'$ 满足：

• $t'_1 = P' + s_{j,1} + S'$
• $t'_2 = P' + s_{j,2} + S'$

这依然是一个复杂的对齐子串匹配问题。一个更高效的思路是利用字符串数据结构进行批量处理。

算法1：基于AC自动机

1. 将问题看作一个“二维”或“成对”的字符串匹配。对于每个规则 $(s_{j,1}, s_{j,2})$ 和询问 $(t_1, t_2)$，构造一个“对偶串”，其中每个字符是一个二元组。例如，将 (abc, abd) 构造成 [(a,a), (b,b), (c,d)]。
2. 找到每个对偶串中第一个和最后一个不匹配的位置。将不匹配的核心部分以及其前后的匹配部分作为特征串。
3. 一个规则能匹配一个询问，当且仅当规则的特征串是询问特征串的“对齐子串”。
4. 这个问题可以通过在所有规则的特征串上建立一个AC自动机来解决。然后将每个询问的特征串在自动机上匹配，统计沿途 fail 链上的有效模式数量。

算法2：基于字典树（Trie）和离线处理

1. 对于每个询问 $(t_1, t_2)$，找到第一个不同位置 $L$ 和最后一个不同位置 $R$。
2. 对于每个规则 $(s_1, s_2)$，找到第一个不同位置 $l$ 和最后一个不同位置 $r$。
3. 一个规则 $(s_1, s_2)$ 能在 $t_1$ 的 $p$ 位置完成替换，必须满足：
   • 替换窗口 $[p, p+|s_1|-1]$ 必须完整覆盖差异区间 $[L, R]$。
   • $t_1$ 在该窗口内的子串等于 $s_1$。
   • $t_2$ 在该窗口内的子串等于 $s_2$。
   • $t_1$ 和 $t_2$ 在窗口外完全相同。
4. 这等价于：$s_1$ 的前缀 $s_1[0..l-1]$ 是 $t_1[p..L-1]$ 的后缀；$s_1$ 的后缀 $s_1[r+1..]$ 是 $t_1[R+1..p+|s_1|-1]$ 的前缀；并且核心部分完全匹配。
5. 可以将此问题离线化：
   • 对所有规则和询问的所需前缀（反转后）和后缀建立字典树。
   • 使用字符串哈希或字典树节点编号来唯一标识每个核心串、前缀和后缀。
   • 将问题转化为：查询有多少规则 $s$ 满足其（前缀哈希，核心哈希，后缀哈希）与询问 $t$ 的某个对齐子串匹配。
   • 这可以进一步通过在字典树上进行DFS，同时用树状数组或哈希表维护路径信息来高效统计。

时间复杂度：使用哈希表或优化过的Trie/AC自动机，理论时间复杂度可达 $O(\sum|s| + \sum|t|)$。

T4

省流

输入 $n, m \le 500$，一个长度为 $n$ 的01序列 $s$，以及一个长度为 $n$ 的数列 $\{c_i\}$。 对一个 $n$ 阶排列 $p$，定义第 $i$ 个人在时刻 $p^{-1}_i$ 到达。一个人 $i$ 被“录用”的条件是：

1. 其所在位置 $k = p^{-1}_i$ 满足 $s_k=1$。
2. 在其之前到达的所有人中（即位于位置 $j < k$ 的人），未被录用的人数严格小于 $c_i$。

任务是计数满足“录用人数 $\ge m$”的排列 $p$ 的个数，结果对 $998244353$ 取模。

解题思路与算法

这是一个与排列和动态条件相关的计数问题，适合使用动态规划。

首先，一个关键的观察是，录用条件只与人的 $c_i$ 值和其在排列中的位置有关，而与人的具体编号 $i$ 无关。因此，问题可以转化为：将多重集 $\{c_1, \dots, c_n\}$ 填入到 $1, \dots, n$ 的位置中，形成一个序列 $q_1, \dots, q_n$（其中 $q_k$ 是被放在位置 $k$ 的人的 $c$ 值），然后统计满足条件的序列 $q$ 的数量。

核心洞察与简化

• 位置 $k$ 若 $s_k=0$，则此处的人必定不被录用。
• 引理: 位于位置 $k$、耐心值为 $q_k$ 的人的录用条件，等价于“在他之前 $j<k$ 的 $s_j=0$ 的位置数，加上在他之前 $j<k$ 且 $s_j=1$ 的位置中、耐心值 $q_j < q_k$ 且未被录用的人数之和，严格小于 $q_k$”。
• 这个引理的本质是，如果一个耐心值大的人因为未录用人数达到阈值而被拒绝，那么对于一个后续出现的耐心值更小的人，同样的未录用人数也一定会使其被拒绝。因此，在判断一个人的录用情况时，可以忽略掉在他之前但耐心值比他更大的人是否被录用。

这个性质提示我们应该按照 $c$ 值从小到大的顺序来安排人，即进行DP。

动态规划设计 按 $c$ 值从小到大处理所有的人。

• 状态定义: $f[i][j][k]$ 表示考虑完所有 $c \le i$ 的人之后：

  • $j$ 是第一个满足“在 $1 \dots j-1$ 位置中，未被录用且 $c \le i$ 的人数等于 $i+1$”的位置。换言之，$j$ 是对于任何一个 $c > i$ 的人来说，如果他被放在 $j$ 或之后的位置，他肯定不会因为 $c \le i$ 的未录用者而被拒绝。
  • $k$ 是已被放置的、$c \le i$ 的人中，位于 $\ge j$ 且 $s=1$ 的位置上的人数。
  • $f[i][j][k]$ 的值是满足此状态的方案数（只考虑了 $c \le i$ 的人的放置方式）。

• 转移: DP的转移发生在从考虑完 $c \le i$ 的人到考虑完 $c \le i+1$ 的人。假设有 $N_{i+1}$ 个 $c$ 值为 $i+1$ 的人，我们需要将他们放入剩余的空位中。根据他们被放入的位置（$<j$ 或 $\ge j$，$s=1$ 或 $s=0$），会更新“失败点” $j$ 和后续人数 $k$。转移过程涉及组合数计算，可以通过预处理前缀和等技巧进行优化。

• 答案统计: 在DP的最后一步（即考虑完所有 $c$ 值），统计所有状态 $f[\max(c)][j][k]$。对于一个最终状态，总录用人数为（所有 $s=1$ 的位置总数）-（最终未录用人数）。我们累加所有录用人数 $\ge m$ 的状态的方案数。

时间复杂度: 状态数为 $O(n \cdot n \cdot n) = O(n^3)$。每次转移需要枚举新放置的人的分配情况，若直接枚举则复杂度较高。但通过数学方法和预计算组合数、前缀和，可以将转移的均摊复杂度优化到 $O(1)$，使得总时间复杂度为 $O(n^3)$。