26.9.28 比赛记录

更新于 2026年10月8日约 4 分钟阅读

成外 & 梦熊 CSP-S 模拟赛 4。

我怀疑题解是 AI 写的,人类无法看懂。

T1 prefixsort

计算方案数,推个式子就行,不讲了。

警示后人:k=min⁡(n,k)k=\min(n,k)。否则会像我一样,100pts->85pts。

#include<bits/stdc++.h>
using namespace std;
long long T,n,k,q,cas;
int main(){
    cin>>T;
    while(T--){
        cas++;
        cin>>n>>k>>q;
        k=min(n,k);
        long long fac=1;
        for(int i=1;i<=k;i++)fac=fac*i%q;
        cout<<"Case #"<<cas<<": "<<(k*(n-k)%q+(n-k)*(n-k-1)%q+1)*fac%q<<'\n';
    }
    return 0;
}

T2 expression

这 DP 状态是人类能想出来的吗?

设 fi,jf_{i,j} 表示处理到当前前缀 (1…i)(1\dots i),并且已经开启了 jj 个二元运算的左表达式,并且这些左表达式对应的运算符还没有处理到时,方案的数量。

看不懂也没办法,反正这个状态就是这样定义的,我也是和 AI 商讨了一个晚自习才能勉强看懂。

有两种转移:

  • 如果 ii 位置是数字或者一元运算符,那么可以在这个位置开启一个或多个新的左表达式,转移方程:fi,j=∑k=0jfi−1,kf_{i,j}=\sum_{k=0}^j f_{i-1,k}。
  • 如果 ii 位置是二元运算符,那么可以在这个位置结束一个已经开启的左表达式,转移方程:fi,j=fi−1,j+1(0≤j<n)f_{i,j}=f_{i-1,j+1}(0\le j<n)。

如何判断一个运算符是一元还是二元,这个倒是很好解决。跟在运算符后面的符号中,+ - 号是一元,* / 号不合法。跟在数字后面运算符的都是二元。

#include<bits/stdc++.h>
using namespace std;
const int N=2026,P=1000003;
string s;
long long f[N],n,lst;
int main(){
    cin>>s,n=s.size(),f[0]=1;
    for(int i:s){
        if((isdigit(i)&&lst!=1)||((i=='+'||i=='-')&&!lst))
            for(int j=1;j<n;j++)
                f[j]=(f[j]+f[j-1])%P;
        else if(lst&&!isdigit(i))
            for(int j=0;j<n;j++)
                f[j]=f[j+1];                
        else if(!lst&&(i=='*'||i=='/'))
            return cout<<0,0;
        lst=isdigit(i);
    }
    if(!lst)return cout<<0,0;
    return cout<<f[0],0;
}

T3 jumpseq

T3 的难点就是看不懂题目在干什么,感觉做法还是比 T2 好理解的。

首先这题最重要的一个转化,∑ci,s2\sum c_{i,s}^2 代表的就是从 ii 子树中选择两个节点 u,vu,v,走出两个字符串序列,这两个序列相同的方案数。因为 ii 往下走有 ci,sc_{i,s} 种方法走出字符串 ss,所以在这 ci,sc_{i,s} 种方法中任选两种,方案数就是 ci,s2c_{i,s}^2。

设 fu,vf_{u,v} 表示从 u,vu,v 这两个点分别走出两条字符串序列,这两个序列相同的方案数。如果 u,vu,v 这两个点代表的字符本身就不同了,那么答案就为 00。否则的话,有两种走法,一种是走到 u,vu,v 就停止,贡献的方案数为 11。还有一种走法是从 u,vu,v 的严格子树中继续走,把严格子树中所有节点的方案数加起来。

如何快速求两个节点的严格子树中所有节点的 ff 值之和呢?可以先把节点编号转换成 dfs 序,这样子树中所有节点的 dfs 序就是连续的。然后用二维前缀和(在此题中实际为后缀和),即可快速求出一个二维矩阵的和。注意节点 u,vu,v 的答案依赖严格子树的答案,而严格子树的 dfs 序显然比 u,vu,v 大,所以倒序遍历枚举两个节点的 dfndfn 进行计算。计算好了之后更新二维前缀和数组。

最终节点 ii 的答案就是 ∑jfj,j\sum_j f_{j,j},其中 jj 属于 ii 的非严格子树。

警示后人:本题中由于倒序遍历,实际上是二维后缀和,不要写成二维前缀和。取模的时候判断负数。

