CSP-S2025 部分分详解

chenxi2009 · 2025-11-03 20:00:10 · 算法·理论

本文尝试构建、剖析每一题部分分至正解的思维链，希望能借此帮助读者了解自己在考场上犯下的错误、策略的不足，并尝试让一些能力不足以写出题目正解的选手也能理解题目的部分思想。因此文章可能较为冗长。

题解区交不了不关联题目的文章，所以发在这里。

宣传，利益相关：OI 选手

club

n=2,4,10

我们考虑枚举所有方案。

具体地，枚举每个人被分配到了哪个社团，判断方案是否合法，求所有合法方案的答案最大值。方案数是 3^n，复杂度为 O(n\times 3^n)，可以使用搜索实现，可以通过 n\le 10 的数据。

n\le 200

注意到枚举方案时我们只关心前面每种社团报了多少人和现在总收益而不关心具体是前面的哪个人报了哪个社团，考虑 DP。

任意顺序考虑所有人，令 f_{i,j,k} 表示前 i+j+k 个人中，i 个人报了第一个部门，j 个人报了第二个部门，k 个人报了第三个部门时的最大答案，有带条件转移 f_{i,j,k}\to f_{i+1,j,k},f_{i,j+1,k},f_{i,j,k + 1}。时空复杂度 O(n^3)。

性质 A

选部门二和部门三没有贡献。易知我们让 a_{i,1} 最大的 \displaystyle\frac{n}{2} 个人选择部门一，其他人随便可得最大值。

性质 B

选部门三没有贡献，剩下两个部门都最多进 \displaystyle\frac{n}{2} 个人，要把 n 个人安排进去，必然是一边一半。考虑返回贪心，全部分给部门一，然后按 a_{i,2}-a_{i,1} 从大到小贪心分一半给部门二。

性质 C

注意到一半以上的人最喜欢的社团相同是一个极端情况，在 n 很大的时候不太可能发生。GPT 给出 n=100000 时出现这种情况的可能大概在 10^{-2716} 量级。

正解

求证：最优解中没有人选择自己严格最不喜欢的部门。

证明：找出这样的人，另外两个部门中现在最多只有 n-1 个人，所以其中至少有一个人数未满 \displaystyle\frac{n}{2}，可以把这个人挪过去。

所以一个人只会在自己最喜欢或次喜欢的部门里。

考虑类似于性质 B 的做法，所有人先选择自己最喜欢的部门，如果有部门超了上限就要把超出部分挪一些人到他们次喜欢的部门中，损失是最喜欢部门的 a 值减去次喜欢部门的 a 值，按这个数字贪心即可。

::::info[参考代码]

#include<bits/stdc++.h>
#define ep emplace 
#define eb emplace_back
#define ll long long
#define ull unsigned ll
#define fr(a,b,c) for(int a = (b);(a) <= (c);(a) ++)
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = getchar();while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 200000;
int T,n,a[N][4],cnt[3],ans,c[N],ov;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> T;
  while(T --){
    cnt[1] = cnt[2] = cnt[3] = ans = ov = 0;
    cin >> n;
    fr(i,1,n) cin >> a[i][1] >> a[i][2] >> a[i][3];
    fr(i,1,n){
      fr(j,1,3){
        if(a[i][j] == max({a[i][1],a[i][2],a[i][3]})){//找出最喜欢的部门
          cnt[j] ++,c[i] = j,ans += a[i][j];
          break;
        }
      }
    }
    fr(i,1,3) if(cnt[i] > n / 2) ov = i;
    if(ov){//如果有部门招募了超过一半的人
      while(q.size()) q.pop();
      fr(i,1,n) if(c[i] == ov) q.ep(a[i][ov] - (a[i][1] + a[i][2] + a[i][3] - a[i][ov] - min({a[i][1],a[i][2],a[i][3]})));//按损失值贪心
      fr(i,1,cnt[ov] - n / 2) ans -= q.top(),q.pop();//优先取损失小的
    }
    printf("%d\n",ans);
  }
  return 0;
}

::::

road

k\le 0

考虑图论建模。

P3366 【模板】最小生成树

k\le 5\wedge m\le 10^5

考虑图论建模。

把城镇化后的乡镇当作新点，花钱连接乡镇和城市的操作看成一条新边，我们考虑最优方案是选出某些乡镇城镇化后的新图上的最小生成树。可能有乡镇没有和城市连通的情况，但是注意到乡镇城镇化的花费是非负的，取消这样乡镇的城镇化不会更劣。

