CSP-S2025 部分分详解

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

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

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

值，按这个数字贪心即可。

参考代码

CPP

#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)

。

参考代码

CPP

#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

q=1

。

回到

L_1,L_2\le 2000

，前面的枚举还是太暴力了。我们可以提前做哈希使得任意串匹配的复杂度为

O(1)

。这样可以优化到

O(nL_2)

，仍然无法通过。

看样子暴力没有优化空间了，我们需要发掘性质。

不难发现：和性质 B 一样，每一个

s

只可能对一个

t

的一个位置作出贡献，我们假设存在两个方案，由于替换一定要造成修改，所以两个位置一定有交；考虑被修改的位置，由于两种方案不同，

s_{j,1}\ne s_{j,2}

，一定有一个位置在一个方案中被修改而在另一个方案中没被修改，显然这两种方案不能都得到

t_{i,2}

，所以矛盾。

一个

s

只能对某个

t

的最多一个位置作出贡献，尝试找到它们能互相贡献的条件。

类似于上一个部分中处理极长公共前后缀、匹配中段的思想，我们把一个询问拆成三部分，左边是极长公共前缀，右边是极长公共后缀，中间是剩下的部分，其中左右都一定不得改变，中间一定要改变。

相对应地，

s_{i,1/2}

也可以拆成三部分，中间是造成的改变，公共前后缀不会造成替换后的字符串改变，但是它是一种限制，要求

t

的某段要匹配上

s

的全部部分而非只是中间部分。

归纳得到

s

对

t

有贡献的三个必要条件：

$s_{i,1}$ 的中间部分匹配 $t_{i,1}$ 的中间部分， $s_{i,2}$ 的中间部分匹配 $t_{i,2}$ 的中间部分。
$s$ 的极长公共前缀是 $t$ 的极长公共前缀的后缀。
$s$ 的极长公共后缀是 $t$ 的极长公共后缀的前缀。

第一个条件就是替换的本质，条件二三是要保证

s1

完美匹配了

t1

，

s2

完美匹配了

t2

。可以类比性质 B 的位移量相同和那个二维数点的两个条件。

把

s

和

t

分别划分成三段就可以直接

O(1)

计算每个

s,t

对之间能不能相互贡献了。时间复杂度

O(nq)

。

正解

考虑按中间部分，即条件一，中间部分相同的

s

对和

t

对划分成子问题，对多个子问题分开做，接下来只用考虑条件二和三。它们和偏序条件其实类似，但是更为严格。接下来的转化方法比较多。

一种做法是注意到空间给了 2048MiB，考虑 trie，把后缀条件的串反转一下变成前缀条件，前缀条件“

a

是

b

的前缀”可以转化为“

a

在 trie 树上的代表结点是

b

在 trie 树上的代表结点的祖先”。

P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands 的下一步转化与此类似，如果你做过这道题应该可以马上反应过来下一步了：两个前缀要求就是要求在两棵 trie 树上

s

都是

t

的祖先，考虑视作普通树，

s

是

t

的祖先要求

t

的结点 dfs 序在一个区间内（即在 s 的子树内），两棵树都有要求就是二维问题，

s

要求

t

的两个 dfs 序为坐标表示的点在一个矩形内，即给出若干矩形，每次询问给出一个点，问这个点在多少个矩形中。简单扫描线用树状数组可以解决。

我考场上的想法另类一些，只用

s

的反转前缀建 trie 树，

t

用反转前缀按字典顺序遍历这棵 trie，这样可以保证每个结点只进出一次，进出结点的时候把这个结点对应的

s

丢进/出要 check 的序列里，走到

t

的终止结点的时候 check 序列里就有了所有满足条件二的字符串

s

，我们要用条件三计数。

注意到做到这里其实还是

O(nq)

的，但是我们不暴力去做条件三，考虑

s

和

t

的条件三如何 check，令它们的后缀分别为

S

和

T

，条件三为判断

T

的长度为

\vert S\vert

的前缀是否和

S

相等，故前述“把

s

丢进 check 序列”的操作可以实现为对把

s

丢进以后缀长度、后缀哈希值为键的哈希桶，

t

则对每个后缀的前缀去查桶元素个数，因为要用哈希查找所以常数较大，但

L_2

只有

5\times 10^6

应该是能过的。优点在于如果你全部用哈希实现那么这个做法是

