CSP-S 2025 个人解法
I_am_Accepted
·
·
题解
暂醒复寐
题解
社团招新 / club
尝试让所有人都选满意度最高的部门。如果出现了超员的部门，求每个在该部门的人转至第二喜欢的部门的代价。将代价排序并取最小的那些即可。调整后一定不会出现超员的部门，因为不可能有第二个人数超过 n/2 的部门。
道路修复 / road
$O(2^knk(\alpha(n)+\log k))$ 过了，嘻嘻。
DFS 出所有乡镇是否启用，维护当前点集的 MST，每次将 $O(n)$ 的边集归并与 Kruskal，复杂度 $O(2^kn\alpha(n))$。
每次归并的两个边集为 $\delta(x)$ 和 $E(G)\backslash\delta(x)$，有良好的性质。遂不用并查集，直接连通块打标记即可，具体见代码，复杂度 $O(2^kn)$。
### 谐音替换 / replace
找到规则/询问最左和最右的修改位置，按照中间这段从啥改到啥分类（使用字符串哈希）。接下来我们只关注同一类中的规则/询问。
将规则的前缀后缀分别建 trie 树（前缀要反转）。设规则的前缀后缀 pair 集合为 $S$。每个询问转化为 $x,y$ 分别是第一/第二棵树上的节点，查询 $|\{(x'\text{ is anc of }x)\land(y'\text{ is anc of }y)|(x',y')\in S\}|$。将询问离线下来，DFS 第一棵树，查询第二棵树点到根的链和。由于链长之和有保证，所以这部分复杂度线性。
### 员工招聘 / employ
$f_{i,j,k}$ 表示前 $i$ 个面试位置，在 $\mathtt{1}$ 处放了 $j$ 个应聘人，有 $k$ 个通过面试的方案数。
若一位应聘人通过面试，则对其耐心的限制为大于某个值。我们将这些限制容斥成【不限制】与【限制耐心不超过某个值】。
此 DP 只在 $\mathtt{1}$ 处转移（从上一个 $\mathtt{1}$ 转移过来，忽略中间的 $\mathtt{0}$），将第一维 $i$ 滚动掉。
$$
\begin{aligned}
f'_{j,k+1}
&\longleftarrow f_{j,k}
&\quad\text{(approved with no constraint)}
\\
f'_{j+1,k+1}
&\longleftarrow (-1)\times f_{j,k}\times (\text{cnt}_{\le i-1-k}-j)
&\quad\text{(approved with an I-E constraint)}
\\
f'_{j+1,k}
&\longleftarrow f_{j,k}\times (\text{cnt}_{\le i-1-k}-j)
&\quad\text{(rejected)}
\end{aligned}
$$
最后将 DP 值乘上 $(n-j)!$ 即为所求。
## 代码
### T1
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N][3],mx[N],cnt[3];
void work(){
cin>>n;
for(int i=1;i<=n;i++) for(int j=0;j<3;j++) cin>>a[i][j];
for(int j=0;j<3;j++) cnt[j]=0;
int sum=0;
for(int i=1;i<=n;i++){
cnt[mx[i]=max_element(a[i],a[i]+3)-a[i]]++;
sum+=a[i][mx[i]];
}
int w=-1;
for(int j=0;j<3;j++) if(cnt[j]*2>n) w=j;
if(w!=-1){
int del=cnt[w]-n/2;
vector<int> s;
for(int i=1;i<=n;i++) if(mx[i]==w){
sort(a[i],a[i]+3);
s.emplace_back(a[i][2]-a[i][1]);
}
sort(s.begin(),s.end());
for(int i=0;i<del;i++) sum-=s[i];
}
cout<<sum<<"\n";
}
signed main(){ios::sync_with_stdio(false);
int T;cin>>T;
while(T--)work();
return 0;
}
```
### T2
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+30;
struct edge{
int u,v,w;
edge(int _u,int _v,int _w):u(_u),v(_v),w(_w){}
edge(){}
friend bool operator<(const edge&x,const edge&y){
return x.w<y.w;
}
};
vector<edge> dis[10];
vector<int> e[N];
int n,m,cost[10],f[N];
bool vis[N];
long long ans=1e18;
inline int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}
bool link(int x,int y){
x=gf(x),y=gf(y);
if(x==y) return false;
f[x]=y;
return true;
}
void paint(int x){
if(vis[x]) return ;
vis[x]=true;
for(int i:e[x]) paint(i);
}
vector<edge> shrink(vector<edge> edges,int root){
vector<edge> res;
for(int i=1;i<=n+m;i++) vis[i]=false,e[i].clear();
for(auto i:edges){
if(i.u==root || i.v==root){
int x=i.u^i.v^root;
if(!vis[x]){
res.emplace_back(i);
paint(x);
}
}else{
int x=i.u;
int y=i.v;
e[x].emplace_back(y);
e[y].emplace_back(x);
if(!vis[x]&&!vis[y]){
res.emplace_back(i);
}else if(vis[x]&&!vis[y]){
res.emplace_back(i);
paint(y);
}else if(!vis[x]&&vis[y]){
res.emplace_back(i);
paint(x);
}
}
}
return res;
}
void dfs(int w,vector<edge> edges,long long co){
if(w==m){
for(auto i:edges) co+=i.w;
ans=min(ans,co);
return ;
}
dfs(w+1,edges,co);
vector<edge> edges_new;
merge(edges.begin(), edges.end(),
dis[w].begin(), dis[w].end(),
back_inserter(edges_new));
edges_new=shrink(edges_new,n+1+w);
dfs(w+1,edges_new,co+cost[w]);
}
signed main(){ios::sync_with_stdio(false);
cin>>n>>m;
vector<edge> edges,edges_new;
edges.resize(m);
cin>>m;
for(auto&[u,v,w]:edges){
cin>>u>>v>>w;
}
sort(edges.begin(),edges.end());
iota(f+1,f+1+n,1);
for(auto[u,v,w]:edges){
if(link(u,v)){
edges_new.emplace_back(u,v,w);
}
}
for(int i=0;i<m;i++){
cin>>cost[i];
for(int j=1;j<=n;j++){
int x;cin>>x;
dis[i].emplace_back(n+1+i,j,x);
}
sort(dis[i].begin(),dis[i].end());
}
dfs(0,edges_new,0);
cout<<ans<<"\n";
return 0;
}
```
### T3
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=5e6+10;
const long long P=((long long)1e18)+3,base=998244353;
int n,m,ans[N];
map<long long,
pair<
vector<pair<string,string>>,
vector<pair<pair<string,string>,int>>
>
> mp;
struct trie{
int ch[M][26],f[M],tot;
void clear(){
tot=0;
nnd();
}
int nnd(){
tot++;
f[tot]=0;
for(int i=0;i<26;i++) ch[tot][i]=0;
return tot;
}
int&operator()(int x,char w){
return ch[x][w-'a'];
}
int operator()(int x){
return f[x];
}
int insert(string x){
int rt=1;
for(auto w:x){
int&res=(*this)(rt,w);
if(!res) res=nnd(),f[res]=rt;
rt=res;
}
return rt;
}
int insert2(string x){
int rt=1;
for(auto w:x){
int&res=(*this)(rt,w);
if(!res) break;
rt=res;
}
return rt;
}
void traverse(function<void(int)> in,function<void(int)> out,int x=1){
in(x);
for(int i=0;i<26;i++) if(ch[x][i]) traverse(in,out,ch[x][i]);
out(x);
}
}F,G;
vector<int> hang[M];
vector<pair<int,int>> hang2[M];
int cnt[M];
long long hsh(string x){
long long res=0;
for(auto i:x) res=((__int128)res*base+i)%P;
return res;
}
pair<long long,pair<string,string>> get_diff(string x,string y){
int l=0,r=x.size()-1;
while(x[l]==y[l]) l++;
while(x[r]==y[r]) r--;
string tmp=x.substr(0,l);
reverse(tmp.begin(),tmp.end());
return make_pair(hsh(x.substr(l,r-l+1)+y.substr(l,r-l+1)),make_pair(tmp,x.substr(r+1,x.size()-r-1)));
}
signed main(){ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
string x,y;
cin>>x>>y;
if(x!=y){
auto[xx,yy]=get_diff(x,y);
mp[xx].first.emplace_back(yy);
}
}
for(int i=1;i<=m;i++){
string x,y;
cin>>x>>y;
if(x.size()==y.size()){
auto[xx,yy]=get_diff(x,y);
mp[xx].second.emplace_back(yy,i);
}
}
for(const auto&[key,value]:mp){
const auto&[rules,queries]=value;
for(int i=1;i<=F.tot;i++) hang[i].clear(),hang2[i].clear();
for(int i=1;i<=G.tot;i++) cnt[i]=0;
F.clear(),G.clear();
for(const auto&[i,j]:rules){
int y=G.insert(j);
hang[F.insert(i)].emplace_back(y);
}
for(const auto&[i,k]:queries){
int x=F.insert2(i.first);
int y=G.insert2(i.second);
hang2[x].emplace_back(y,k);
}
F.traverse(
[&](int x){
for(int i:hang[x]){
cnt[i]++;
}
for(auto[i,j]:hang2[x]){
while(i){
ans[j]+=cnt[i];
i=G(i);
}
}
},
[&](int x){
for(int i:hang[x]){
cnt[i]--;
}
}
);
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
```
### T4
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=504,P=998244353;
int n,m,b[N],f[N][N],g[N][N],cnt[N],fac[N];
char a[N];
signed main(){ios::sync_with_stdio(false);
cin>>n>>m;
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=(long long)fac[i-1]*i%P;
cin>>(a+1);
for(int i=1;i<=n;i++) cin>>b[i],cnt[b[i]]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
f[0][0]=1;
for(int i=1;i<=n;i++){
if(a[i]=='1'){
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
g[j][k]=0;
}
}
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
if(f[j][k]!=0){
(g[j][k+1]+=f[j][k])%=P;
(g[j+1][k+1]+=P-(long long)f[j][k]*max(0,cnt[i-1-k]-j)%P)%=P;
(g[j+1][k]+=(long long)f[j][k]*max(0,cnt[i-1-k]-j)%P)%=P;
}
}
}
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
f[j][k]=g[j][k];
}
}
}
}
int ans=0;
for(int j=0;j<=n;j++){
for(int k=m;k<=n;k++){
(ans+=(long long)f[j][k]*fac[n-j]%P)%=P;
}
}
cout<<ans<<"\n";
return 0;
}
```