所以可以枚举城镇化哪些乡镇再在新图上跑最小生成树。时间复杂度 O(2^k m\log m)。

性质 A

城镇化乡镇并把它和某一个城市连起来没有代价。

所以城镇化所有乡镇后在新图上跑最小生成树不会劣。直接跑就行。

k\le 5 或 n\le 1000

求证：给一个连通图加上若干个点和若干条边成为一个新的连通图，用原图的最小生成树上的边和新边一定能构成新图的一个最小生成树。

证明：考虑 Kruscal 算法过程，注意原图的不在最小生成树上的边，它不在最小生成树上是因为按边权排序后在它之前的边可以把它的两个端点连通。加入新边后在它之前的边只会变多，故原来被舍弃掉的边还是会被舍弃。证毕。

因此我们在原图上可以只保留跑出来的最小生成树的 n-1 条边，枚举方案并在新图上跑最小生成树即可。时间复杂度 O(m\log m+2^k nk\log (nk))。

正解

上述算法瓶颈在给新图的边排序。考虑提前把树边和所有的潜在新边放一起排序，之后枚举的时候遍历这个排好的边序列即可，注意判断当前遍历到的边是不是当前方案中有的边。时间复杂度 O(m\log m+2^k nk)。 ::::info[参考代码]

#include<bits/stdc++.h>
#define ep emplace 
#define eb emplace_back
#define ll long long
#define ull unsigned ll
#define fr(a,b,c) for(int a = (b);a <= (c);a ++)
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = getchar();while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 20000,M = 1500000,K = 11;
struct node{
    int u,v,w;
};
int n,m,k,c[K],a[K][N],f[N],cnt,cnting;
ll ans = 2e18,cst;
node e[M],G[M];
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
int main(){
  cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    fr(i,1,m) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1,e + m + 1,[](node a,node b){
        return a.w < b.w;
    });
    iota(f + 1,f + n + 1,1);
    fr(i,1,m){
        auto [u,v,w] = e[i];
        if(find(u) == find(v)) continue;
        f[f[u]] = f[v],G[++ cnt] = e[i];//记录原图最小生成树边
    }
    fr(i,1,k){
        cin >> c[i];
        fr(j,1,n){
            cin >> a[i][j];
            G[++ cnt] = {j,i + n,a[i][j]};//把所有可能的新边加入一起排序
        }
    }
    sort(G + 1,G + cnt + 1,[](node a,node b){
        return a.w < b.w;
    });
    fr(st,0,(1 << k) - 1){//枚举城镇化方案
        cst = 0,cnting = n - 1;
        fr(i,1,k) if(st & (1 << i - 1)) cst += c[i],cnting ++;
        iota(f + 1,f + n + k + 1,1);
        fr(i,1,cnt){
            auto [u,v,w] = G[i];
            if(v > n && !(st & (1 << v - n - 1))) continue;//这条边不在当前方案中
            if(find(u) == find(v)) continue;
            cst += w,f[f[u]] = f[v];
            if(!-- cnting || cst > ans) break;//剪枝，**不**降低时间复杂度
        }
        ans = min(ans,cst);
    }
    printf("%lld\n",ans);
  return 0;
}

:::: 更好的解法：拓展上面的证明，两个图并作一个新图，两个原图的最小生成树边可以构成新图的最小生成树。所以对于所有添加了两个及以上新点的情况，我们考虑找出两个新图并起来得到这个新图，归并这两个新图的生成树边做 Kruscal 即可。时间复杂度 O(m\log m+2^k n\alpha(n))。

replace

需要有一定字符串基础。

首先根据替换的性质可以简单得到 s_{i,1}=s_{i,2} 和 \vert t_{i,1}\vert\ne\vert t_{i,2}\vert 是无法产生答案的，本文以下分析建立在这两种情况不存在的基础之上。

L_1,L_2\le 200

考虑暴力。

枚举每个 t_{i,1} 的每个字符作为被替换串 y 的开头，再枚举每个 s_{j,1} 尝试与此段匹配，若匹配上则替换成 s_{j,2} 后查看是否和 t_{i,2} 相同。

枚举每个 t_{i,1} 的每个位置是 O(L_2) 的，之后枚举所有替换串并匹配是 O(L_1) 的，和 t_{i,2} 匹配是 O(L_2) 的，时间复杂度 O\left(L_1{L_2}^2\right)。

L_1,L_2\le 2000

