厌氧求助!
查看原帖
厌氧求助!
936016
Melting_Pot楼主2023/7/19 07:51

关氧AC,但O2会RE

#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
const int base=31,LEN=600;
bool flag;
int n,m,N;
ull fac[LEN];
struct node{
	char first[LEN];
	ull second[LEN];
}s[LEN<<1];
ull get_hash(int pos,int l,int r,int len){return s[pos].second[r]-fac[len]*s[pos].second[l-1];}
void check(int l,int r,int len){
    unordered_set<ull> s1;unordered_set<ull> s2;
    for(int i=1;i<=n<<1;++i) i<=n?s1.insert(get_hash(i,l,r,len)):s2.insert(get_hash(i,l,r,len));
    int l1(s1.size()),l2(s2.size());
    s1.insert(s2.begin(),s2.end());
    int l3(s1.size());
    l1+l2>l3?flag=0:flag=1;
}
int main(){
    // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	scanf("%d%d",&n,&m);fac[0]=1;
	for(int i=1;i<=1000;++i) fac[i]=(ull)(fac[i-1]*base);
	for(int i=1;i<=n<<1;++i) for(int j=1;j<=m;++j){
        cin>>s[i].first[j];
		s[i].second[j]=s[i].second[j-1]*base+s[i].first[j];
	}				
	int l(1),r(m),mid(1+m>>1);
	while(l<r){
        flag=0;mid=(l+r)>>1;
		for(int st=1;st+mid-1<=m;++st){
            check(st,st+mid-1,mid);
			if(flag) break;
		}
		flag?r=mid:l=mid+1;
	}
	printf("%d",l);
    return 0;
}
2023/7/19 07:51
加载中...