首页 > 代码库 > Poi 2014 解题报告（ 1 - 4 ,6 ）

Poi 2014 解题报告（ 1 - 4 ,6 ）

2024-07-04 05:44:09   225人阅读

撸了一下Poi 2014 ，看了一下网上题解不多，所以决定写一下。有的题应该是数据不强水过去了，等北京回来在写一下复杂度比较靠谱的代码 o(╯□╰)o

第一题：

　　题意是给定一个长度不大于1000000，只包括p和j的串，求一个最长的子串，要求子串任何一个前缀和后缀都满足p的数量不少于j的数量。

　　首先把p当做1，把j当做0，算出前缀和 sum[] ，原来的问题就转化为求一个最长区间 [l,r] ，使得任意的i∈[l,r]，都有 sum[i] - sum[l-1] >= 0 并且 sum[r] - sum[i-1] >= 0 。然后就是陈题了。我的做法是用单调栈预处理出对于每个l-1，在满足第一个不等式的情况下向右最长延伸多长r[l-1]，然后用线段树求出l-1到r[l]之间最大的sum的下标k，如果sum[k] >= sum[l-1] 那么[l,k] 就是一个合法的区间。这样复杂度是O(n+nlogn) = O(nlogn)，跑了1.4s，代码1500B左右。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <stack>
 5 using namespace std ;
 6 const int N = 1000000 + 10 ;
 7 char s[N] ;
 8 int p[N] ,a[N<<2] ,r[N] ,Q ,st[N] ,top ,M ;
 9 void calM( int n ){
10     for( n -- ,M = 1 ;M <<= 1 ,n >>= 1 ; ) ;
11 }
12 int query( int s ,int t ){
13     if(s==t) return a[s+M];
14     int ans = p[a[s+=M]] > p[a[t+=M]] ? a[s] : a[t] ;
15     for( ;s ^ t ^ 1 ;s >>= 1 ,t >>= 1 ){
16         if(~s&1) ans = p[a[s^1]] > p[ans] ? a[s^1] : ans ;
17         if( t&1) ans = p[a[t^1]] > p[ans] ? a[t^1] : ans ;
18     }
19     return ans ;
20 }
21 void update( int x ,int t ){
22     for( a[x+=M] = t ;x >>= 1 ; )
23         a[x] = p[a[x+x]] > p[a[x+x+1]] ? a[x+x] : a[x+x+1] ;
24 }
25 int solve( int n ){ 
26     top = 0 ;
27     int ans = 0 ;
28     for( int i = 0 ;i <= n ;i ++ ){
29         if( i ) update( i - 1 ,i ) ;
30         while( top && p[st[top-1]] > p[i] ){
31             r[st[--top]] = i ;
32         }
33         st[top++] = i ;
34     }
35     for( int i = n ;i < M ;i ++ ) update( i ,n ) ; 
36     while( top ){
37         r[st[--top]] = n+1 ;
38     }
39     for( int i = 0 ;i <= n ;i ++ ){
40         if( s[i] == ‘j‘ ) continue ; 
41         if( ans > n - i ) break ; 
42         Q = query( max( i ,1 ) - 1 ,r[i] - 1 ) ;
43         if( p[Q] > p[i] ) ans = max( ans ,Q - i ) ;
44     }
45     printf( "%d\n" ,ans ) ;
46 }
47 int main(){
48     int n ;
49     scanf( "%d %s" ,&n ,s ) ;
50     calM( n+1 ) ;
51     for( int i = 1 ;i <= n ;i ++ )
52         p[i] = p[i-1] + ( s[i-1] == ‘p‘ ? 1 : -1 ) ;
53     solve(n) ;
54 }
第一题代码

-------------------------------------------------------------------------------------坑爹的BZOJ挂掉了睡觉去--------------------------------------------------------------------------------------


联系
我们