发现和 t_{i,2} 匹配非常不优，因为在这个过程中我们对 t_{i,1} 没有改变的部分 x,z 和 t_{i,2} 做了冗余的 check。考虑这个部分只做一次，即处理出 t_{i,1/2} 的最长公共前后缀，如果替换后需要 t_{i,1/2} 的相同前后缀长度比这个长就可以宣布匹配失败，如果成功再比较 s_{j,2} 和 t_{i,2} 的中间部分是否相同。这个比较的复杂度和 s_{j,1} 与 t_{i,1} 比较是相同的，因此总时间复杂度为 O(L_1L_2)。

性质 B

每个字符串有一个 b，剩下的全是 a。

考虑此时替换相当于移动 t_{i,1} 中字符 b 的位置，要使得新位置刚好在 t_{i,2} 的 b 处。

令 b 在 t_{i,1/2} 中的位置为 xt_{1/2}，我们考虑写出 b 需要的向右位移量 x=xt_2-xt_1，对于 s 则有 x=xs_2-xs_1，显然 s 替换造成的位移要和 t 的位移相匹配才能够贡献，且显然 s_{j,1} 的 b 要放在 t_{i,1} 的 b 的那个位置，所以也只有一个位置能够匹配。

还有限制吗？有的有的，我们还要保证把 s_{j,1} 放到 t_{i,1} 的这个位置之后 s 的两边不比 t 长，因为 t 的 b 左右两边太短的话 s 就会凸出去匹配不上。所以还要要求 t 的 b 的左右两边 a 的个数要不小于 s 的对应个数。

我们首先按位移量把 s 和 t 划分开，s 对 t 做贡献有一个二维限制，我们可以做二维数点来解决。

nq\le 10^6，性质 A

考虑枚举所有排列 p 进行 O(n) 的 check，时间复杂度 O(n\times n!)。

n\le 18

考虑从左往右，对人是否已经参与面试进行状压，f_{state,i} 表示人的参与情况为 state，已经有 i 个人在面试中失败或放弃了面试时的方案数，转移时枚举下一个过来的人是哪一个即可。状态数 O(2^n\times n)，单个状态有 O(n) 个向外转移，时间复杂度 O(2^n\times n^2)。

::::info[参考代码]

#include<bits/stdc++.h>
#define ep emplace 
#define eb emplace_back
#define ll long long
#define ull unsigned ll
#define fr(a,b,c) for(int a = (b);(a) <= (c);(a) ++)
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = getchar();while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 20;
const ll MOD = 998244353;
int n,m,c[N];
ll ans,f[270000][N];
string s;
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> s,s = " " + s;
  fr(i,1,n) cin >> c[i];
  f[0][0] = 1;
  fr(st,0,(1 << n) - 2){
    int i = __builtin_popcount(st);//这个状态有几个人已经参与面试
    fr(j,0,i){
      fr(k,1,n){//枚举下一个参与面试的人
        if(st & (1 << k - 1)) continue;
        if(s[i + 1] == '1' && c[k] > j) f[st + (1 << k - 1)][j] = (f[st + (1 << k - 1)][j] + f[st][j]) % MOD;//面试成功
        else f[st + (1 << k - 1)][j + 1] = (f[st + (1 << k - 1)][j + 1] + f[st][j]) % MOD;//面试失败 
      }
    }
  }
  fr(i,0,n - m) ans = (ans + f[(1 << n) - 1][i]) % MOD;
  printf("%lld\n",ans);
  return 0;
}

::::

m=n

注意到只有一个点，比暴力分还少，想必难度和去年 NOIPT3 输出 1 差不多。

因为你需要招到所有人，所以有 c_i=0 或 s_i=0 就寄了，一定完不成，答案为 0。

否则 c_i\ge 1,s_i=1，没有人会不被录取，任意排列 p 均可，答案为 n!。

m=1

我们考虑枚举那个被录取的第一个人的位置。令其在位置 i，则这个位置必须有 s_i=0 且这个人要求 c_j\in [i,n]，因为他前面的 i-1 个人都失败了，不然他就不是被录取的第一个人了。

在他后面的人 c 怎么样我们不关心，最后考虑。

在他前面的 s_i=0 的位置站的人 c 怎么样都会失败，我们不关心，最后考虑。

在他前面的 s_j=1 的位置上的人要求 c_k\in[0,j)，因为这个位置前的人都失败了，这个人也必须失败。

不难发现从前往后计数是简单的，因为后面位置的范围包住了前面位置的 c 的取值范围，所以从前往后做可以确定每一个前面的确定人选会减少后面的一个选项；[0,j) 和 [i,n] 一定不交，所以前者的计算和后者的计算独立。最后乘上剩余未定人数的阶乘即可得到最终答案。 ::::info[参考代码]