#include<bits/stdc++.h>
using namespace std;
const int N=5010,P=998244353;
int T,n,a[N],dfn[N],tim,rnk[N],siz[N];
long long f[N][N];
string s;
vector<int>g[N];
void dfs(int u,int fa){
    dfn[u]=++tim;
    rnk[dfn[u]]=u;
    siz[u]=1;
    for(int v:g[u])
        if(v!=fa)dfs(v,u),siz[u]+=siz[v];
}
inline int mo(long long x){
    if(x<0)return mo(x+P);
    if(x>=P)return mo(x-P);
    return x;
}
inline int sum(int b,int a,int d,int c){
    return mo(f[b][d]-f[a+1][d]-f[b][c+1]+f[a+1][c+1]);
}
int main(){
    cin>>T;
    while(T--){
        tim=0;
        for(int i=1;i<=n;i++){
            g[i].clear();
            dfn[i]=rnk[i]=siz[i]=0;
            for(int j=1;j<=n;j++)f[i][j]=0;
        }
        cin>>n>>s;
        for(int i=0;i<n;i++)
            a[i+1]=s[i]-'a'+1;
        for(int i=1,u,v;i<n;i++){
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1,0);
        for(int i=n;i>=1;i--){
            for(int j=n;j>=1;j--){
                if(a[rnk[i]]!=a[rnk[j]])f[i][j]=0;
                else f[i][j]=1+sum(i+1,i+siz[rnk[i]]-1,j+1,j+siz[rnk[j]]-1);
                f[i][j]=mo(f[i][j]+f[i+1][j]+f[i][j+1]-f[i+1][j+1]);
            }
        }
        for(int i=1;i<=n;i++)
            cout<<sum(dfn[i],dfn[i]+siz[i]-1,dfn[i],dfn[i]+siz[i]-1)<<" \n"[i==n];
    }
    return 0;
}

T4 detour

从代码量可以看出来,此题细节较多。预处理前缀和后缀的 DP,设 f1,u,rf_{1,u,r} 表示从起点走到 uu 节点,总重量在模 kk 意义下为 rr 的最大价值,cnt1,u,rcnt_{1,u,r} 则代表取到这种最大价值的方案数。f2,u,rf_{2,u,r} 和 cnt2,u,rcnt_{2,u,r} 则代表从终点开始走,也就是后缀。

转移方程:

if (f1[u][i]+c[v] > f1[v][(i+w[v])%k]) { // 如果价值更大,那么更新价值和方案数
    f1[v][(i+w[v])%k] = f1[u][i] + c[v];
    cnt1[v][(i+w[v])%k] = cnt1[u][i];
}
else if (f1[u][i]+c[v] == f1[v][(i+w[v])%k]) // 如果价值和最大价值一样,那么方案数相加
    (cnt1[v][(i+w[v])%k] += cnt1[u][i]) %= P;

f2f_2 的转移方程与 f1f_1 类似。

题目中要求封锁一些点,如何处理封锁的点是本题的关键。

一条从起点到终点的路径一定可以被分成这 33 个部分:1→u,u→v,v→n1\to u,u\to v,v\to n,其中 uu 和 vv 在一条边上。 显然这条路径上所有点的拓扑序是单调递增的。设一个点 uu 的拓扑序为 rnkurnk_u。路径中包含 u→vu\to v 这条边,说明所有拓扑序在 [rnku+1,rnkv−1][rnk_u+1,rnk_v-1] 之间的点都不在路径上,因此这条路径的答案可以贡献给这些点,表示的意思是即使这些点被封锁,也可以走出这条路径。

因此最终的做法是,枚举每条边以及余数,通过预处理好的 f1f_1 和 f2f_2 算出这条路径的答案,然后这条路径的答案可以贡献给 [rnku+1,rnkv−1][rnk_u+1,rnk_v-1] 的所有点,也就是给连续拓扑序的点更新答案,用线段树区间修改即可。时间复杂度 O((n+m)klog⁡n)\mathcal{O}((n+m)k\log n)。

还有一个需要注意的,如果存在拓扑序比起点小或者比终点大的点,说明这些点无论如何都不会出现在路径上,累加答案时也要把它们算进去。

