HDU 5371 （2015多校联合训练赛第七场1003）Hotaru's problem(manacher+二分/枚举)-白红宇

HDU 5371 （2015多校联合训练赛第七场1003）Hotaru's problem(manacher+二分/枚举)

阅读量：7282 次

发布时间：2019-06-30

本文共 1792 字，大约阅读时间需要 5 分钟。

题意：

定义一个序列为N序列：这个序列按分作三部分，第一部分与第三部分同样，第一部分与第二部分对称。

如今给你一个长为n（n<10^5）的序列，求出该序列中N序列的最大长度。

思路：

来自官方题解：~~修正了一些题解错别字（误~~

先用求回文串的Manacher算法。求出以第i个点为中心的回文串长度。记录到数组p中

要满足题目所要求的内容。须要使得两个相邻的回文串，共享中间的一部分，也就是说。左边的回文串长度的一半，要大于等于共享部分的长度，右边回文串也是一样。由于我们已经记录下来以第i个点为中心的回文串长度，那么问题能够转化成，相距x的两个数a[i],a[i+x]，满足p[i]/2>=x 而且 p[i+x]/2>=x。要求x尽量大

这能够用一个set维护。一開始集合为空，依次取出p数组中最大的元素。将其下标放入set中，每取出一个元素，在该集合中二分查找比i+p[i]/2小，但最大的元素。更新ans。

然后查找集合中比i-p[i]/2大，但最小的元素，更新ans。

答案就是3*ans

~~嗯~事实上不用二分暴力扫下也能水过去~~

/** @author FreeWifi_novicer* language : C++/C*/#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;#define clr( x , y ) memset(x,y,sizeof(x))#define cls( x ) memset(x,0,sizeof(x))#define mp make_pair#define pb push_backtypedef long long lint;typedef long long ll;typedef long long LL;const int maxn = 100000 + 5;int p[2*maxn];int s[maxn];int s1[2*maxn];int n;void init(){ cls(s1); s1[0] = -1; s1[1] = -2; int k = 2; for(int i = 0 ; i < n ; i++){ s1[k++] = s[i]; s1[k++] = -2; }}void manacher(){ int mx = 0 , id = 0; p[0] = 0; for(int i = 0 ; i < 2*n+1 ; i++){ if(mx > i) p[i] = min(p[2*id-i] , mx-i); else p[i] = 1; while(s1[i-p[i]] == s1[i+p[i]]) p[i]++; if(mx < p[i]+i){ mx = p[i] + i; id = i; } }}int solve(){ int ans = 0; for(int i = 1; i < n*2 + 1 ; i += 2) if((p[i] - 1) / 2 > ans){ for(int j = i + p[i] - 1 ; ; j -= 2){ if(p[j] >= j-i){ ans = (j-i) / 2; break; } if((j-i)/2 <= ans) break; } } return 3*ans; }int main(){ //freopen("input.txt","r",stdin); int t; cin >> t ; int kase = 1; while(t--){ cls(s);cls(p);cls(s1); cin >> n; for(int i = 0 ; i < n ; i++){ scanf("%d",s+i); } init(); manacher(); printf("Case #%d: %d\n",kase++,solve()); } return 0;}