#include<bits/stdc++.h>
#define ep emplace 
#define eb emplace_back
#define ll long long
#define ull unsigned ll
#define fr(a,b,c) for(int a = (b);(a) <= (c);(a) ++)
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = getchar();while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 600;
const ll MOD = 998244353;
int n,m,c[N],a[N],S[N];
ll ans,fct[N];
string s;
int main(){
  fct[0] = 1;
  fr(i,1,N - 1) fct[i] = fct[i - 1] * i % MOD;
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> s,s = " " + s;
  fr(i,1,n) cin >> c[i],a[c[i]] ++;
  S[0] = a[0];
  fr(i,1,n) S[i] = S[i - 1] + a[i];//做桶来统计 c 在一个区间内的人数
  fr(i,1,n){
    if(s[i] == '0') continue;   
    int cnt = 0;ll tot = 1;
    fr(j,1,i - 1){
      if(s[j] == '0') continue;
      tot = tot * max(0,S[j - 1] - cnt) % MOD,cnt ++;//cnt 记录 [0,j) 范围内取走了多少个 c
    }
    tot = tot * (S[n] - S[i - 1]) % MOD,cnt ++;//确定 i 处放的人
    ans = (ans + tot * fct[n - cnt]) % MOD;//剩下的人任意排列，有阶乘种情况
  }
  printf("%lld\n",ans);
  return 0;
}

::::

正解

考虑 m=1 为什么能做，这是因为前面选择的每一个“失败的人”，都一定会使得后面的“失败的人”可选的人选减一，同时不会影响“成功的人”的选择方案。如果要能通过“确定选择顺序”来做到简单计数，那么一定得是满足“每次选择一个人的范围要么包含，要么不交”。例如 m=1，确定了“第一个被录取的人”后，我们每个 s_i=1 的人选范围如下图：

下矩形是失败的 s_i=1 处，从左往右已经失败的人数递增，因此呈包含关系，有了包含关系我们就知道前面一次选择了一个人，这个人必然在下一次的可选择范围里，因此这个选择使得下一次的选择人选少了一个。上矩形是被成功录取的位置，选择范围和其他矩形不交，因此不互相影响。

当我们需要录取的人数超过 1 时，图就变了：

这样似乎压根就没有简单的做法，因为出现第一个成功者之前都是包含或不交的，但是后面出现失败者之后就会有问题，你并不知道那个成功者的 c 值放到此处会不会失败，也就无从知道那个人的选择是否使得此处的可选人少 1。

注意到这做不了之后就开始考虑把此决策延后，也就是在“需要知道那个人的 c 值是否在一个范围内”的时候再去决定那个人的 c 值是否在此范围内。

具体演示，我们定义 f_{i,j,k} 为前 i 个位置，j 个人失败，这些人中有 k 个人的 c\le j，c>j 的具体人选还未确定时的情况数。我们先考虑 s_i=1 的情况，要让下一个人失败他就得有 c\le j，我们令 S[l,r] 表示 l\le c_i\le r 的人数，则下一个人失败的情况数是 S[0,j]-k，成功的情况数是 S[j+1,n]。

还没做完，成功的情况是显然的，直接转；失败的时候后续状态的 j\leftarrow j+1，想要知道后续状态的 k，我们就要确定前面的 c>j 的人有多少是 c=j+1 的。枚举这个数字 l，考虑这 l 个人在哪些位置、取了哪些人、内部如何排列，转移的方案数是 S[0,j]\times\displaystyle\binom{S[j+1,j+1]}{l}\times\displaystyle\binom{i-k}{l}\times l!。

具体一点，对于 f_{i,j,k} 的后续转移：

如上完成了 s_{i+1}=1 的转移，也即 A 性质的内容。

考虑 s_{i+1}=0，一定会有 j\leftarrow j+1，因此必定有 l 的讨论。令 tmp\leftarrow f_{i,j,k}\times \displaystyle\binom{S[j+1,j+1]}{l}\times\displaystyle\binom{i-k}{l}\times l! 我们考虑两种情况：

• 下一个人的 c\le j+1，有 tmp\times (S[j+1,j+1]-k-l)\to f_{i+1,j+1,k+l+1},0\le l\le \min(S[0,j+1]-k-1,i-k,S[j+1,j+1])
• 下一个人的 c>j+1，有 tmp\to f_{i+1,j+1,k+l},0\le l\le \min(i-k,S[j+1,j+1])

