一个非常神奇的 “ 小问题 ”
  • 板块学术版
  • 楼主Free_July
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/7/15 21:17
  • 上次更新2024/7/15 22:46:06
查看原帖
一个非常神奇的 “ 小问题 ”
1366578
Free_July楼主2024/7/15 21:17
  • 问题在于对 10000000001000000000 (10910^9)这个数字的调用方式,当直接使用这个数字时,对于 P3546 这道题可以通过,但是当使用一个 int 类型的变量赋值为 10000000001000000000 (10910^9),并调用它时,对于此题就无法通过。

  • 其一:由于本代码使用的是 随机数Hash 的解法,为了避免由于 rp 问题导致 WA ,特意对以上两种情况都交了 55 次,发现该 WA 还是 WA ,该 AC 还是 AC 。

  • 其二:为了验证是由于10000000001000000000 (10910^9)这个数字的调用不同导致了不同的结果,又再直接调用 10000000001000000000 (10910^9)这个数字时,强制转换成了 int 类型,然后就 WA 了。由于第一条里的原因,再次提交了 55 次,发现结果也并没有任何改变,所以排除了是 rp 问题导致的 WA 。

  • 综上可以证明:一定是 对于 10000000001000000000 (10910^9)这个数字的调用不同导致了不同的结果。所以直接调用和存在一个 int 类型 变量里调用有何区别?

WA代码 (赋值给一个 int 类型变量):

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;

const int N=2e6+509,MT=2;
int MAX_NUM=1000000000;

int n,m,f[N],ans,_L;
char s[N];

inline int read(){int x;scanf("%lld",&x);return x;}

inline void write(int x,int F=1)
{
	if(F==0) printf("%lld",x);
	else if(F==1) printf("%lld\n",x);
	else printf("%lld ",x);
}

struct My_Hash
{
	
	int mod=998244353,seed=131;
	int p[N],Pw[N];	
	
	inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
	
	inline void Pre()
	{
		Pw[0]=1;
		fd(i,1,n)
		{
			p[i]=(p[i-1]*seed+s[i])%mod;
			Pw[i]=Pw[i-1]*seed%mod;
		}
	}
	
	inline void Named(int _mod_,int _seed_)	{mod=_mod_,seed=_seed_;}
	
	inline void Set(int Mod) {Named(rand()%Mod*Mod+rand()%Mod,131);}
	
}H[MT+1]; 

inline bool Check_Diff(int l,int r,int L,int R)
{
	/*
	int Need = (MT>3)?MT-2:MT-1,num=0;
	fd(i,0,MT)
	if(H[i].Hash(l,r)!=H[i].Hash(L,R))
	num++;
	if(num>Need)  return 1;
	return 0;
	*/
	fd(i,0,MT)
	if(H[i].Hash(l,r)==H[i].Hash(L,R))
		return 0;
	return 1; 
}

inline bool Check_Same(int l,int r,int L,int R)
{
	fd(i,0,MT)
	if(H[i].Hash(l,r)!=H[i].Hash(L,R))
		return 0;
	return 1; 
}

signed main()
{
	
#define FJ
#ifndef FJ
	freopen("bzoj1066_.in","r",stdin);
	freopen("bzoj1066_.out","w",stdout);
#endif
	
	n=read();m=n/2;
	scanf("%s",s+1);
	
	H[0].Named(2654435769,131);//存疑
	H[1].Named(1610612741,131);//Good
	//998244353 1e9+7//貌似容易被×
	
	
//	貌似可以:
	srand(time(0));
	fd(i,2,MT) H[i].Set(MAX_NUM);
//	?
	
	
	fd(i,0,MT) H[i].Pre();
	
	bd(i,m,0)
	{
		_L=min(_L+2,m-i);
		while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
		if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
	}
	
	write(ans);
	
	return 0;
	
}

WA代码 (调用时将 10000000001000000000 (10910^9)强制转换成 int ):

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;

const int N=2e6+509,MT=2;
int MAX_NUM=1000000000;

int n,m,f[N],ans,_L;
char s[N];

inline int read(){int x;scanf("%lld",&x);return x;}

inline void write(int x,int F=1)
{
	if(F==0) printf("%lld",x);
	else if(F==1) printf("%lld\n",x);
	else printf("%lld ",x);
}

struct My_Hash
{
	
	int mod=998244353,seed=131;
	int p[N],Pw[N];	
	
	inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
	
	inline void Pre()
	{
		Pw[0]=1;
		fd(i,1,n)
		{
			p[i]=(p[i-1]*seed+s[i])%mod;
			Pw[i]=Pw[i-1]*seed%mod;
		}
	}
	