O(n+q+L_1+L_2)

的，一只老哥都没有。

撰写代码时可能因为实现原因，发现以 pair 和 tuple 为键的 unordered_map 速度极慢，甚至让此线性做法不得通过。参考代码部分哈希用 map 实现，实际写出的复杂度为

O(L\log (n+q))

，也能够跑进 1000ms 内。

参考代码

CPP

#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;}
namespace std{template<>struct hash<tuple<ull,ull,ull,ull>>{size_t operator()(const tuple<ull,ull,ull,ull> &t) const noexcept{auto h1 = hash<ull>()(get<0>(t));auto h2 = hash<ull>()(get<1>(t));auto h3 = hash<ull>()(get<2>(t));auto h4 = hash<ull>()(get<3>(t));return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2)) ^ (h3 + 0x9e3779b97f4a7c15ULL + (h2 << 6) + (h2 >> 2)) ^ (h4 + 0x9e3779b97f4a7c15ULL + (h3 << 6) + (h3 >> 2));}};}
const int N = 210000,L = 11000000,C = 26,P1 = 998244353,P2 = 23,MOD1 = 700000031,MOD2 = 1000000007;
int n,q,sx[N],sy[N],tx[N],ty[N],subqcnt,cnt,ch[L][C],ans[N];
string s[N][2],t[N][2];
vector<int> up[N],qr[N],upd[L],qry[L];
unordered_map<tuple<ull,ull,ull,ull>,int> mp;
map<pair<ull,ull>,int> bck;
int trie(string s){
  int u = 0;
  for(auto c : s){
    c -= 'a';
    if(!ch[u][c]) ch[u][c] = ++ cnt;u = ch[u][c];
  }
  return u;
}
void sch(int u){
  vector<pair<ull,ull>> tmp;
  tmp.reserve(upd[u].size());
  for(auto i : upd[u]){
    auto S = s[i][0].substr(s[i][0].size() - sy[i],sy[i]);
    ull x1 = 0,x2 = 0;
    for(auto c : S) x1 = (x1 * P1 + c) % MOD1,x2 = (x2 * P2 + c) % MOD2;
    bck[{x1,x2}] ++;//对最长公共后缀哈希建桶
    tmp.eb(x1,x2);
  }
  for(auto i : qry[u]){
    auto S = t[i][0].substr(t[i][0].size() - ty[i],ty[i]);
    ull x1 = 0,x2 = 0;
    for(auto c : S) ans[i] += bck[{x1,x2}],x1 = (x1 * P1 + c) % MOD1,x2 = (x2 * P2 + c) % MOD2;
    if(bck.find({x1,x2}) != bck.end()) ans[i] += bck[{x1,x2}];
  }
  fr(i,0,25) if(ch[u][i]) sch(ch[u][i]);
  for(auto i : tmp) bck[i] --;
}
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  fr(i,1,n){
    cin >> s[i][0] >> s[i][1];
    if(s[i][0] == s[i][1]) continue;
    fr(j,0,s[i][0].size() - 1){//x/y 记最长公共前后缀长度
      if(s[i][0][j] == s[i][1][j]) sx[i] ++;
      else break;
    }
    for(int j = s[i][0].size() - 1;~j;j --){
      if(s[i][0][j] == s[i][1][j]) sy[i] ++;
      else break;
    }
    int bh;
    tuple<ll,ll,ll,ll> tmp;//记录中段哈希值，两个串双哈希所以有四个元素
    fr(j,0,1){
      auto S = s[i][j].substr(sx[i],s[i][0].size() - sx[i] - sy[i]);
      ull x1 = 0,x2 = 0;
      for(auto c : S) x1 = (x1 * P1 + c) % MOD1,x2 = (x2 * P2 + c) % MOD2;
      if(j) get<2>(tmp) = x1,get<3>(tmp) = x2;
      else get<0>(tmp) = x1,get<1>(tmp) = x2;
    }
    if(mp.find(tmp) == mp.end()) mp[tmp] = bh = ++ subqcnt;
    else bh = mp[tmp];
    up[bh].eb(i);//映射入对应问题，t 同理
  }
  fr(i,1,q){
    cin >> t[i][0] >> t[i][1];
    if(t[i][0].size() != t[i][1].size()) continue;
    fr(j,0,t[i][0].size() - 1){
      if(t[i][0][j] == t[i][1][j]) tx[i] ++;
      else break;
    }
    for(int j = t[i][0].size() - 1;~j;j --){
      if(t[i][0][j] == t[i][1][j]) ty[i] ++;
      else break;
    }
    int bh;tuple<ll,ll,ll,ll> tmp;
    fr(j,0,1){
      auto S = t[i][j].substr(tx[i],t[i][0].size() - tx[i] - ty[i]);
      ull x1 = 0,x2 = 0;
      for(auto c : S) x1 = (x1 * P1 + c) % MOD1,x2 = (x2 * P2 + c) % MOD2;
      if(j) get<2>(tmp) = x1,get<3>(tmp) = x2;
      else get<0>(tmp) = x1,get<1>(tmp) = x2;
    }
    if(mp.find(tmp) == mp.end()) continue;//没有对应的 s 就直接舍弃，没有必要再开问题
    bh = mp[tmp],qr[bh].eb(i);
  }
  fr(i,1,subqcnt){
    fr(i,0,cnt){
      upd[i].clear(),qry[i].clear();
      fr(j,0,25) ch[i][j] = 0;
    }
    bck.clear(),cnt = 0;
    for(auto j : up[i]){//对反转最长公共前缀建 trie，一个 t 要 check 所有祖先结点的 s
      string S = s[j][0].substr(0,sx[j]);
      reverse(S.begin(),S.end());
      upd[trie(S)].eb(j);
    }
    for(auto j : qr[i]){
      string S = t[j][0].substr(0,tx[j]);
      reverse(S.begin(),S.end());
      qry[trie(S)].eb(j);
    }
    sch(0);
  }
  fr(i,1,q) printf("%d\n",ans[i]);
  return 0;
}

