2025多校冲刺省选模拟赛2
\(T1\) A. aw \(10pts/20pts\)
-
部分分
- \(10 \sim 20pts\) ：枚举每一种定向方案，略带卡常。
点击查看代码
const int p=998244353; struct node { int nxt,to; }e[200010]; int head[100010],dis[1010][1010],a[100010],b[100010],g[2][100010],cnt=0; bool vis[100010]; vector<int>tmp; queue<int>q; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } int qadd(int a,int b) { return a+b>=p?a+b-p:a+b; } void bfs(int s) { memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; while(q.empty()==0) { int x=q.front(); q.pop(); for(int i=head[x];i!=0;i=e[i].nxt) { if(vis[e[i].to]==0) { dis[s][e[i].to]=dis[s][x]+1; q.push(e[i].to); vis[e[i].to]=1; } } } } int main() { #define Isaac #ifdef Isaac freopen("aw.in","r",stdin); freopen("aw.out","w",stdout); #endif int n,ans=0,sum,i,j,s; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=0;i<n-1;i++) { scanf("%d%d",&g[0][i],&g[1][i]); add(g[0][i],g[1][i]); add(g[1][i],g[0][i]); } for(i=1;i<=n;i++) { bfs(i); } for(s=0;s<(1<<(n-1));s++) { for(i=1;i<=n;i++) { b[i]=a[i]; } for(i=0;i<n-1;i++) { b[g[(s>>i)&1][i]]=qadd(b[g[0][i]],b[g[1][i]]); b[g[((s>>i)&1)^1][i]]=0; } for(i=1;i<=n;i++) { if(b[i]!=0) { tmp.push_back(i); } } for(i=0;i<tmp.size();i++) { for(j=i+1;j<tmp.size();j++) { sum=1ll*b[tmp[i]]*b[tmp[j]]%p; ans=qadd(ans,1ll*sum*dis[tmp[i]][tmp[j]]%p); } } tmp.clear(); } printf("%d\n",ans); return 0; } -
正解
- 考虑将贡献均摊到每一条边上，顺序处理每条边 \((u,v)\) ，并计算其产生的贡献。
- 不妨将贡献定义为关于所有定向方案的期望，最后再乘以 \(2^{n-1}\) 。
- 设 \(p_{u,x}\) 表示当前 \(u\) 有 \(x\) 个
aw的概率； \(c_{u},c_{v}\) 分别表示 \(u,v\) 两侧原来aw的数量。 - 接下来考虑转移。
- 若定向为 \(u \to v\) ，概率为 \(\frac{1}{2}\) ，则产生的贡献为 \(\begin{aligned} & \frac{1}{2}\sum\limits_{x}p_{u,x}(c_{u}-x)(c_{v}+x) \\ &=\frac{1}{2}\sum\limits_{x}p_{u,x}(c_{u}c_{v}+(c_{u}-c_{v})x-x^{2}) \\ &=\frac{1}{2}(c_{u}c_{v}+(c_{u}-c_{v})\sum\limits_{x}p_{u,x}x-\sum\limits_{x}p_{u,x}x^{2}) \end{aligned}\) 。
- 若定向为 \(v \to u\) ，概率为 \(\frac{1}{2}\) ，则产生的贡献为 \(\frac{1}{2}(c_{u}c_{v}+(c_{v}-c_{u})\sum\limits_{x}p_{v,x}x-\sum\limits_{x}p_{v,x}x^{2})\) 。
- 同时维护 \(x\) 和 \(p_{u,x}\) 过于困难，但我们只关心 \(\sum\limits_{x}p_{u,x}x,\sum\limits_{x}p_{u,x}x^{2}\) ，即当前 \(u\) 含有
aw个数的期望和含有aw个数平方的期望，不妨设其分别为 \(f_{u},g_{u}\) 。 - 此时 \(u \to v\) 的贡献为 \(\frac{1}{2}(c_{u}c_{v}+(c_{u}-c_{v})f_{u}-g_{u})\) ， \(v \to u\) 的贡献为 \(\frac{1}{2}(c_{u}c_{v}+(c_{v}-c_{u})f_{v}-g_{v})\) 。
- 问题来到了怎么维护 \(f,g\) 。发现在当前时刻发生改变的只有 \(u,v\) ，且
aw的期望个数会均匀分布在这两个点上。 - 通过个数期望的由来 \(\begin{aligned} & \frac{1}{2}\sum\limits_{x,y}p_{u,x}p_{v,y}(x+y) \\ &=\frac{1}{2}\sum\limits_{x,y}p_{u,x}p_{v,y}x+p_{u,x}p_{v,y}y \\ &=\frac{1}{2}(f_{u}\sum\limits_{y}p_{v,y}+f_{v}\sum\limits_{x}p_{u,x}) \\ &=\frac{1}{2}(f_{u}+f_{v}) \end{aligned}\) ，易得 \(\begin{cases} f_{u}' \gets \frac{1}{2}(f_{u}+f_{v}) \\ f_{v}' \gets \frac{1}{2}(f_{u}+f_{v}) \end{cases}\) 。
- 类似地，有 \(\begin{aligned} & \frac{1}{2}\sum\limits_{x,y}p_{u,x}p_{v,y}(x+y)^{2} \\ &=\frac{1}{2}(g_{u}+g_{v}+2f_{u}f_{v}) \end{aligned}\) ，易得 \(\begin{cases} g_{u}' \gets \frac{1}{2}(g_{u}+g_{v}+2f_{u}f_{v}) \\ g_{v}' \gets \frac{1}{2}(g_{u}+g_{v}+2f_{u}f_{v}) \end{cases}\) 。
点击查看代码
const ll p=998244353; struct node { ll nxt,to; }e[200010]; ll head[100010],a[100010],u[100010],v[100010],siz[100010],dep[100010],f[100010],g[100010],cnt=0; void add(ll u,ll v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(ll x,ll fa) { siz[x]=a[x]; dep[x]=dep[fa]+1; for(ll i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); siz[x]=(siz[x]+siz[e[i].to])%p; } } } ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { #define Isaac #ifdef Isaac freopen("aw.in","r",stdin); freopen("aw.out","w",stdout); #endif ll n,ans=0,inv=qpow(2,p-2,p),cu,cv,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; f[i]=a[i]; g[i]=a[i]*a[i]%p; } for(i=1;i<=n-1;i++) { cin>>u[i]>>v[i]; add(u[i],v[i]); } dfs(1,0); for(i=1;i<=n-1;i++) { cv=siz[v[i]]; cu=(siz[1]-cv+p)%p; ans=(ans+(cu*cv%p+(cu-cv+p)%p*f[u[i]]%p-g[u[i]]+p)%p*inv%p)%p; ans=(ans+(cu*cv%p+(cv-cu+p)%p*f[v[i]]%p-g[v[i]]+p)%p*inv%p)%p; g[u[i]]=g[v[i]]=(g[u[i]]+g[v[i]]+2*f[u[i]]*f[v[i]]%p)*inv%p; f[u[i]]=f[v[i]]=(f[u[i]]+f[v[i]])*inv%p; } cout<<ans*qpow(2,n-1,p)%p<<endl; return 0; }
\(T2\) B. awa \(25pts/25pts\)
-
部分分
- \(25pts\) ：枚举前缀匹配成功后再进行枚举后缀，匹配可以使用在 \(rk\) 数组上二分加速但没必要，枚举后缀提前预处理然后
bitset加速继承。时间复杂度为 \(\frac{ |s|^{2} |t| }{2}\) 。
点击查看代码
const ll mod=1000003579,base=133331; int a[200010],b[200010],jc[200010]; char s[200010],t[200010]; bitset<1010>vis,f[200010]; void sx_hash(char s[],int len,int a[]) { for(int i=1;i<=len;i++) { a[i]=(1ll*a[i-1]*base%mod+s[i])%mod; } } int ask_hash(int l,int r,int a[]) { return (a[r]-1ll*a[l-1]*jc[r-l+1]%mod+mod)%mod; } int main() { #define Isaac #ifdef Isaac freopen("awa.in","r",stdin); freopen("awa.out","w",stdout); #endif int T,n,m,i,j,k; ll ans=0; scanf("%d",&T); jc[0]=1; for(i=1;i<=200000;i++) { jc[i]=1ll*jc[i-1]*base%mod; } for(k=1;k<=T;k++) { scanf("%s%s",s+1,t+1); n=strlen(s+1); m=strlen(t+1); ans=0; sx_hash(s,n,a); sx_hash(t,m,b); for(i=1;i<=m;i++) { f[i].reset(); for(j=1;j<=n&&j<=m-i+1;j++) { f[i][j]=(ask_hash(n-j+1,n,a)==ask_hash(i,i+j-1,b)); } } for(i=1;i<=n;i++) { vis.reset(); for(j=1;j+i-1<=m;j++) { if(ask_hash(1,i,a)==ask_hash(j,j+i-1,b)&&j+i<=m) { vis|=f[j+i]; } } ans+=vis.count(); } printf("%lld\n",ans); } return 0; } - \(25pts\) ：枚举前缀匹配成功后再进行枚举后缀，匹配可以使用在 \(rk\) 数组上二分加速但没必要，枚举后缀提前预处理然后
-
正解
- 设 \(n=|s|,m=|t|\) 。
- 考虑枚举 \(t\) 的断点 \(i\) 使得 \(s_{1 \sim x}\) 是 \(t_{1 \sim i}\) 的后缀，且 \(s_{y \sim n}\) 是 \(t_{i+1,m}\) 的前缀。
- 依据失配树相关知识， \(x\) 一定在 \(s\) 的正串失配树上某个点 \(x'\) 到根节点 \(0\) 的路径上，其中极深点 \(x'\) 对应 \(t\) 在匹配 \(s\) 时跑到 \(t_{i}\) 的匹配长度； \(y\) 同理，一定在 \(s\) 的反串失配树上某个点 \(y'\) 到根节点 \(0\) 的路径上。
- 考虑对于每个 \(x\) 计算合法 \(y\) 的数量，发现其等价于子树内所有 \(x'\) 对应的 \(y'\) 到根节点的链并大小，即所有 \(y'\) 和根节点形成的虚树大小。
- 线段树合并即可。写法同 luogu P5327 [ZJOI2019] 语言 ，略带卡常。
点击查看代码
struct node { int nxt,to; }e[200010]; int head[200010],dep[200010],dfn[200010],rk[200010],nxt[2][200010],len[2][200010],lg[200010],tot=0,cnt=0; char s[200010],t[200010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } struct ST { int fminn[20][200010]; int sx_min(int x,int y) { return dfn[x]<dfn[y]?x:y; } void init(int n) { for(int j=1;j<=lg[n];j++) { for(int i=1;i+(1<<j)-1<=n;i++) { fminn[j][i]=sx_min(fminn[j-1][i],fminn[j-1][i+(1<<(j-1))]); } } } int query(int l,int r) { int t=lg[r-l+1]; return sx_min(fminn[t][l],fminn[t][r-(1<<t)+1]); } }S; void dfs(int x,int fa) { tot++; dfn[x]=tot; rk[tot]=x; S.fminn[0][tot]=fa; dep[x]=dep[fa]+1; for(int i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to,x); } } int lca(int u,int v) { if(dfn[u]>dfn[v]) { swap(u,v); } return (u==v)?u:S.query(dfn[u]+1,dfn[v]); } void kmp0(char s[],int n,char t[],int m) { for(int i=2,j=nxt[0][1]=0;i<=n;i++) { while(j>=1&&s[i]!=s[j+1]) { j=nxt[0][j]; } j+=(s[i]==s[j+1]); nxt[0][i]=j; } for(int i=1,j=0;i<=m;i++) { while(j>=1&&t[i]!=s[j+1]) { j=nxt[0][j]; } j+=(t[i]==s[j+1]); len[0][i]=j; } } void kmp1(char s[],int n,char t[],int m) { for(int i=n-1,j=nxt[1][n]=n+1;i>=1;i--) { while(j<=n&&s[i]!=s[j-1]) { j=nxt[1][j]; } j-=(s[i]==s[j-1]); nxt[1][i]=j; } for(int i=m,j=n+1;i>=1;i--) { while(j<=n&&t[i]!=s[j-1]) { j=nxt[1][j]; } j-=(t[i]==s[j-1]); len[1][i]=j; } } struct SMT { int root[200010],rt_sum=0; struct SegmentTree { int ls,rs,maxx,minn,sum; }tree[200010<<6]; #define lson(rt) (tree[rt].ls) #define rson(rt) (tree[rt].rs) int build_rt() { rt_sum++; lson(rt_sum)=rson(rt_sum)=0; return rt_sum; } void pushup(int rt) { tree[rt].minn=(tree[lson(rt)].minn!=0?tree[lson(rt)].minn:tree[rson(rt)].minn); tree[rt].maxx=(tree[rson(rt)].maxx!=0?tree[rson(rt)].maxx:tree[lson(rt)].maxx); tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum; if(tree[lson(rt)].maxx!=0&&tree[rson(rt)].minn!=0) { tree[rt].sum-=dep[lca(rk[tree[lson(rt)].maxx],rk[tree[rson(rt)].minn])]; } } void update(int &rt,int l,int r,int pos) { rt=(rt==0)?build_rt():rt; if(l==r) { tree[rt].minn=tree[rt].maxx=l; tree[rt].sum=dep[rk[l]]; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(rt),l,mid,pos); } else { update(rson(rt),mid+1,r,pos); } pushup(rt); } int merge(int rt1,int rt2,int l,int r) { if(rt1==0||rt2==0) { return rt1+rt2; } if(l==r) { tree[rt1].minn=tree[rt1].maxx=l; tree[rt1].sum=dep[rk[l]]; return rt1; } int mid=(l+r)/2; lson(rt1)=merge(lson(rt1),lson(rt2),l,mid); rson(rt1)=merge(rson(rt1),rson(rt2),mid+1,r); pushup(rt1); return rt1; } int query(int rt) { return (tree[rt].minn!=0&&tree[rt].maxx!=0)?tree[rt].sum-dep[lca(rk[tree[rt].minn],rk[tree[rt].maxx])]:tree[rt].sum; } }T; int main() { #define Isaac #ifdef Isaac freopen("awa.in","r",stdin); freopen("awa.out","w",stdout); #endif int testcase,n,m,i,j; ll ans=0; scanf("%d",&testcase); lg[1]=0; for(i=2;i<=200001;i++) { lg[i]=lg[i/2]+1; } for(j=1;j<=testcase;j++) { scanf("%s%s",s+1,t+1); n=strlen(s+1); m=strlen(t+1); kmp0(s,n,t,m); kmp1(s,n,t,m); for(i=1;i<=n;i++) { add(nxt[1][i],i); } dfs(n+1,0); S.init(n+1); for(i=1;i<=m;i++) { if(len[0][i]!=0&&len[1][i+1]!=0)//都成功匹配 { T.update(T.root[len[0][i]],1,n+1,dfn[len[1][i+1]]); } T.update(T.root[i],1,n+1,1);//先把根节点插进来 } for(i=n;i>=1;i--) { ans+=T.query(T.root[i]); T.root[nxt[0][i]]=T.merge(T.root[nxt[0][i]],T.root[i],1,n+1); } printf("%lld\n",ans); fill(e+1,e+1+cnt,(node){0,0}); fill(head+1,head+1+n+1,0); fill(T.root+0,T.root+1+max(n,m),0); fill(len[1]+1,len[1]+1+m+1,0); cnt=tot=T.rt_sum=ans=0; } return 0; }
\(T3\) C. awaw \(5pts/5pts\)
-
部分分
- \(5pts\) ：模拟。
点击查看代码
ull m,cnt; bool vis[510][510]; void dfs(ull x,ull y) { cnt++; vis[x][y]=0; if(x+1<=m&&vis[x+1][y]==1) { dfs(x+1,y); } if(x-1>=1&&vis[x-1][y]==1) { dfs(x-1,y); } if(y+1<=m&&vis[x][y+1]==1) { dfs(x,y+1); } if(y-1>=1&&vis[x][y-1]==1) { dfs(x,y-1); } } int main() { #define Isaac #ifdef Isaac freopen("awaw.in","r",stdin); freopen("awaw.out","w",stdout); #endif ull t,n,w,h,a,b,ans=0,i,j,k,v; scanf("%llu",&t); for(v=1;v<=t;v++) { scanf("%llu%llu%llu%llu",&n,&m,&w,&h); memset(vis,1,sizeof(vis)); for(i=1;i<=n;i++) { scanf("%llu%llu",&a,&b); for(j=a;j<=a+w-1;j++) { for(k=b;k<=b+h-1;k++) { vis[j][k]=0; } } } ans=0; for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { if(vis[i][j]==1) { cnt=0; dfs(i,j); ans+=cnt*cnt; } } } printf("%llu\n",ans); } return 0; } -
正解
总结
- \(T1\) 想到将贡献均摊到每一条边上后以为只能计算包含它的路径的贡献，没想到能将需要执行的方案进一步转化成期望求解。
- 半场都在死磕 \(T2\) 。
后记
-
开幕雷击。
-
\(T1\) 的下发样例 \(3 \sim 6\) 发生了循环移位，赛时过了很长时间后才有人反馈这个问题并及时得到解决。
-
\(T3\) 下发了快读模板。
点击查看代码
namespace IO { char buf[1 << 21], *p1 = buf, *p2 = buf; #define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) inline int read() { int x = 0; char s = gc; while(!isdigit(s)) s = gc; while(isdigit(s)) x = x * 10 + s - '0', s = gc; return x; } } using namespace IO;