社区讨论
厌氧求助!
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 条回复,欢迎继续交流。
正在加载回复...