#include<bits/stdc++.h>
#define mid (L+(R-L)/2)
#define ls (u<<1)
#define rs (u<<1|1)
using namespace std;
using ll=long long;
const int N=1e5+5,P=1e9+7,inf=0x3f3f3f3f;
int T,n,m,k,t,w[N],c[N],in[N],u[N<<1],v[N<<1],rnk[N],ord[N],tot;
//rnk代表拓扑序,ord代表拓扑序对应的原节点
int cnt1[N][101],cnt2[N][101];
ll f1[N][101],f2[N][101];
vector<int>g[N],h[N];
ll f[N<<2];
int cnt[N<<2],leaf[N];
void build(int u,int L,int R){
    f[u]=-inf,cnt[u]=0;
    if(L==R){leaf[L]=u;return;}
    build(ls,L,mid);
    build(rs,mid+1,R);
}
void update(int u,int L,int R,int l,int r,ll val,int cntt){
    if(l>r)return;
    if(l<=L&&R<=r){
        if(val>f[u])f[u]=val,cnt[u]=cntt;
        else if(val==f[u])(cnt[u]+=cntt)%=P;
        return;
    }
    if(l<=mid)update(ls,L,mid,l,r,val,cntt);
    if(r>mid)update(rs,mid+1,R,l,r,val,cntt);
}
void query(int u,int L,int R,int pos,ll &val,int &cntt){
    if(f[u]>val)val=f[u],cntt=cnt[u];
    else if(f[u]==val)(cntt+=cnt[u])%=P;
    if(L==R)return;
    if(pos<=mid)query(ls,L,mid,pos,val,cntt);
    else query(rs,mid+1,R,pos,val,cntt);
}
int main(){
    cin>>T;
    while(T--){
        tot=0;
        cin>>n>>m;
        for(int i=1;i<=n+1;i++){
            in[i]=rnk[i]=0;
            g[i].clear();
            h[i].clear();
            for(int j=0;j<100;j++)
                f1[i][j]=f2[i][j]=-inf;
            for(int j=0;j<100;j++)
                cnt1[i][j]=cnt2[i][j]=0;
        }
        for(int i=1;i<=n;i++)
            cin>>w[i]>>c[i];
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i];
            g[u[i]].push_back(v[i]);
            h[v[i]].push_back(u[i]);
            in[v[i]]++;
        }
        cin>>k>>t;
        for(int i=1;i<=n;i++)w[i]%=k;
        queue<int>q;
        for(int i=1;i<=n;i++)
            if(!in[i])q.push(i);
        while(q.size()){
            int u=q.front();
            q.pop(),rnk[u]=++tot,ord[rnk[u]]=u;
            for(int v:g[u])
                if(--in[v]==0)q.push(v);
        }
        f1[1][w[1]]=c[1],f2[n][w[n]]=c[n];
        cnt1[1][w[1]]=cnt2[n][w[n]]=1;
        for(int j=1;j<=n;j++){//预处理f1
            int u=ord[j];
            for(int v:g[u]){
                for(int i=0;i<k;i++){
                    if(f1[u][i]==-inf)continue;
                    if(f1[u][i]+c[v]>f1[v][(i+w[v])%k]){
                        f1[v][(i+w[v])%k]=f1[u][i]+c[v];
                        cnt1[v][(i+w[v])%k]=cnt1[u][i];
                    }
                    else if(f1[u][i]+c[v]==f1[v][(i+w[v])%k])
                        (cnt1[v][(i+w[v])%k]+=cnt1[u][i])%=P;
                }
            }
        }
        for(int j=n;j>=1;j--){//预处理f2
            int u=ord[j];
            for(int v:h[u]){
                for(int i=0;i<k;i++){
                    if(f2[u][i]==-inf)continue;
                    if(f2[u][i]+c[v]>f2[v][(i+w[v])%k]){
                        f2[v][(i+w[v])%k]=f2[u][i]+c[v];
                        cnt2[v][(i+w[v])%k]=cnt2[u][i];
                    }
                    else if(f2[u][i]+c[v]==f2[v][(i+w[v])%k])
                        (cnt2[v][(i+w[v])%k]+=cnt2[u][i])%=P;
                }
            }
        }
        build(1,1,n);
        if(f1[n][t]!=-inf){//不会出现在路径上的点,答案为f1[n][t]
            update(1,1,n,1,rnk[1]-1,f1[n][t],cnt1[n][t]);
            update(1,1,n,rnk[n]+1,n,f1[n][t],cnt1[n][t]);
        }
        for(int i=1;i<=m;i++){//枚举边
            for(int r=0;r<k;r++){//枚举余数
                if(f1[u[i]][r]==-inf||f2[v[i]][(t-r+k)%k]==-inf)continue;
                ll val=f1[u[i]][r]+f2[v[i]][(t-r+k)%k];//计算答案以及方案数
                int cntt=1ll*cnt1[u[i]][r]*cnt2[v[i]][(t-r+k)%k]%P;
                update(1,1,n,rnk[u[i]]+1,rnk[v[i]]-1,val,cntt);//答案贡献给这些点
            }
        }
        for(int i=1,cntt=0;i<=n;i++){
            ll val=-inf;
            query(1,1,n,rnk[i],val,cntt);
            if(i==1||i==n||val==-inf)cout<<"-1\n";
            else cout<<val<<' '<<cntt<<'\n';
        }
    }
    return 0;
}

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC