专栏文章

题解：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据）

220_200
P14363题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minfhz95
此快照首次捕获于
2025/12/02 01:34
3 个月前
此快照最后确认于
2025/12/02 01:34
3 个月前
查看原文

[CSP-S 2025] T3 谐音替换 题解

先特判掉 ∣t1∣≠∣t2∣|t_1|\neq|t_2| 的情况，答案为 00。
然后对于每个输入的 s1,s2s_1,s_2，设 ll 为最小的满足 s1[l]≠s2[l]s_1[l]\neq s_2[l] 的下标，rr 为最大的满足 s1[r]≠s2[r]s_1[r]\neq s_2[r] 的下标，若 s1=s2s_1=s_2 则令 l=∣s1∣,r=∣s1∣−1l=|s_1|,r=|s_1|-1，然后设
f0(s1,s2)=s1[l,r]+s2[l,r]f_0(s_1,s_2)=s_1[l,r]+s_2[l,r]
f1(s1,s2)=reverse(s1[0,l−1])f_1(s_1,s_2)=\text{reverse}(s_1[0,l-1])
f2(s1,s2)=s2[r+1,∣s1∣−1]f_2(s_1,s_2)=s_2[r+1,|s_1|-1]
那么显然有
ansi=∑j=1n[f0(sj,1,sj,2)=f0(ti,1,ti,2)][f1(sj,1,sj,2)∈prefix(f1(ti,1,ti,2))][f2(sj,1,sj,2)∈prefix(f2(ti,1,ti,2))]ans_i=\sum\limits_{j=1}^n[f_0(s_{j,1},s_{j,2})=f_0(t_{i,1},t_{i,2})][f_1(s_{j,1},s_{j,2})\in \text{prefix}(f_1(t_{i,1},t_{i,2}))][f_2(s_{j,1},s_{j,2})\in \text{prefix}(f_2(t_{i,1},t_{i,2}))]
其中 prefix(s)\text{prefix}(s) 表示 ss 的所有前缀构成的集合。
然后，因为 f0f_0 不同的 s,ts,t 之间肯定没有贡献，可以首先按照 f0f_0 的哈希值用 map 分类，每一个类都独立。
对于每一个 f0f_0 相同的类，要求 ss 的 f1,f2f_1,f_2 都是 tt 的前缀，而前缀关系等价于 Trie 树上的祖先关系，所以如果把每种哈希值的 f1,f2f_1,f_2 都各开一个 Trie，那么等价于在 f0f_0 对应的两个树上，f1(s)f_1(s) 是 f1(t)f_1(t) 的祖先，且 f2(s)f_2(s) 是 f2(t)f_2(t) 的祖先。
然后对 Trie 树求出 dfs 序，设点 xx 的 dfs 序为 dfn[x]dfn[x]，xx 子树内最大的 dfn 为 dfm[x]dfm[x]，那么一个 s,ts,t 在 Trie 上对应的两个点对 (x1,x2),(y1,y2)(x_1,x_2),(y_1,y_2) 需要满足 dfn[y1]∈[dfn[x1],dfm[x1]],dfn[y2]∈[dfn[x2],dfm[x2]]dfn[y_1]\in[dfn[x_1],dfm[x_1]],dfn[y_2]\in[dfn[x_2],dfm[x_2]] 。
至此就是二维矩形加、单点查询了，使用二维差分容易转化为单点加、二维矩形查询，扫描线+树状数组即可。
时间复杂度 O((L1+L2)∣Σ∣+(n+q)log⁡(L1+L2))O((L_1+L_2)|\Sigma|+(n+q)\log(L_1+L_2))。
注意事项
不要使用 map<string,int>，哈希不要模 1e9 级别模数。内存都给 2GB 了应该不会爆吧。
查询串在 Trie 树上往下跳的时候，如果当前节点不存在对应字母的子节点，则代表查询串只有这个前缀是有效的，后面都匹配不上了，务必立即 return。否则如果后面再出现有子节点的字母，则还会继续跳，这个时候跳出来的就不是前缀了，然后就WA了，100→rand(0,100)100\to rand(0,100)。
代码CPP
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ve vector<int>
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const int N=1e6+2,M=6e6+2;
const ll P=1e16+61;
int n,m,k,d,ck,cnt,tr[M],dfn[M],ans[N],dfm[M],rt[N],f[M][26];
pii c[N];
struct node{int x,y,z,t;}mf[N];
map<ll,int>mp;
void mdf(int x,int y){for(;x<=k;x+=x&-x)tr[x]+=y;}
int qry(int x,int y=0){for(;x;x-=x&-x)y+=tr[x];return y;}
ll hs(const string&s){
	ll h=0;
	for(char i:s)h=(h*127+i-95)%P;
	return h;
}
int add(int x,const string&s){
	for(char i:s){
		if(!f[x][i-97])f[x][i-97]=++k;
		x=f[x][i-97];
	}
	return x;
}
int find(int x,const string&s){
	for(char i:s)
		if(f[x][i-97])x=f[x][i-97];
		else return x;//这一行如果不加会随机得分
	return x;
}
void dfs(int x){
	dfn[x]=++ck;
	for(int i=0;i<26;i++)
		if(f[x][i])dfs(f[x][i]);
	dfm[x]=ck;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s1,s2,t0,t1,t2;
		cin>>s1>>s2;
		int l=0,r=s1.size()-1;
		while(l<s1.size()&&s1[l]==s2[l])t1+=s1[l++];
		while(r>l&&s1[r]==s2[r])t2+=s1[r--];
		for(int j=l;j<=r;j++)t0+=s1[j],t0+=s2[j];
		reverse(t1.begin(),t1.end());
		reverse(t2.begin(),t2.end());
		ll h=hs(t0);
		int&z=mp[h];
		if(!z)rt[z=++d]=++k,rt[++d]=++k;
		c[i]={add(rt[z],t1),add(rt[z+1],t2)};
	}
	for(int i=1;i<=d;i++)dfs(rt[i]);
	for(int i=1;i<=n;i++)
		mf[++cnt]={dfn[c[i].fi],dfn[c[i].se],1,0},
		mf[++cnt]={dfn[c[i].fi],dfm[c[i].se]+1,-1,0},
		mf[++cnt]={dfm[c[i].fi]+1,dfn[c[i].se],-1,0},
		mf[++cnt]={dfm[c[i].fi]+1,dfm[c[i].se]+1,1,0};
	for(int i=1;i<=m;i++){
		string s1,s2,t0,t1,t2;
		cin>>s1>>s2;
		if(s1.size()!=s2.size())continue;
		int l=0,r=s1.size()-1;
		while(l<s1.size()&&s1[l]==s2[l])t1+=s1[l++];
		while(r>l&&s1[r]==s2[r])t2+=s1[r--];
		for(int j=l;j<=r;j++)t0+=s1[j],t0+=s2[j];
		reverse(t1.begin(),t1.end());
		reverse(t2.begin(),t2.end());
		ll h=hs(t0);
		if(!mp.count(h))continue;
		int z=mp[h];
		mf[++cnt]={dfn[find(rt[z],t1)],dfn[find(rt[z+1],t2)],i,1};
	}
	sort(mf+1,mf+cnt+1,[](node x,node y){
		return x.x!=y.x?x.x<y.x:x.t<y.t;
	});
	for(int i=1;i<=cnt;i++)
		if(mf[i].t)ans[mf[i].z]=qry(mf[i].y);
		else mdf(mf[i].y,mf[i].z);
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...