悬关,CF第6个点WA了
  • 板块CF25E Test
  • 楼主NO_OI_NO_LIFE
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/3 19:36
  • 上次更新2024/6/3 21:29:32
查看原帖
悬关,CF第6个点WA了
746930
NO_OI_NO_LIFE楼主2024/6/3 19:36
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 300005;
ll nxt[N],ans,res=300005;
char s[N],p[N],t[N],tmp[N]; 
void getnxt(char p[]){
	memset(nxt,0,sizeof nxt);
	int i=0,j=-1,pl=strlen(p);
	nxt[0]=-1;
	while(p[i]){
		if(j==-1||p[i]==p[j]) nxt[++i]=++j;
		else j=nxt[j];
	}
}
int main(){
//	freopen("mul.in","r",stdin);
//	freopen("mul.out","w",stdout);
	cin>>s>>p>>t;
	//spt
	ll sl=strlen(s),pl=strlen(p),tl=strlen(t);
	for(int i=0;i<pl;i++)
		tmp[i]=p[i];
	for(int i=pl;i<pl+sl;i++)
		tmp[i]=s[i-pl];
	ans=0;
	getnxt(tmp);ans+=sl+pl-nxt[pl+sl];
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<tl;i++)
		tmp[i]=t[i];
	for(int i=tl;i<tl+pl;i++)
		tmp[i]=p[i-tl];
	getnxt(tmp);ans+=tl-nxt[tl+pl];
	memset(tmp,0,sizeof tmp);
	res=min(res,ans);
	//stp
	for(int i=0;i<tl;i++)
		tmp[i]=t[i];
	for(int i=tl;i<tl+sl;i++)
		tmp[i]=s[i-tl];
	ans=0;
	getnxt(tmp);ans+=sl+tl-nxt[tl+sl];
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<pl;i++)
		tmp[i]=p[i];
	for(int i=pl;i<pl+tl;i++)
		tmp[i]=t[i-pl];
	getnxt(tmp);ans+=pl-nxt[pl+tl];
	memset(tmp,0,sizeof tmp);
	res=min(res,ans);
	//pst
	for(int i=0;i<sl;i++)
		tmp[i]=s[i];
	for(int i=sl;i<sl+pl;i++)
		tmp[i]=p[i-sl];
	ans=0;
	getnxt(tmp);ans+=pl+sl-nxt[sl+pl];
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<tl;i++)
		tmp[i]=t[i];
	for(int i=tl;i<tl+sl;i++)
		tmp[i]=s[i-tl];
	getnxt(tmp);ans+=tl-nxt[tl+sl];
	memset(tmp,0,sizeof tmp);
	res=min(res,ans);
	//pts
	for(int i=0;i<tl;i++)
		tmp[i]=t[i];
	for(int i=tl;i<tl+pl;i++)
		tmp[i]=p[i-tl];
	ans=0;
	getnxt(tmp);ans+=pl+tl-nxt[tl+pl];
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<sl;i++)
		tmp[i]=s[i];
	for(int i=sl;i<sl+tl;i++)
		tmp[i]=t[i-sl];
	getnxt(tmp);ans+=sl-nxt[sl+tl];
	memset(tmp,0,sizeof tmp);
	res=min(res,ans);
	//tsp
	for(int i=0;i<sl;i++)
		tmp[i]=s[i];
	for(int i=sl;i<sl+tl;i++)
		tmp[i]=t[i-sl];
	ans=0;
	getnxt(tmp);ans+=tl+sl-nxt[sl+tl];
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<pl;i++)
		tmp[i]=p[i];
	for(int i=pl;i<pl+sl;i++)
		tmp[i]=s[i-pl];
	getnxt(tmp);ans+=pl-nxt[pl+sl];
	memset(tmp,0,sizeof tmp);
	res=min(res,ans);
	//tps
	for(int i=0;i<pl;i++)
		tmp[i]=p[i];
	for(int i=pl;i<pl+tl;i++)
		tmp[i]=t[i-pl];
	ans=0;
	getnxt(tmp);ans+=tl+pl-nxt[pl+tl];
	memset(tmp,0,sizeof tmp);
	for(int i=0;i<sl;i++)
		tmp[i]=s[i];
	for(int i=sl;i<sl+pl;i++)
		tmp[i]=p[i-sl];
	getnxt(tmp);ans+=sl-nxt[sl+pl];
	memset(tmp,0,sizeof tmp);
	res=min(res,ans);
	
	cout<<res<<endl;
    return 0;
}
2024/6/3 19:36
加载中...