CSP2025 題解
你猜我為什(shen)么不寫游(you)記。
直接貪心即可。
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
using namespace std;
const int N=1e5+5;
inline int read(){
int w=1,s=0;
char c=getchar();
for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
return w*s;
}
int T,n,a[N][5],id[N],cnt[5],ans;
signed main(){
// freopen("club.in","r",stdin);
// freopen("club.out","w",stdout);
T=read();
while(T--){
cnt[1]=cnt[2]=cnt[3]=0;
n=read();
ans=0;
for(int i=1;i<=n;i++){
int maxn=0;
for(int j=1;j<=3;j++) a[i][j]=read(),maxn=max(maxn,a[i][j]);
for(int j=1;j<=3;j++){
if(maxn==a[i][j]){
id[i]=j,cnt[j]++;
break;
}
}
ans+=maxn;
}
int mx=max({cnt[1],cnt[2],cnt[3]});
if(mx>n/2){
int o;
for(int i=1;i<=3;i++) if(mx==cnt[i]) o=i;
vector<int> vec;
for(int i=1;i<=n;i++){
if(id[i]==o){
int se=0;
for(int j=1;j<=3;j++) if(j!=o) se=max(se,a[i][j]);
vec.push_back(a[i][o]-se);
}
}
sort(vec.begin(),vec.end());
for(int i=0;i<mx-n/2;i++) ans-=vec[i];
}
printf("%d\n",ans);
}
return 0;
}
根據 Kruskal 的過程不難發現在加上那 \(O(nk)\) 條邊后原圖的邊只有原最小生成樹上的邊是有用的，因此有用的邊數是 \(O(nk)\) 的。
然后 \(O(2^k)\) 枚舉選擇了哪些新點，然后跑 Kruskal 求出此時的最小生成樹即可。
可以提前在外面排好 \(O(nk)\) 條邊的順序，這樣枚舉之后就不需要再排一遍序了。
\(O(2^knk\alpha(n))\)，應該不(bu)是正解，但跑得挺(ting)快的。
code
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
#define LL long long
using namespace std;
const int N=1e4+100,M=1e6+5;
inline int read(){
int w=1,s=0;
char c=getchar();
for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
return w*s;
}
int n,m,k,fa[N],c[15],a[15][N],tot;
bool flag[15];
LL ans=LLONG_MAX;
struct Edge{ int u,v,w,op; } E[M],MST[N];
int get(int x){ return (x==fa[x])?(x):(fa[x]=get(fa[x])); }
bool cmp(Edge x,Edge y){ return x.w<y.w; }
void Kruskal(){
for(int i=1;i<=n;i++) fa[i]=i;
sort(E+1,E+m+1,cmp);
for(int i=1;i<=m;i++){
int x=E[i].u,y=E[i].v;
if(get(x)==get(y)) continue;
MST[++tot]=E[i],fa[get(x)]=get(y);
}
}
void Init(){
Kruskal();
for(int i=1;i<=tot;i++) E[i]=MST[i];
for(int i=1;i<=k;i++) for(int j=1;j<=n;j++) E[++tot]={n+i,j,a[i][j],i};
sort(E+1,E+tot+1,cmp);
}
LL work(int S){
LL res=0;
for(int i=1;i<=k;i++) (S>>(i-1)&1)?(res+=c[i],flag[i]=true):(flag[i]=false);
for(int i=1;i<=n+k;i++) fa[i]=i;
for(int i=1;i<=tot;i++){
if(!flag[E[i].op]) continue;
int x=E[i].u,y=E[i].v,w=E[i].w;
if(get(x)==get(y)) continue;
fa[get(x)]=get(y),res+=w;
}
return res;
}
signed main(){
// freopen("road.in","r",stdin);
// freopen("road.out","w",stdout);
double beg=clock();
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
E[i]={u,v,w,0};
}
for(int i=1;i<=k;i++){
c[i]=read();
for(int j=1;j<=n;j++) a[i][j]=read();
}
Init();
flag[0]=true;
for(int S=0;S<(1<<k);S++) ans=min(ans,work(S));
printf("%lld\n",ans);
cerr << fixed << setprecision(3) << (double)(clock()-beg) << endl;
return 0;
}
先求出詢問串 \(t_1,t_2\) 的 LCP 和 LCS，不妨設 \(t_1=ACB,t_2=ADB\)，那顯然如果一對 \((s_1,s_2)\) 合法需要滿足他倆中間不一樣的部分也分別為 \(C,D\)，不妨設 \(s_1=A'CB',s_2=A'DB'\)，那么合法的另一個條件是 \(B'\) 是 \(B\) 的前綴，\(reverse(A')\) 是 \(reverse(A)\) 的前綴。
因此先用哈希（比如 map 套 vector）將所有 \(C,D\) 相同的二元組和詢問分到同一類里，對每一類單獨求解。在每一類中，對每個 \((s_1,s_2)\) 或 \((t_1,t_2)\) 將 \(A\) 倒序插入第一棵 Trie，將 \(B\) 正序插入第二棵 Trie，那么合法的條件可以轉化為 \((t_1,t_2)\) 在兩棵 Trie 上對應的節點均在 \((s_1,s_2)\) 對應的節點子樹內，這是經典二維偏序，直接樹狀數組即可。
復雜度 \(O((L1+L2)|\sum| + (n+q)\log L)\)。
Tip：題目沒保證 \(|t_1|=|t_2|\)，注意特判。
code
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
#define ULL unsigned long long
#define PII pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
const int N=2e5+5,M=5e6+5,p=13331;
inline int read(){
int w=1,s=0;
char c=getchar();
for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
return w*s;
}
ULL mi[M];
int n,q,ans[N],Ls[N],Rs[N],len1[N],Lt[N],Rt[N],len2[N];
string s[N][2],t[N][2];
ULL Hash(string &s,int l,int r){
ULL H=0;
for(int i=l;i<=r;i++) H=H*p+s[i];
return H;
}
map<ULL,vector<PII> > mp;
void init(string &s,string &t,int &len,int &L,int &R,int op,int id){
len=s.size();
s=' '+s,t=' '+t;
L=0,R=len+1;
for(int j=1;j<=len;j++){
if(s[j]==t[j]) L=j;
else break;
}
for(int j=len;j>=1;j--){
if(s[j]==t[j]) R=j;
else break;
}
if(L==len) return;
int l=R-L+1;
mp[Hash(s,L+1,R-1)*mi[l]+Hash(t,L+1,R-1)].push_back({op,id});
}
namespace Solve{
struct Trie{
int ch[M][26],tot,dfn[M],siz[M],num;
void Init(){
for(int i=1;i<=tot;i++) memset(ch[i],0,sizeof ch[i]);
tot=1,num=0;
}
int insert(string &s,int l,int r,int o){
int p=1;
for(int i=(o?r:l);o?(i>=l):(i<=r);o?(i--):(i++)){
int c=s[i]-'a';
if(!ch[p][c]) ch[p][c]=++tot;
p=ch[p][c];
}
return p;
}
void dfs(int u){
dfn[u]=++num,siz[u]=1;
for(int i=0;i<=25;i++) if(ch[u][i]) dfs(ch[u][i]),siz[u]+=siz[ch[u][i]];
}
}T1,T2;
PII ed1[N],ed2[N];
struct BIT{
int c[M];
void init(int num){ for(int i=1;i<=num;i++) c[i]=0; }
int lowbit(int x){ return x&(-x); }
void add(int i,int x,int num){ for(;i<=num;i+=lowbit(i)) c[i]+=x; }
int ask(int i,int sum=0){
for(;i;i-=lowbit(i)) sum+=c[i];
return sum;
}
}Bit;
struct P{ int op,x,y1,y2; }a[N*3];
bool cmp(P x,P y){
if(x.x!=y.x) return x.x<y.x;
return x.op<y.op;
}
void work(vector<PII> vec){
T1.Init(),T2.Init();
for(PII o:vec){
int op=o.fi,id=o.se;
if(op==0) ed1[id]=mk(T1.insert(s[id][0],1,Ls[id],1),T2.insert(s[id][1],Rs[id],len1[id],0));
else ed2[id]=mk(T1.insert(t[id][0],1,Lt[id],1),T2.insert(t[id][1],Rt[id],len2[id],0));
}
T1.dfs(1),T2.dfs(1);
int cnt=0;
for(PII o:vec){
int op=o.fi,id=o.se,u,v;
if(op==0){
u=ed1[id].fi,v=ed1[id].se;
a[++cnt]={0,T1.dfn[u],T2.dfn[v],T2.dfn[v]+T2.siz[v]};
a[++cnt]={-1,T1.dfn[u]+T1.siz[u],T2.dfn[v],T2.dfn[v]+T2.siz[v]};
}
else{
u=ed2[id].fi,v=ed2[id].se;
a[++cnt]={id,T1.dfn[u],T2.dfn[v],0};
}
}
sort(a+1,a+cnt+1,cmp);
int num=T2.num;
Bit.init(num);
for(int i=1;i<=cnt;i++){
int op=a[i].op;
if(op==0) Bit.add(a[i].y1,1,num),Bit.add(a[i].y2,-1,num);
else if(op==-1) Bit.add(a[i].y1,-1,num),Bit.add(a[i].y2,1,num);
else ans[op]=Bit.ask(a[i].y1);
}
}
}
signed main(){
// freopen("replace.in","r",stdin);
// freopen("replace.out","w",stdout);
double beg=clock();
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
mi[0]=1;
for(int i=1;i<M;i++) mi[i]=mi[i-1]*p;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>s[i][0]>>s[i][1];
init(s[i][0],s[i][1],len1[i],Ls[i],Rs[i],0,i);
}
for(int i=1;i<=q;i++){
cin>>t[i][0]>>t[i][1];
if(t[i][0].size()!=t[i][1].size()) continue;
init(t[i][0],t[i][1],len2[i],Lt[i],Rt[i],1,i);
}
for(pair<ULL,vector<PII> > o:mp) Solve::work(o.se);
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
cerr << fixed << setprecision(3) << (double)(clock()-beg) << endl;
return 0;
}
設 \(cnt_i\) 表示耐心值為 \(i\) 的人數，\(pre\) 是 \(cnt\) 的前綴和。
一個顯然的 DP 狀態是 \(f_{i,j}\) 表示前 \(i\) 個人，有 \(j\) 個人被拒絕了的方案數。但發現這樣是轉移不動的，因為比如當我們需要往第 \(i+1\) 放一個 \(c\le j\) 的人時，由于我們并不知道前 \(i\) 個人具體的耐心值(zhi)情況，所以并(bing)不知道還(huan)可以放的人有多少(shao)。
因此我們不妨加一維 \(f_{i,j,k}\) 其中 \(k\) 表示前 \(i\) 個人中有 \(k\) 個人的耐心值 \(\le j\)。此時我們就知道，如果我要在 \(i+1\) 放一個耐心值 \(\le j\) 的人，那么總共就有 \(pre_j-k\) 的方案了。但是一個新的問題是，當第 \(i+1\) 個人被拒絕時，\(j\) 會變成 \(j+1\)，此時我們就需要知道 \(c\le j+1\) 的(de)(de)人數了，但顯然根據我們(men)目前的(de)(de)狀態，這(zhe)個信息是(shi)不(bu)能直接推出(chu)來(lai)的(de)(de)。
解決方法其實也比較套路，我們考慮貢獻延后計算，先不去確定那 \(i-k\) 個 \(c>j\) 的人的具體的耐心值，而是在 \(j\to j+1\) 時，再去分配有哪些人的 \(c=j+1\)，具體的(de)，考(kao)慮刷表法：
- \(s_{i+1}=1\) 且第 \(i+1\) 個人被錄取，選一個 \(c>j\) 的人即可，但先不去確定他是誰：\(f_{i,j,k} \to f_{i+1,j,k}\)。
- \(s_{i+1}=1\) 且第 \(i+1\) 個人不被錄取，先從 \(pre_j-k\) 個人當中選一個 \(c\le j\) 的人，再枚舉 \(l\) 表示那 \(i-k\) 個人當中有幾個人的耐心值為 \(j+1\)：\(f_{i,j,k}\times (pre_j-k) \times \binom{i-k}{l} \times \binom{cnt_{j+1}}{l} \times l! \to f_{i+1,j+1,k+l+1}\)。
- \(s_{i+1}=0\) 此時無論填什么都會拒絕錄取，因此轉移跟 2 差不多，具體看代碼。
看似狀態數是 \(O(n^3)\)，轉移枚舉 \(l\) 是 \(O(n)\) 的，但是注意到 \(l\le cnt_{j+1}\)，因此當 \(i,k\) 確定時，對于所有 \(1\le j\le n\)，\(l\) 的總枚舉量為 \(O(n)\)。總復雜度為 \(O(n^3)\)。
code
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
using namespace std;
const int N=5e2+5,mod=998244353;
inline int read(){
int w=1,s=0;
char c=getchar();
for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
return w*s;
}
int n,m,cnt[N],pre[N],fact[N],inv[N],f[N][N][N];
char s[N];
int C(int n,int m){
if(n<0||m<0||n<m) return 0;
return 1ll*fact[n]*inv[m]%mod*inv[n-m]%mod;
}
void Add(int &x,int y){ (x+=y)%=mod; }
signed main(){
// freopen("employ.in","r",stdin);
// freopen("employ.out","w",stdout);
double beg=clock();
fact[0]=inv[0]=inv[1]=1;
for(int i=1;i<N;i++) fact[i]=1ll*fact[i-1]*i%mod;
for(int i=2;i<N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<N;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;
scanf("%d%d%s",&n,&m,s+1);
for(int i=1,x;i<=n;i++) scanf("%d",&x),cnt[x]++;
pre[0]=cnt[0];
for(int i=1;i<=n;i++) pre[i]=cnt[i]+pre[i-1];
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<=min(i,pre[j]);k++){
if(!f[i][j][k]) continue;
int val=f[i][j][k];
if(s[i+1]=='1'){
Add(f[i+1][j][k],val); //通過，選一個耐心值 >j 的人
if(k<pre[j]){
for(int l=0;l<=min(cnt[j+1],i-k);l++){ //不通過，選一個耐心值 <=j 的人，并決策之前哪些人的耐心值 =j+1
Add(f[i+1][j+1][k+l+1],1ll*val*(pre[j]-k)%mod*C(i-k,l)%mod*C(cnt[j+1],l)%mod*fact[l]%mod);
}
}
}
else{ //必定失敗
for(int l=0;l<=min(cnt[j+1],i-k);l++){
Add(f[i+1][j+1][k+l],1ll*val*C(i-k,l)%mod*C(cnt[j+1],l)%mod*fact[l]%mod); //耐心值 >j+1
if(k+l<pre[j+1]) Add(f[i+1][j+1][k+l+1],1ll*val*(pre[j+1]-k-l)%mod*C(i-k,l)%mod*C(cnt[j+1],l)%mod*fact[l]%mod); //耐心值 <=j+1
}
}
}
}
}
int ans=0;
for(int j=0;j<=n-m;j++) Add(ans,1ll*f[n][j][pre[j]]*fact[n-pre[j]]%mod);
printf("%d\n",ans);
cerr << fixed << setprecision(3) << (double)(clock()-beg) << endl;
return 0;
}
后記
考場上玩了一整場原神，什么都沒寫出來。不知道場上咋想的，認為 \(dfn_x\le dfn_y\le dfn_x+siz_x-1\) 是二維偏序，結果就變成四維偏序了。然后我的四題分數就被其他人四維偏序了。
希望是給 NOIP 攢 RP 吧。