注意空间限制，可能需要滚动数组。容易发现虽然我们要枚举 l，但是各个 i 枚举的 l 总和 O(n)，因为它的枚举范围是对应的 c 的个数。时间复杂度 O\left(n^3 \right)。

::::info[参考代码]

#include<bits/stdc++.h>
#define ep emplace 
#define eb emplace_back
#define ll long long
#define ull unsigned ll
#define fr(a,b,c) for(int a = (b);(a) <= (c);(a) ++)
using namespace std;
template<typename T>void read(T &x){x = 0;int f = 1;char c = getchar();while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)) x = x * 10 + c - '0',c = getchar();x *= f;}
const int N = 600;
const ll MOD = 998244353;
int n,m,c[N],S[N];
ll f[N][N],g[N][N],ans,fct[N],inv[N];
string s;
ll qp(ll a,ll b){
  ll c = 1;
  for(;b;b >>= 1,a = a * a % MOD) if(b & 1) c = c * a % MOD;
  return c;
}
ll C(int n,int m){
  if(m < 0 || m > n) return 0ll;
  return fct[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main(){
  fct[0] = 1;
  fr(i,1,N - 1) fct[i] = fct[i - 1] * i % MOD;
  inv[N - 1] = qp(fct[N - 1],MOD - 2);
  for(int i = N - 1;i;i --) inv[i - 1] = inv[i] * i % MOD;
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> s;
  s = " " + s;
  fr(i,1,n) cin >> c[i],S[c[i]] ++;
  fr(i,1,n) S[i] += S[i - 1];
  f[0][0] = 1;
  fr(i,0,n - 1){
    fr(j,0,i) fr(k,0,min(S[j],i)) g[j][k] = f[j][k],f[j][k] = 0;
    fr(j,0,i){
      fr(k,0,min(S[j],i)){
        if(s[i + 1] == '1'){
          f[j][k] = (f[j][k] + g[j][k]) % MOD;
          if(k < S[j]){
            fr(l,0,min(i - k,S[j + 1] - S[j])){z
              f[j + 1][k + l + 1] = (f[j + 1][k + l + 1] + g[j][k] * C(i - k,l) % MOD * C(S[j + 1] - S[j],l) % MOD * fct[l] * (S[j] - k)) % MOD;
            }
          }
        }
        else{
          fr(l,0,min(i - k,S[j + 1] - S[j])){
            ll tmp = g[j][k] * C(S[j + 1] - S[j],l) % MOD * C(i - k,l) % MOD * fct[l] % MOD;
            if(k + l < S[j + 1]){
              f[j + 1][k + l + 1] = (f[j + 1][k + l + 1] + tmp * (S[j + 1] - k - l)) % MOD;
            }
            f[j + 1][k + l] = (f[j + 1][k + l] + tmp) % MOD;
          }
        }
      }
    }
  }
  fr(i,0,n - m) ans = (ans + f[i][S[i]] * fct[n - S[i]]) % MOD;
  printf("%lld\n",ans);
  return 0;
}

::::

总结

分析各题知识点构成，便于寻找失分原因和策略失误。存在个人差，请理性看待。以下“简单的”一般指笔者认为不超过洛谷黄难度。具有分层断档的题目所述的难度指的不是此部分单独作为题目的难度，而是从上一档思考转向此部分得出做法的思维上的难度，也不存在实际洛谷难度评级中的“黄+黄=绿”的类似情况，不代表训练难度，请不要过于纠结于此。

club

• 20 分：暴力枚举，搜索

• +20 分：简单贪心

• +10 分：对“随机”的观察

• +30 分：简单的 DP 设计

• 100 分：具有反悔思想的贪心

  road

  前置知识：最小生成树

• 16 分：基本建模

• 32 分：暴力枚举，搜索

• +32/24 分：性质观察

• 80 分：对最小生成树的观察或贪心

• 100 分：各种过程优化

  replace

• 10 分：暴力枚举

• 25 分：简单的字符串哈希运用

• +25 分：转化问题本质，运用字符串哈希

• +20 分：再次转化，二维数点

• 100 分：扫描线，trie，哈希，AC 自动机等

  employ

• 8 分：暴力枚举

• 20 分：简单的状压 DP

• +4 分：简单的观察

• +12 分：一定的计数思维与观察

• +20 分：完成正解的一半

• 100 分：具有一定难度的 DP，需要会一些 trick

失败并不可怕，失败而不能了解自己失败的原因才是真正的失败。

叠甲：笔者在出考场时已经会了 336 分的做法，实际因为各种原因只获得了 241 分。