題目鏈接：點(diǎn)擊查看

題目大意：給出n個數(shù)組成的數(shù)列，現(xiàn)在規(guī)定一種結(jié)構(gòu)滿足以下條件：

該結(jié)構(gòu)由三個部分組成

第一個部分與第三個部分相等

第一個部分與第二個部分對稱

現(xiàn)在問數(shù)列中最長的可以組成該結(jié)構(gòu)的字串的長度

題目分析：對于題目中的條件，我們換句話來解釋，還是三個部分，顯然第一個部分和第二個部分可以組成回文串，第二個部分可以和第三個部分組成回文串，而且組成的回文串還都是偶回文串，既然涉及到了字串和回文串，我們可以先用馬拉車跑一下以每個位置為終點(diǎn)的回文串長度，此后就可以暴力維護(hù)答案了，既然是要求兩個回文串，且必須滿足其中間有交集，則只需滿足：

設(shè)x為回文串1和回文串2中點(diǎn)位置的距離

回文串1的右半部分大于等于x

回文串2的左半部分大于等于x

如果滿足上述三個條件，那么必然可以構(gòu)造出一種題目要求的數(shù)列，且長度為x*3，如此暴力維護(hù)一下最大值就是答案了

不得不說，這個題我是不太敢暴力的，但加上了最優(yōu)性剪枝，以及適當(dāng)?shù)腷reak之后，其實(shí)暴力起來的時間復(fù)雜度遠(yuǎn)遠(yuǎn)小于n*n，反而更接近O(n)

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int a[N],p[N],n;void Manacher() {p[0]=1;int id=0,mmax=0;for(int i=1;i<n;i++){if(i<mmax)p[i]=min(mmax-i,p[2*id-i]);elsep[i]=1;while(a[i-p[i]]==a[i+p[i]])p[i]++;if(i+p[i]>mmax){mmax=i+p[i];id=i;}p[i]--;//這里減一代表的是不算當(dāng)前位置可以向左或向右擴(kuò)展多少個單位 } } int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){int nn;scanf("%d",&nn);n=0;a[n++]=-1;while(nn--){a[n++]=0;scanf("%d",&a[n++]);}a[n++]=0;a[n++]=-1;Manacher();int ans=0;for(int i=1;i<n;i+=2)//枚舉第一個回文串的中點(diǎn)，因為要跳過'#'，所以每次加二for(int j=i+p[i];j-i>ans;j-=2)//枚舉第二個回文串的中點(diǎn)，同理每次減二 if(j-i<=p[j]){ans=max(ans,j-i);break;}printf("Case #%d: %d\n",++kase,ans/2*3);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5371 Hotaru's problem(马拉车+暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。