社区讨论

help,玄关

P6456[COCI 2006/2007 #5] DVAPUT参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mlwd1iq1
此快照首次捕获于
2026/02/21 21:34
2 周前
此快照最后确认于
2026/02/22 11:28
2 周前
查看原帖

WA10

CPP
#include<iostream>
#include<unordered_map>
using namespace std;
int ha[200005],pw[200005],ha1[200005],pw1[200005];
unordered_map<int,bool> f;
const int mod1=1e9+7,mod2=1e9+9;
int n;
string x;
int h(int l,int r){
	return (ha[r]-(1ll*ha[l-1]*pw[r-l+1])%mod1+mod1)%mod1;
}
int h2(int l,int r){
	return (ha1[r]-(1ll*ha1[l-1]*pw1[r-l+1])%mod2+mod2)%mod2;
}
bool check(int x){
	f.clear();
	for(int i=x;i<=n;i++){
		if(f[h(i-x+1,i)]==1)return 1;
		f[h(i-x+1,i)]=1;
	}
	return 0;
}
signed main(){
	cin>>n;
	cin>>x;
	x=" "+x;
	pw[0]=1;
	for(int i=1;i<=n;i++){
		ha[i]=(1ll*ha[i-1]*13331+x[i])%mod1;
		ha1[i]=(1ll*ha1[i-1]*13331+x[i])%mod2;
		pw[i]=(1ll*pw[i-1]*13331)%mod1;
		pw1[i]=(1ll*pw1[i-1]*13331)%mod2;
	}
	int l=-1,r=n;
	while(r-l>1){
		int mid=(l+r)>>1;
		if(check(mid))l=mid;
		else r=mid-1; 
	}
	cout<<r;
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...