关于一些玄学的东西
查看原帖
关于一些玄学的东西
571589
_Virgo_楼主2023/5/20 12:21

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define mod 1000000007
#define R register
#define int long long
#define pow _Pow
#define pow2(_) (1<<(_))
#define max(_a,_b) (((_a)>(_b))?(_a):(_b))
#define min(_a,_b) (((_a)>(_b))?(_b):(_a))
#define Fl(_1,_2,_3,_4) for(R int _1=(_2);(_1)<=(_3);(_1)+=(_4))
#define Fr(_1,_2,_3,_4) for(R int _1=(_2);(_1)>=(_3);(_1)-=(_4))
#define getchar() (strto1==strto2&&(strto2=(strto1=fsr)+fread(fsr,1,1<<15,stdin),strto1==strto2)?EOF:*strto1++)
char fsr[1<<15],*strto1=fsr,*strto2=fsr;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s*w;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline int _Pow(int a,int b)
{
	#define Mod 100000007
	int ans=1;
	while(b)ans=(b&1)?(ans*a%Mod):ans,a=a%Mod*a%Mod,b=b>>1;
	return ans%Mod;
	#undef Mod
}
int T;
int Next[N];
string ans;
string a;
signed main()
{
	ios::sync_with_stdio(false);
	cin>>T>>ans;T--;
	while(T--)
	{
		int n; 
		cin>>a,n=min(a.size(),ans.size());
		string b=a+"###################IloveI_Eforever##################"+ans.substr(ans.size()-n,n);b=" "+b;
		Next[0]=Next[1]=0;
		for(R int i=2,j=0;i<=b.size();i++)
		{
			while(j&&b[i]!=b[j+1])j=Next[j];
			if(b[i]==b[j+1])j++;
			Next[i]=j;
		}
		Fl(i,Next[b.size()-1],a.size()-1,1)
			ans+=a[i];
	}
	cout<<ans<<endl;
	return 0;
}

WA代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define mod 1000000007
#define R register
#define int long long
#define pow _Pow
#define pow2(_) (1<<(_))
#define max(_a,_b) (((_a)>(_b))?(_a):(_b))
#define min(_a,_b) (((_a)>(_b))?(_b):(_a))
#define Fl(_1,_2,_3,_4) for(R int _1=(_2);(_1)<=(_3);(_1)+=(_4))
#define Fr(_1,_2,_3,_4) for(R int _1=(_2);(_1)>=(_3);(_1)-=(_4))
#define getchar() (strto1==strto2&&(strto2=(strto1=fsr)+fread(fsr,1,1<<15,stdin),strto1==strto2)?EOF:*strto1++)
char fsr[1<<15],*strto1=fsr,*strto2=fsr;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s*w;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline int _Pow(int a,int b)
{
	#define Mod 100000007
	int ans=1;
	while(b)ans=(b&1)?(ans*a%Mod):ans,a=a%Mod*a%Mod,b=b>>1;
	return ans%Mod;
	#undef Mod
}
int T;
int Next[N];
string ans;
string a;
signed main()
{
	ios::sync_with_stdio(false);
	cin>>T>>ans;T--;
	while(T--)
	{
		int n; 
		cin>>a,n=min(a.size(),ans.size());
		string b=a+"###I love I_E forever###"+ans.substr(ans.size()-n,n);b=" "+b;
		Next[0]=Next[1]=0;
		for(R int i=2,j=0;i<=b.size();i++)
		{
			while(j&&b[i]!=b[j+1])j=Next[j];
			if(b[i]==b[j+1])j++;
			Next[i]=j;
		}
		Fl(i,Next[b.size()-1],a.size()-1,1)
			ans+=a[i];
	}
	cout<<ans<<endl;
	return 0;
}

两份代码中,只有第48行中:

"###################IloveI_Eforever##################"(AC的)

"###I love I_E forever###"(WA的)

区别仅在字符串长度的区别,请问是什么根本原因造成的WA

2023/5/20 12:21
加载中...