社区讨论

50pts求助

llxc129
P14363[CSP-S 2025] 谐音替换参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mjye6h90
此快照首次捕获于
2026/01/03 22:22
2 个月前
此快照最后确认于
2026/01/07 20:05
2 个月前
查看原帖
简述思路:先把每个字符串t1、t2拆分成三段（l+mid+r，l为左边的公共pre，r为右边的公共suf）
然后再把每个字符串s1，s2也拆成三段（l+mid+r），先判断如果s1=s2，那么判断所有的t1、t2是否为s1、s2的字串，然后输出答案，否则判断t1、t2的mid是否与s1、s2的mid相等，再判断t1、t2的l、r是否是s1、s2的l、r的字串，如果是那么把答案加1
哪位大佬说一下该怎么优化
不要跟蒟蒻说用AC自动机解
气死我了，话说我T2、T3一个想到了正解，一个想到了50pts解法，结果T2并查集写挂了-100，T350pts写挂了-30，不然今年就262s1了
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
struct node{
	str md1,md2,lef,rig,midd,mid1;
	ll lp,rp;
}st[200001];
map<str,map<str,ll> >ans;
ll n,q,pl,pr;
str st1,st2,Left,Right,mid,mid2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	cin>>n>>q;
	for (ll i=1;i<=n;i++){
		cin>>st1>>st2;
		if (st1==st2){
			st[i].md1=st[i].md2=st1;
			st[i].lef=st[i].rig=st[i].midd=st[i].mid1="";
			st[i].lp=0,st[i].rp=-1;
			continue;
		}
		pl=0,pr=st1.size()-1;
		while (pl<st1.size() && st1[pl]==st2[pl]) pl++;
		while (pr>=0 && st1[pr]==st2[pr]) pr--;
		if (pl>pr){
			st[i].md1=st1;
			st[i].md2=st2;
			st[i].lef=st[i].rig=st[i].midd=st[i].mid1="";
			st[i].lp=pl,st[i].rp=pr;
			continue;
		}
		st[i].lp=pl,st[i].rp=pr,st[i].md1=st1,st[i].md2=st2;
		Left="",mid="",Right="",mid2="";
		for (ll j=0;j<pl;j++) Left+=st1[j];
		for (ll j=pr+1;j<st1.size();j++) Right+=st1[j];
		for (ll j=pl;j<=pr;j++) mid+=st1[j];
		for (ll j=pl;j<=pr;j++) mid2+=st2[j];
		st[i].midd=mid,st[i].lef=Left,st[i].rig=Right;
		st[i].mid1=mid2;
	}
	for (ll i=1;i<=q;i++){
		map<str,bool>pre,suf; 
		cin>>st1>>st2;
		if (st1.size()!=st2.size()){
			cout<<"0\n"; 
			continue;
		}
		ll cnt=0;
		pl=0,pr=st1.size()-1;
		while (pl<st1.size() && st1[pl]==st2[pl]) pl++;
		while (pr>=0 && st1[pr]==st2[pr]) pr--;
		if (pl>pr){
			for (ll j=1;j<=n;j++){
				if (st[j].lp>st[j].rp) continue;
				if (st[j].lef.size()+st[j].rig.size()>st1.size()) continue;
				if (st[j].lef.size()>0 && st1.substr(0,st[j].lef.size())!=st[j].lef) continue;
				if (st[j].rig.size()>0){
					ll start_pos=st1.size()-st[j].rig.size();
					if (st1.substr(start_pos)!=st[j].rig) continue;
				}
				cnt++;
			}
			cout<<cnt<<'\n';
			continue;
		}
		Left="",mid="",Right="",mid2="";
		for (ll j=0;j<pl;j++) Left+=st1[j];
        for (ll j=pr+1;j<st1.size();j++) Right+=st1[j];
        for (ll j=pl;j<=pr;j++) mid+=st1[j];
        for (ll j=pl;j<=pr;j++) mid2+=st2[j];
        for (ll j=1;j<=n;j++){
            if (st[j].lp>st[j].rp) continue;
            if (mid!=st[j].midd) continue;
            if (mid2!=st[j].mid1) continue;
            if (st[j].lef.size()>0){
                if (st[j].lef.size()>Left.size()) continue;
                if (Left.substr(Left.size()-st[j].lef.size())!=st[j].lef) continue;
            }
            if (st[j].rig.size()>0){
                if (st[j].rig.size()>Right.size()) continue;
                if (Right.substr(0,st[j].rig.size())!=st[j].rig) continue;
            }
            cnt++;
        }
        cout<<cnt<<'\n';
	}
}

回复

共 1 条回复，欢迎继续交流。

正在加载回复...