注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

2806: [Ctsc2012]Cheat(后缀自动机+单调队列优化动态规划+二分查找)  

2014-04-06 21:20:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2806


第一道后缀自动机额。。。SAM预处理,二分L,然后DP判定,用单调队列优化。


代码(PS:好像网上很多代码都是有问题的,就是答案为1时会输出2。。。):

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •    
  • using namespace std ;
  •    
  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
  •    
  • #define C( t , x ) sam[ t ].child[ x ]
  • #define P( t ) sam[ t ].parent
  • #define L( t ) sam[ t ].len 
  • #define N( t ) sam[ t ]
  •    
  • #define inf 0x7fffffff
  • #define maxn 1200010
  • #define maxv ( maxn << 1 )
  •    
  • #define check( ch ) ( ch == '0' || ch == '1' )
  •   
  • #define G( x ) ( f[ x ] - x )
  •    
  • struct node {
  •     int child[ 3 ] , parent , len ; 
  •     node(  ) {
  •         parent = len = 0 ; 
  •         memset( child , 0 , sizeof( child ) ) ;
  •     }
  • } sam[ maxv ] ;
  •    
  • int root , last , V ;
  •    
  • void Init_sam(  ) {
  •     root = last = maxv - 1 , V = 0 ;
  • }
  •    
  • void add_sam( int ch , int l ) {
  •     int p = last , np = ++ V ;
  •     L( V ) = l ;
  •     for ( ; p && ! C( p , ch ) ; p = P( p ) ) C( p , ch ) = np ;
  •     if ( ! p ) P( np ) = root ; else {
  •         if ( L( C( p , ch ) ) == L( p ) + 1 ) P( np ) = C( p , ch ) ; else {
  •             int q = C( p , ch ) , r = ++ V ;
  •             N( r ) = N( q ) ;
  •             L( r ) = L( p ) + 1 ; 
  •             P( q ) = P( np ) = r ; 
  •             for ( ; p && C( p , ch ) == q ; p = P( p ) ) C( p , ch ) = r ; 
  •         }
  •     }
  •     last = np ; 
  • }
  •    
  • int n , m , s[ maxn ] , Len , cnt = 0 ; 
  •    
  • void getstr(  ) {
  •     Len = 0 ; 
  •     int ch ; 
  •     for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;
  •     s[ ++ Len ] = ch - '0' ;
  •     for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {
  •         s[ ++ Len ] = ch - '0' ;
  •     }
  • }
  •    
  • int f[ maxn ] , que[ maxn ] , head , tail , d[ maxn ] ;
  •   
  • bool Dp( int L ) {
  •     head = 1 , tail = 0 ;
  •     f[ 0 ] = 0 ;
  •     int temp = 0 ;
  •     rep( i , Len ) {
  •         f[ i ] = f[ i - 1 ] ;
  •         if ( i - L >= 0 ) {
  •             int x = i - L ;
  •             for ( ; head <= tail && G( que[ tail ] ) <= G( x ) ; -- tail ) ;
  •             que[ ++ tail ] = x ;
  •         }
  •         for ( ; head <= tail && que[ head ] < i - d[ i ] ; ++ head ) ;
  •         if ( head <= tail ) {
  •             f[ i ] = max( f[ i ] , G( que[ head ] ) + i ) ;
  •         }
  •         temp = max( temp , f[ i ] ) ;
  •     }
  •     return 10 * temp >= 9 * Len ;
  • }
  •   
  • int Solve(  ) {
  •     for ( int t = root , i = 0 , temp = 0 ; i ++ < Len ; ) {
  •         if ( C( t , s[ i ] ) ) ++ temp , t = C( t , s[ i ] ) ; else {
  •             for ( ; t && ! C( t , s[ i ] ) ; t = P( t ) ) ;
  •             if ( ! t ) t = root , temp = 0 ; else {
  •                 temp = L( t ) + 1 ;
  •                 t = C( t , s[ i ] ) ;
  •             }
  •         }
  •         d[ i ] = temp ;
  •     }
  •     int l = 0 , r = Len + 1 ;
  •     while ( r - l > 1 ) {
  •         int mid = ( l + r ) >> 1 ; 
  •         if ( Dp( mid ) ) l = mid ; else r = mid ;
  •     }
  •     return l ; 
  • }
  •    
  • int main(  ) {
  •     Init_sam(  ) ;
  •     scanf( "%d%d" , &n , &m ) ;
  •     rep( i , m ) {
  •         getstr(  ) ;
  •         rep( j , Len ) add_sam( s[ j ] , ++ cnt ) ;
  •         add_sam( 2 , ++ cnt ) ;
  •     }
  •     while ( n -- ) {
  •         getstr(  ) ; 
  •         printf( "%d\n" , Solve(  ) ) ;
  •     }
  •     return 0 ;
  • }



  评论这张
 
阅读(4)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017