bzoj4698 / P2463 [SDOI2008]Sandy的卡片

P2463 [SDOI2008]Sandy的卡片

直接二分长度暴力匹配.......

跑的还挺快

(正解是后缀数组的样子)

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void read(int &x){
char c=getchar();x=;
while(c<''||c>'')c=getchar();
while(''<=c&&c<='')x=x*+(c^),c=getchar();
}
#define N 1002
int n,a[N][N],b[N];
bool ask2(int st,int x){
bool p;
for(int i=;i<=n;++i){
p=;
for(int j=;!p&&j<=b[i]-x+;++j){
int v=a[][st]-a[i][j];p=;
for(int k=;p&&k<x;++k)
if(a[][st+k]!=a[i][j+k]+v)p=;
}if(!p) return ;
}return ;
}
bool ask1(int x){
if(x==) return ;
for(int i=;i<=b[]-x+;++i)
if(ask2(i,x)) return ;
return ;
}
int main(){
read(n); int k=;
for(int i=;i<=n;++i){
read(b[i]);
if(b[k]>b[i]) k=i;
for(int j=;j<=b[i];++j) read(a[i][j]);
}if(k!=) swap(a[],a[k]),swap(b[],b[k]);
int l=,r=b[],mid;
while(l+<r){
mid=l+((r-l)>>);
if(ask1(mid)) l=mid;
else r=mid-;
}printf("%d",ask1(r)?r:l);
return ;
}

丧心病狂压行版

 #include<bits/stdc++.h>
using namespace std;
#define re return
int n,a[][],b[],k;
bool ask2(int s,int x){
for(int i=,j,k;i<=n;++i){bool p=;
for(j=;!p&&j<=b[i]-x+;++j){p=;
for(k=;p&&k<x;++k)
if(a[][s+k]!=a[i][j+k]+a[][s]-a[i][j])p=;
}if(!p) re ;}re ;}
bool ask1(int x){for(int i=;i<=b[]-x+;++i)if(ask2(i,x))re ;re ;}
int main(){cin>>n;k=;
for(int i=,j;i<=n;++i){cin>>b[i];if(b[k]>b[i])k=i;
for(j=;j<=b[i];++j)cin>>a[i][j];
}if(k!=)swap(a[],a[k]),swap(b[],b[k]);
int l=,r=b[],mid;
while(l+<r)mid=l+r>>,ask1(mid)?l=mid:r=mid-;
cout<<(ask1(r)?r:l);}
上一篇:【BZOJ4698】[SDOI2008]Sandy的卡片


下一篇:【BZOJ4698】Sdoi2008 Sandy的卡片 后缀数组+RMQ