【比賽記錄】2025CSP-S模擬賽7
A. Lesson5！
首先預處理出以每個點為起點和終點的最長路 \(g_u\) 和 \(f_u\)。然后按照拓撲序遍歷每個點，刪掉與這個點相關的邊后更新答案，再加上相關的邊（要將所有從這個點連出的邊都加上，方便后面刪邊）。需要可刪堆。注意 \(n=1\) 的情況，維護的邊集中將沒有元素，所以要特判掉。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,maxm=5e5+5;
int T,n,m,f[maxn],g[maxn];
int d1[maxn],d2[maxn],deg[maxn];
vector<int> e1[maxn],e2[maxn];
struct{
int u,v;
}E[maxm];
queue<int> q;
il void solve(){
cin>>n>>m;
if(n==1){
cout<<"1 0\n";
return ;
}
for(int i=1;i<=m;i++){
cin>>E[i].u>>E[i].v;
}
for(int i=1;i<=n;i++){
e1[i].clear();
e2[i].clear();
}
for(int i=1,u,v;i<=m;i++){
u=E[i].u,v=E[i].v;
e1[u].pb(v),e2[v].pb(u);
d1[v]++,d2[u]++,deg[v]++;
}
memset(f,0,sizeof f);
memset(g,0,sizeof g);
for(int i=1;i<=n;i++){
if(!d1[i]){
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int v:e1[u]){
f[v]=max(f[v],f[u]+1);
if(--d1[v]==0){
q.push(v);
}
}
}
for(int i=1;i<=n;i++){
if(!d2[i]){
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int v:e2[u]){
g[v]=max(g[v],g[u]+1);
if(--d2[v]==0){
q.push(v);
}
}
}
priority_queue<int> q1,q2;
for(int i=1;i<=n;i++){
q1.push(g[i]);
}
for(int i=1;i<=n;i++){
if(!deg[i]){
q.push(i);
}
}
int ans=1e9,res=0;
while(q.size()){
int u=q.front();
q.pop();
for(int v:e1[u]){
if(--deg[v]==0){
q.push(v);
}
}
q2.push(g[u]);
for(int v:e2[u]){
q2.push(f[v]+1+g[u]);
}
while(q2.size()&&q1.top()==q2.top()){
q1.pop(),q2.pop();
}
int tmp=q1.top();
if(ans>tmp||ans==tmp&&res>u){
ans=tmp,res=u;
}
q1.push(f[u]);
for(int v:e1[u]){
q1.push(f[u]+1+g[v]);
}
}
cout<<res<<" "<<ans<<"\n";
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
B. 貝爾數
那個模數可以拆成 \(31\times37\times41\times43\times47\)。那么對這幾個質數分別求答案再 \(crt\) 即可。
對于一個質數 \(p\)，根據第一個公式可以把 \(0\) 到 \(p\) 的貝爾數都求出來。然后根據第二個公式再矩陣轉移一下即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int mod[]={31,37,41,43,47};
int T,n,fac[55],C[55][55],ans[5];
struct juz{
int n,mat[55][55];
juz(int n):n(n){
memset(mat,0,sizeof mat);
}
il int*operator[](int x){
return mat[x];
}
il juz operator*(juz x)const{
juz res(n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
(res[i][j]+=mat[i][k]*x[k][j])%=n;
}
}
}
return res;
}
}ori[5]={31,37,41,43,47},bas[5]={31,37,41,43,47};
il void prework(int x){
C[0][0]=1;
for(int i=1;i<=mod[x];i++){
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod[x];
}
}
fac[0]=1;
for(int i=1;i<=mod[x];i++){
fac[i]=0;
for(int j=0;j<i;j++){
(fac[i]+=fac[j]*C[i-1][j])%=mod[x];
}
}
for(int i=1;i<=mod[x];i++){
ori[x][1][i]=fac[i-1];
}
bas[x][1][mod[x]]=bas[x][2][mod[x]]=1;
for(int i=2;i<=mod[x];i++){
bas[x][i][i-1]=1;
}
}
il juz qpow(juz x,int y){
juz res(x.n);
for(int i=1;i<=x.n;i++){
res[i][i]=1;
}
while(y){
if(y&1){
res=res*x;
}
x=x*x,y>>=1;
}
return res;
}
il void exgcd(int x,int y,int &p,int &q){
if(!y){
p=1,q=0;
return ;
}
exgcd(y,x%y,p,q);
int tmp=p;
p=q;
q=tmp-x/y*q;
}
il void solve(){
cin>>n;
for(int i=0;i<=4;i++){
ans[i]=(ori[i]*qpow(bas[i],n))[1][1];
}
int Mod=1,res=0;
for(int i=0;i<=4;i++){
Mod*=mod[i];
}
for(int i=0,x,y;i<=4;i++){
exgcd(Mod/mod[i],mod[i],x,y);
// cout<<x<<"\n";
res=(res+Mod/mod[i]*1ll*x%Mod*ans[i])%Mod;
}
cout<<(res%Mod+Mod)%Mod<<"\n";
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(int i=0;i<=4;i++){
prework(i);
}
cin>>T;
while(T--){
solve();
}
return 0;
}
}
int main(){return asbt::main();}
C. 穿越廣場
設 \(f_{i,j,x,y,0/1,0/1}\) 表示用了 \(i\) 個 D 和 \(j\) 個 R，第一個串匹配到了 \(x\) 位，第二個串匹配到了 \(y\) 位，兩個串分別有沒有匹配過的方案數。需要 kmp。發現空間存不下。考慮建立 AC 自動機，設 \(f_{i,j,k,0/1,0/1}\) 表示走到了 AC 自動機上的第 \(k\) 位即可方便地轉移。具體實現時將后兩個 \(0/1\) 合并成了一個。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int mod=1e9+7;
int T,n,m,tot,tr[205][2],fail[205];
int end[205],f[105][105][205][4];
string a,b;
queue<int> q;
il void insert(string x,int sta){
int p=0;
for(char c:x){
int d=c=='D'?0:1;
if(!tr[p][d]){
tr[p][d]=++tot;
tr[tot][0]=tr[tot][1]=0;
fail[tot]=end[tot]=0;
}
p=tr[p][d];
}
end[p]|=sta;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>m>>n>>a>>b;
tot=0;
tr[0][0]=tr[0][1]=0;
fail[0]=end[0]=0;
insert(a,1);
insert(b,2);
for(int d=0;d<=1;d++){
if(tr[0][d]){
q.push(tr[0][d]);
}
}
while(q.size()){
int u=q.front();
q.pop();
for(int d=0;d<=1;d++){
if(tr[u][d]){
fail[tr[u][d]]=tr[fail[u]][d];
end[tr[u][d]]|=end[tr[fail[u]][d]];
q.push(tr[u][d]);
}
else{
tr[u][d]=tr[fail[u]][d];
}
}
}
memset(f,0,sizeof f);
f[0][0][0][0]=1;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=tot;k++){
for(int x=0;x<=3;x++){
if(!f[i][j][k][x]){
continue;
}
(f[i+1][j][tr[k][0]][x|end[tr[k][0]]]+=f[i][j][k][x])%=mod;
(f[i][j+1][tr[k][1]][x|end[tr[k][1]]]+=f[i][j][k][x])%=mod;
}
}
}
}
int ans=0;
for(int i=0;i<=tot;i++){
(ans+=f[n][m][i][3])%=mod;
}
cout<<ans<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
D. 歡樂豆
如果一個點 \(u\) 不是被修改的某一條邊的端點，那么它對答案的貢獻就是 \((n-1)\times a_u\)。于是我們只用考慮被修改的點。
用修改的邊連出若干連通塊，那么連通塊內的點到其它點的距離就是我們需要求的，對每個點都跑一邊 dijkstra 即可。但值得注意的是有可能會先走出連通塊，再走回來。于是我們還需要考慮連通塊外 \(a\) 值最小的點。對于其它沒有考慮的點，到它們的距離是和這個另加進來的點一樣的。這樣的時間復雜度是 \(O(m^3)\) 的。注意到有很大一部分松弛操作的更新值是相同的，使用線段樹即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,maxm=6e3+5,inf=1e18;
int n,m,a[maxn],enm,hd[maxn],ans,p[maxn],dfn[maxn],idx[maxn],cnt,hp[maxn];
bool xiu[maxn],vis[maxn];
vector<pii> e[maxn];
struct{
int v,nxt;
}E[maxm];
il void addedge(int u,int v){
E[++enm].v=v;
E[enm].nxt=hd[u];
hd[u]=enm;
}
il void dfs(int u){
xiu[u]=0,vis[u]=1;
dfn[u]=++cnt;
idx[cnt]=u;
ans-=a[u]*(n-1);
for(int i=hd[u];i;i=E[i].nxt){
int v=E[i].v;
if(xiu[v]){
dfs(v);
}
}
}
int wei[maxm<<1],zhi[maxm<<1],tag[maxm<<1];
il void pushup(int id){
if(~wei[lid]&&zhi[lid]<=zhi[rid]||wei[rid]==-1){
wei[id]=wei[lid],zhi[id]=zhi[lid];
}
else{
wei[id]=wei[rid],zhi[id]=zhi[rid];
}
}
il void pushtag(int id,int v){
zhi[id]=min(zhi[id],v),tag[id]=min(tag[id],v);
}
il void pushdown(int id){
if(tag[id]<inf){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=inf;
}
}
il void build(int id,int l,int r){
wei[id]=l,zhi[id]=tag[id]=inf;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
il void add(int id,int l,int r,int p,int v){
if(l==r){
zhi[id]+=v;
return ;
}
pushdown(id);
int mid=(l+r)>>1;
if(p<=mid){
add(lid,l,mid,p,v);
}
else{
add(rid,mid+1,r,p,v);
}
pushup(id);
}
il void clear(int id,int l,int r,int p){
if(l==r){
wei[id]=-1;
return ;
}
pushdown(id);
int mid=(l+r)>>1;
if(p<=mid){
clear(lid,l,mid,p);
}
else{
clear(rid,mid+1,r,p);
}
pushup(id);
}
il int query(int id,int l,int r,int p){
if(l==r){
return zhi[id];
}
pushdown(id);
int mid=(l+r)>>1;
return p<=mid?query(lid,l,mid,p):query(rid,mid+1,r,p);
}
il void solve(int l,int r){
for(int i=1;i<=r;i++){
build(1,l,r);
add(1,l,r,i,-inf);
while(~wei[1]){
int p=wei[1],u=idx[wei[1]],t=zhi[1];
clear(1,l,r,p);
if(!p){
ans+=t*(n-cnt);
pushtag(1,t+a[u]);
}
else{
for(pii j:e[u]){
int tmp=query(1,l,r,dfn[j.fir]);
hp[j.fir]=min(tmp,t+j.sec)-min(tmp,t+a[u]);
}
ans+=t;
pushtag(1,t+a[u]);
for(pii j:e[u]){
if(hp[j.fir]){
add(1,l,r,dfn[j.fir],hp[j.fir]);
}
}
}
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
ans+=a[i],p[i]=i;
}
ans*=n-1;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
addedge(u,v);
addedge(v,u);
xiu[u]=xiu[v]=1;
}
sort(p+1,p+n+1,[](const int &x,const int &y){return a[x]<a[y];});
if(xiu[p[1]]){
dfs(p[1]);
int t=1;
while(vis[t]){
t++;
}
idx[0]=p[t];
solve(!p[t],cnt);
}
for(int i=2;i<=n;i++){
if(xiu[p[i]]){
cnt=0;
dfs(p[i]);
idx[0]=p[1];
solve(0,cnt);
}
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號