2025CSP-S复赛解析

Meunderthesunset · 2025-11-16 11:18:17 · 题解

T1：P14361 [CSP-S 2025] 社团招新 / club（官方数据）

解析

首先不考虑每个人数限制，让所有人根据自己的喜好，选择满意度最高的部门，此时算得的满意度之和即为最理想的答案，接下来我们考虑如何调度人员，可以在损失满意度最少的情况下，满足各部门的人数限制。假设目前人数最多的部门中共有 x 人（显然，至多只有一个部门的人数会超过限制），我们改变其中 (x-\frac{n}{2}) 个人的意愿，将他们安排到其他部门。显然，这一操作也不会导致其他部门的人数过多。因而只需统计人数最多的部门中，所有人最大满意度与次大满意度之差（改变其部门的最小代价），找到部门中最小的 (x-\frac{n}{2}) 个人并将其换到第二喜欢的部门即可。

答案

#include <bits/stdc++.h>
#define ll long long
#define N 100100
using namespace std;

ll T, n, del[N];
struct Num
{
    ll a, b, c;
} num[N];

inline bool cmp(ll u, ll v) { return del[u] < del[v]; }
int main()
{
    cin >> T;
    while (T--)
    {
        ll ans = 0;
        vector<ll> A, B, C; // 表示各部门中包含哪些成员
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld%lld", &num[i].a, &num[i].b, &num[i].c);
            ll mx = max({num[i].a, num[i].b, num[i].c});
            // 计算最大值，并根据最大值选择其部门
            if (num[i].a == mx)
            {
                A.push_back(i);
                del[i] = mx - max(num[i].b, num[i].c);
            }
            else if (num[i].b == mx)
            {
                B.push_back(i);
                del[i] = mx - max(num[i].a, num[i].c);
            }
            else
            {
                C.push_back(i);
                del[i] = mx - max(num[i].a, num[i].b);
            }
            ans += mx;
        }
        if (A.size() > n / 2) // 第一个部门超标，找到最小的 x-n/2 人改变志愿
        {
            sort(A.begin(), A.end(), cmp);
            for (int i = 0; i < A.size() - n / 2; i++)
                ans -= del[A[i]];
        }
        if (B.size() > n / 2) // 第二个部门超标，找到最小的 x-n/2 人改变志愿
        {
            sort(B.begin(), B.end(), cmp);
            for (int i = 0; i < B.size() - n / 2; i++)
                ans -= del[B[i]];
        }
        if (C.size() > n / 2) // 第三个部门超标，找到最小的 x-n/2 人改变志愿
        {
            sort(C.begin(), C.end(), cmp);
            for (int i = 0; i < C.size() - n / 2; i++)
                ans -= del[C[i]];
        }
        printf("%lld\n", ans);
    }
}

T2：P14362 [CSP-S 2025] 道路修复 / road（官方数据）

解析

我们考虑使用 kruskal 算法计算最小生成树的过程，对于最开始的边集，尽管它包含了 (10^6) 条边，但我们将其排序之后，直接执行一遍 kruskal 算法，那么，只有最终出现在最小生成树上的那些边才有用，而其余的被抛弃的边，不管添加了任何的新城镇，这些边仍然不会出现。由于 (n=10^4)，那么我们只保留 n 条边，随后枚举任何可能出现的选择城镇集合，能达到 (O(nk2^k log(n))) 的复杂度。随后，我们考虑到直接枚举任何可能出现的集合，其实有大量的重复计算，我们改用 dfs 来搜索可行集合，每次加入一个新点的时候，就只需要加入 n 条新边，随后我们再按照同样的思路保留关键边，这样我们的最终复杂度就只有 (O(n2^k\log(n))) 了。

答案

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

