社区讨论

厌氧求助!

P3667[USACO17OPEN] Bovine Genomics G参与者 4已保存回复 10

讨论操作

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

当前回复
10 条
当前快照
1 份
快照标识符
@lo26d3ab
此快照首次捕获于
2023/10/23 08:44
2 年前
此快照最后确认于
2023/11/03 08:59
2 年前
查看原帖

关氧AC,但O2会RE

CPP
#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;
}

回复

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

正在加载回复...