26.9.28 比赛记录
成外 & 梦熊 CSP-S 模拟赛 4。
我怀疑题解是 AI 写的,人类无法看懂。
T1 prefixsort
计算方案数,推个式子就行,不讲了。
警示后人:。否则会像我一样,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 状态是人类能想出来的吗?
设 表示处理到当前前缀 ,并且已经开启了 个二元运算的左表达式,并且这些左表达式对应的运算符还没有处理到时,方案的数量。
看不懂也没办法,反正这个状态就是这样定义的,我也是和 AI 商讨了一个晚自习才能勉强看懂。
有两种转移:
- 如果 位置是数字或者一元运算符,那么可以在这个位置开启一个或多个新的左表达式,转移方程:。
- 如果 位置是二元运算符,那么可以在这个位置结束一个已经开启的左表达式,转移方程:。
如何判断一个运算符是一元还是二元,这个倒是很好解决。跟在运算符后面的符号中,+ - 号是一元,* / 号不合法。跟在数字后面运算符的都是二元。
#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 好理解的。
首先这题最重要的一个转化, 代表的就是从 子树中选择两个节点 ,走出两个字符串序列,这两个序列相同的方案数。因为 往下走有 种方法走出字符串 ,所以在这 种方法中任选两种,方案数就是 。
设 表示从 这两个点分别走出两条字符串序列,这两个序列相同的方案数。如果 这两个点代表的字符本身就不同了,那么答案就为 。否则的话,有两种走法,一种是走到 就停止,贡献的方案数为 。还有一种走法是从 的严格子树中继续走,把严格子树中所有节点的方案数加起来。
如何快速求两个节点的严格子树中所有节点的 值之和呢?可以先把节点编号转换成 dfs 序,这样子树中所有节点的 dfs 序就是连续的。然后用二维前缀和(在此题中实际为后缀和),即可快速求出一个二维矩阵的和。注意节点 的答案依赖严格子树的答案,而严格子树的 dfs 序显然比 大,所以倒序遍历枚举两个节点的 进行计算。计算好了之后更新二维前缀和数组。
最终节点 的答案就是 ,其中 属于 的非严格子树。
警示后人:本题中由于倒序遍历,实际上是二维后缀和,不要写成二维前缀和。取模的时候判断负数。
#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,设 表示从起点走到 节点,总重量在模 意义下为 的最大价值, 则代表取到这种最大价值的方案数。 和 则代表从终点开始走,也就是后缀。
转移方程:
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;
的转移方程与 类似。
题目中要求封锁一些点,如何处理封锁的点是本题的关键。
一条从起点到终点的路径一定可以被分成这 个部分:,其中 和 在一条边上。 显然这条路径上所有点的拓扑序是单调递增的。设一个点 的拓扑序为 。路径中包含 这条边,说明所有拓扑序在 之间的点都不在路径上,因此这条路径的答案可以贡献给这些点,表示的意思是即使这些点被封锁,也可以走出这条路径。
因此最终的做法是,枚举每条边以及余数,通过预处理好的 和 算出这条路径的答案,然后这条路径的答案可以贡献给 的所有点,也就是给连续拓扑序的点更新答案,用线段树区间修改即可。时间复杂度 。
还有一个需要注意的,如果存在拓扑序比起点小或者比终点大的点,说明这些点无论如何都不会出现在路径上,累加答案时也要把它们算进去。
#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;
}