struct DSU
{
    vector<int> fa;
    DSU(int n) : fa(n)
    {
        iota(fa.begin(), fa.end(), 0);
    }
    int getfa(int x)
    {
        return fa[x] == x ? x : fa[x] = getfa(fa[x]);
    }
    bool unite(int x, int y)
    {
        x = getfa(x), y = getfa(y);
        if (x == y)
            return false;
        fa[x] = y;
        return true;
    }
};

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<array<int, 3>> edges(m);
    for (auto &[w, u, v] : edges)
    {
        cin >> u >> v >> w;
        --u, --v;
    }
    vector ex(k, vector(n, array<int, 3>{}));
    vector<int> c(k);
    for (int i = 0; i < k; i++)
    {
        cin >> c[i];
        for (int j = 0; j < n; j++)
        {
            cin >> ex[i][j][0];
            ex[i][j][1] = j, ex[i][j][2] = n + i;
        }
        sort(ex[i].begin(), ex[i].end());
    }
    sort(edges.begin(), edges.end());
    DSU dsu(n + k);
    ll sum = 0;
    vector<array<int, 3>> new_edges;
    int blocks = n;
    for (auto [w, x, y] : edges)
    {
        if (dsu.unite(x, y))
        {
            sum += w;
            new_edges.push_back({w, x, y});
            --blocks;
        }
    }
    ll ans = sum;
    auto search = [&](auto &&self, int dep, int cnt, ll exc, vector<array<int, 3>> edges) -> void
    {
        if (dep == k)
        {
            return;
        }
        self(self, dep + 1, cnt, exc, edges);
        ++cnt, exc += c[dep];
        edges.insert(edges.end(), ex[dep].begin(), ex[dep].end());
        inplace_merge(edges.begin(), edges.begin() + edges.size() - n, edges.end());
        DSU dsu(n + k);
        int blocks = n + cnt;
        ll now_cost = exc;
        vector<array<int, 3>> new_edges;
        for (auto [w, x, y] : edges)
        {
            if (dsu.unite(x, y))
            {
                now_cost += w;
                new_edges.push_back({w, x, y});
                --blocks;
            }
        }
        if (blocks == 1)
        {
            ans = min(ans, now_cost);
        }
        self(self, dep + 1, cnt, exc, new_edges);
    };
    search(search, 0, 0, 0, new_edges);
    cout << ans << "\n";
    return 0;
}

P14363 [CSP-S 2025] 谐音替换 / replace（官方数据）

解析

我们注意到不管是数据还是询问，只要能对上，那肯定是前缀相同后缀相同，中间有一段不同的修改，我们预处理出每一对中间的实际转换的内容，容易发现，实际产生贡献的询问和转换串，中间的修改肯定是完全相同的，而转换串两边的前后缀分别是询问串前缀的后缀和后缀的前缀，也就是被包含在询问串的中间。那么，我们对中间的转换哈希一下，然后对于任何中间相同的串，我们对前缀和后缀分别建好 trie，这样对每个询问，就相当于查询两边的 trie 上都是当前点的祖先的点有几个。对于这个问题，我们可以对 trie 计算 dfs 序之后将其转换为二维数点问题，使用树状数组即可维护，最终的总复杂度为 (O(|S|+|T|+(q+n)\log(q+n))) 。

答案

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

using i64 = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;

const i64 P = 1'000'000'000'000'000'003, b = 1'000'000'007;
i64 get_hash(string s)
{
    i64 v = 0;
    for (auto x : s)
        v = (i128(v) * b + x) % P;
    return v;
}

const int N = 200005;
int n, q, ans[N];
string s1[N], s2[N], t1[N], t2[N];
i64 vs[N], vt[N];
pii os[N], ot[N];
map<i64, vector<int>> ms, mt;

const int M = 2500005;
int ch[M][26], tot, dfn, ord[M], ed[M];
void clear()
{
    while (tot)
    {
        memset(ch[tot], 0, sizeof ch[tot]);
        --tot;
    }
    tot = 2;
    dfn = 0;
}
int insert(int p, const string &s)
{
    for (auto c : s)
    {
        int &q = ch[p][c - 'a'];
        if (!q)
            q = ++tot;
        p = q;
    }
    return p;
}
int get_id(int p, const string &s)
{
    for (auto c : s)
    {
        int q = ch[p][c - 'a'];
        if (q)
        {
            p = q;
        }
        else
        {
            break;
        }
    }
    return p;
}