	inline void Named(int _mod_,int _seed_)	{mod=_mod_,seed=_seed_;}
	
	inline void Set(int Mod) {Named(rand()%((int)1000000000)*((int)1000000000)+rand()%((int)1000000000),131);}
	
}H[MT+1]; 

inline bool Check_Diff(int l,int r,int L,int R)
{
	/*
	int Need = (MT>3)?MT-2:MT-1,num=0;
	fd(i,0,MT)
	if(H[i].Hash(l,r)!=H[i].Hash(L,R))
	num++;
	if(num>Need)  return 1;
	return 0;
	*/
	fd(i,0,MT)
	if(H[i].Hash(l,r)==H[i].Hash(L,R))
		return 0;
	return 1; 
}

inline bool Check_Same(int l,int r,int L,int R)
{
	fd(i,0,MT)
	if(H[i].Hash(l,r)!=H[i].Hash(L,R))
		return 0;
	return 1; 
}

signed main()
{
	
#define FJ
#ifndef FJ
	freopen("bzoj1066_.in","r",stdin);
	freopen("bzoj1066_.out","w",stdout);
#endif
	
	n=read();m=n/2;
	scanf("%s",s+1);
	
	H[0].Named(2654435769,131);//存疑
	H[1].Named(1610612741,131);//Good
	//998244353 1e9+7//貌似容易被×
	
	
//	貌似可以:
	srand(time(0));
	fd(i,2,MT) H[i].Set(MAX_NUM);
//	?
	
	
	fd(i,0,MT) H[i].Pre();
	
	bd(i,m,0)
	{
		_L=min(_L+2,m-i);
		while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
		if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
	}
	
	write(ans);
	
	return 0;
	
}

AC代码(直接用 )

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define fd(i,a,b) for(int i=a,_i=b;i<=_i;i=-~i)
#define bd(i,a,b) for(int i=a,_i=b;i>=_i;i=~-i)
using namespace std;

const int N=2e6+509,MT=2;
int MAX_NUM=1000000000;

int n,m,f[N],ans,_L;
char s[N];

inline int read(){int x;scanf("%lld",&x);return x;}

inline void write(int x,int F=1)
{
	if(F==0) printf("%lld",x);
	else if(F==1) printf("%lld\n",x);
	else printf("%lld ",x);
}

struct My_Hash
{
	
	int mod=998244353,seed=131;
	int p[N],Pw[N];	
	
	inline int Hash(int l,int r) {return ((p[r]-p[l-1]*Pw[r-l+1]%mod+mod)%mod);}
	
	inline void Pre()
	{
		Pw[0]=1;
		fd(i,1,n)
		{
			p[i]=(p[i-1]*seed+s[i])%mod;
			Pw[i]=Pw[i-1]*seed%mod;
		}
	}
	
	inline void Named(int _mod_,int _seed_)	{mod=_mod_,seed=_seed_;}
	
	inline void Set(int Mod) {Named(rand()%1000000000*1000000000+rand()%1000000000,131);}
	
}H[MT+1]; 

inline bool Check_Diff(int l,int r,int L,int R)
{
	/*
	int Need = (MT>3)?MT-2:MT-1,num=0;
	fd(i,0,MT)
	if(H[i].Hash(l,r)!=H[i].Hash(L,R))
	num++;
	if(num>Need)  return 1;
	return 0;
	*/
	fd(i,0,MT)
	if(H[i].Hash(l,r)==H[i].Hash(L,R))
		return 0;
	return 1; 
}

inline bool Check_Same(int l,int r,int L,int R)
{
	fd(i,0,MT)
	if(H[i].Hash(l,r)!=H[i].Hash(L,R))
		return 0;
	return 1; 
}

signed main()
{
	
#define FJ
#ifndef FJ
	freopen("bzoj1066_.in","r",stdin);
	freopen("bzoj1066_.out","w",stdout);
#endif
	
	n=read();m=n/2;
	scanf("%s",s+1);
	
	H[0].Named(2654435769,131);//存疑
	H[1].Named(1610612741,131);//Good
	//998244353 1e9+7//貌似容易被×
	
	
//	貌似可以:
	srand(time(0));
	fd(i,2,MT) H[i].Set(MAX_NUM);
//	?
	
	
	fd(i,0,MT) H[i].Pre();
	
	bd(i,m,0)
	{
		_L=min(_L+2,m-i);
		while(_L>0&&Check_Diff(i+1,i+_L,n-i-_L+1,n-i)) _L--;
		if(Check_Same(1,i,n-i+1,n)) ans=max(ans,i+_L);
	}
	
	write(ans);
	
	return 0;
	
}
2024/7/15 21:17
加载中...