考场上因为时间问题没有实现成功，写的是丢进 check 序列后暴力匹配后缀，并且没有按字典顺序走

t

，还写了 map<pair<string,string>,int>。

Upd：考场上挂完了，剩个 B 的 25 分。

employ

$n\le 10$

考虑枚举所有排列

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)

。

参考代码

CPP

#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]

一定不交，所以前者的计算和后者的计算独立。最后乘上剩余未定人数的阶乘即可得到最终答案。

参考代码

CPP

#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}

的后续转移：

f_{i,j,k}\times S[j+1,n]\to f_{i+1,j,k}\\ f_{i,j,k}\times(S[0,j]-k)\times \displaystyle\binom{S[j+1,j+1]}{l}\times\displaystyle\binom{i-k}{l}\times l! \to f_{i+1,j+1,k+l+1},l\in[0,\min(i-k,S[j+1,j+1])]

如上完成了 $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)

。

参考代码

CPP

#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$ 分。

CSP-S2025 部分分详解

文章操作

club

$n=2,4,10$

$n\le 200$

性质 A

性质 B

性质 C

正解

road

$k\le 0$

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

性质 A

$k\le 5$ 或 $n\le 1000$

正解

replace

$L_1,L_2\le 200$

$L_1,L_2\le 2000$

性质 B

$nq\le 10^6$ ，性质 A

正解

employ

$n\le 10$

$n\le 18$

$m=n$

$m=1$

正解

总结

club

road

replace

employ

相关推荐

评论

CSP-S2025 部分分详解

文章操作

club

n=2,4,10n=2,4,10n=2,4,10

n≤200n\le 200n≤200

性质 A

性质 B

性质 C

正解

road

k≤0k\le 0k≤0

k≤5∧m≤105k\le 5\wedge m\le 10^5k≤5∧m≤105

性质 A

k≤5k\le 5k≤5 或 n≤1000n\le 1000n≤1000

正解

replace

L1,L2≤200L_1,L_2\le 200L1​,L2​≤200

L1,L2≤2000L_1,L_2\le 2000L1​,L2​≤2000

性质 B

nq≤106nq\le 10^6nq≤106，性质 A

正解

employ

n≤10n\le 10n≤10

n≤18n\le 18n≤18

m=nm=nm=n

m=1m=1m=1

正解

总结

club

road

replace

employ

相关推荐

评论

$n=2,4,10$

$n\le 200$

$k\le 0$

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

$k\le 5$ 或 $n\le 1000$

$L_1,L_2\le 200$

$L_1,L_2\le 2000$

$nq\le 10^6$ ，性质 A

$n\le 10$

$n\le 18$

$m=n$

$m=1$