i64 work(string &s1, string &s2)
{
    int n = s1.length();
    int l = 0, r = n - 1;
    while (l < n && s1[l] == s2[l])
        ++l;
    if (l == n)
        return 0;
    while (s1[r] == s2[r])
        --r;
    assert(l <= r);
    i64 v = get_hash(s1.substr(l, r - l + 1) + s2.substr(l, r - l + 1));
    s1 = s2.substr(0, l);
    reverse(s1.begin(), s1.end());
    s2 = s2.substr(r + 1, n - r - 1);
    return v;
}

void dfs(int u)
{
    ord[u] = ++dfn;
    for (int c = 0; c < 26; ++c)
    {
        if (ch[u][c])
            dfs(ch[u][c]);
    }
    ed[u] = dfn;
}

namespace BIT
{
    int c[M];
    void clear()
    {
        memset(c + 1, 0, tot * 4);
    }
    void modify(int p, int x)
    {
        for (; p <= tot; p += p & -p)
            c[p] += x;
    }
    void modify(int l, int r, int x)
    {
        modify(l, x);
        modify(r + 1, -x);
    }
    int query(int p)
    {
        int res = 0;
        for (; p; p -= p & -p)
            res += c[p];
        return res;
    }
}

struct node
{
    int x, y, z;
    node() {}
    node(int x, int y, int z) : x(x), y(y), z(z) {}
};
vector<node> mdf[M];
vector<pii> qry[M];

