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);}