void add_mdf(int l1, int r1, int l2, int r2)
{
    mdf[l1].emplace_back(l2, r2, 1);
    mdf[r1 + 1].emplace_back(l2, r2, -1);
}
void add_qry(int x, int y, int id)
{
    qry[x].emplace_back(y, id);
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    {
        cin >> s1[i] >> s2[i];
        vs[i] = work(s1[i], s2[i]);
        ms[vs[i]].push_back(i);
    }
    for (int i = 1; i <= q; ++i)
    {
        cin >> t1[i] >> t2[i];
        if (t1[i].length() != t2[i].length())
            continue;
        vt[i] = work(t1[i], t2[i]);
        mt[vt[i]].push_back(i);
    }

    // cerr << "?" << endl;

    for (const auto &[v, a] : ms)
    {
        if (!mt.count(v))
            continue;
        const auto &b = mt[v];
        assert(v);
        clear();
        for (auto i : a)
        {
            os[i] = pii(insert(1, s1[i]), insert(2, s2[i]));
        }
        for (auto i : b)
        {
            ot[i] = pii(get_id(1, t1[i]), get_id(2, t2[i]));
        }
        dfs(1), dfs(2);

        // cerr << "? " << v << " " << tot << " " << dfn << endl;

        for (int i = 1; i <= dfn; ++i)
            mdf[i].clear(), qry[i].clear();
        for (auto i : a)
        {
            auto [u, v] = os[i];
            add_mdf(ord[u], ed[u], ord[v], ed[v]);
        }
        for (auto i : b)
        {
            auto [u, v] = ot[i];
            add_qry(ord[u], ord[v], i);
        }

        BIT::clear();
        for (int i = 1; i <= dfn; ++i)
        {
            for (auto [l, r, x] : mdf[i])
                BIT::modify(l, r, x);
            for (auto [x, id] : qry[i])
                ans[id] = BIT::query(x);
        }
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";

    return 0;
}

T4：P14364 [CSP-S 2025] 员工招聘 / employ（官方数据）

解析

令 (h_i)( 表示前 i 天中，难度较高的天数的数量。令 (f_i) 表示 (c_j) 小于等于 i 的 j 的数量。我们考虑对于难度较高的天，先不分配具体是谁参加面试。最后答案乘以 (h_n!) 即可。令 (g_{i, j, k}) 表示前 i 天中，有 j 天是不录用人的，且剩下 (i-j) 天中有 k 天是没有确定具体是谁去面试的方案数。我们称 (c_k \leq j) 的人为 “弱人”，其它人为 “强人”。若 (s_{i + 1} = 0)，(g_{i + 1, j + 1, k - l} += g_{i, j, k} * \binom{c_{j + 1} - c_{j}}{l} * \binom{k}{l} * l!)。若 (s_{i + 1} = 1)，且下一天录用人，(g_{i + 1, j, k + 1} += g_{i, j, k}) 。若 (s_{i + 1} = 1)，且下一天不录用人， (g_{i + 1, j + 1, k - l} += g_{i, j, k} * (f_j - (j - h_i)) * \binom{c_{j + 1} - c_j}{l} * \binom{k}{l} * l!)。时间复杂度 (O(n^3))。

答案

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;

template <int P>
struct ModInt {
    int x;
    static int shift(int x) {
        while (x < 0) x += P;
        while (x >= P) x -= P;
        return x;
    }
    ModInt(int x = 0) : x(shift(x)) {}
    ModInt& operator+=(const ModInt &other) {
        if ((x += other.x) >= P) x -= P;
        return *this;
    }
    ModInt& operator-=(const ModInt &other) {
        if ((x -= other.x) < 0) x += P;
        return *this;
    }
    ModInt& operator*=(const ModInt &other) {
        x = (ll)x * other.x % P;
        return *this;
    }
    friend ModInt operator+(ModInt a, const ModInt &b) {
        return a += b;
    }
    friend ModInt operator-(ModInt a, const ModInt &b) {
        return a -= b;
    }
    friend ModInt operator*(ModInt a, const ModInt &b) {
        return a *= b;
    }
    ModInt pow(ll exp) const {
        ModInt res = 1, base = *this;
        while (exp) {
            if (exp & 1) res = res * base;
            base = base * base;
            exp >>= 1;
        }
        return res;
    }
    ModInt inv() const {
        return pow(P - 2);
    }
};
using Mint = ModInt<P>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> cnt(n + 1);
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        ++cnt[x];
    }
    for (int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
    }
    vector<vector<vector<Mint>>> f(n + 1, vector<vector<Mint>>(n + 1, vector<Mint>(n + 1, Mint(0))));
    f[0][0][0] = 1;
    // i = n days
    // j = failed people
    // k = succeed non filled people
    // candidate = cnt[j] - (j - c0) - (n - j - k)
    vector<Mint> fct(n + 1, 1), ifc(n + 1);
    for (int i = 1; i <= n; i++) {
        fct[i] = fct[i - 1] * i;
    }
    ifc[n] = fct[n].inv();
    for (int i = n - 1; i >= 0; i--) {
        ifc[i] = ifc[i + 1] * (i + 1);
    }
    auto C = [&](int a, int b) -> Mint {
        if (b < 0 || b > a) return 0;
        return fct[a] * ifc[b] * ifc[a - b];
    };
    int c0 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            for (int j = c0; j <= i; j++) {
                int x = cnt[j + 1] - cnt[j];
                Mint pl = fct[x];
                for (int k = 0; k <= i - j; k++) {
                    for (int z = 0; z <= cnt[j + 1] - cnt[j] && z <= k; z++) {
                        f[i + 1][j + 1][k - z] += f[i][j][k] * C(k, z) * C(cnt[j + 1] - cnt[j], z) * fct[z];
                    }
                }
            }
            c0++;
        } else {
            for (int j = c0; j <= i; j++) {
                for (int k = 0; k <= i - j; k++) {
                    // not succeed
                    int candidate = cnt[j] - (j - c0) - (i - j - k);
                    if (candidate > 0) {
                        for (int z = 0; z <= cnt[j + 1] - cnt[j] && z <= k; z++) {
                            f[i + 1][j + 1][k - z] += f[i][j][k] * candidate * C(k, z) * C(cnt[j + 1] - cnt[j], z) * fct[z];
                        }
                    }
                    // succeed
                    if (k + 1 <= n) {
                        f[i + 1][j][k + 1] += f[i][j][k];
                    }
                }
            }
        }
    }
    Mint ans = 0;
    for (int j = 0; j <= n - m; j++) {
        for (int k = 0; k <= n; k++) {
            if (n - cnt[j] >= k) {
                ans += f[n][j][k] * C(n - cnt[j], k) * fct[k];
            }
        }
    }
    ans *= fct[c0];
    cout << ans.x << "\n";
    return 0;
}