HDU 5371 – Hotaru’s problem [Manacher+枚举]

点击打开HDU题目链接

问题:给定一个数字序列,求是否存在“N序列”,“N序列”的定义是序列可以平分为三步分,且第一部分==第三部分,第一部分与第二部分为会问串。求一个最长的“N序列”。

分析:以前LeetCode做过一个类似的求回文字串了题,现在重新整理下模板再做一下这一道题。然后枚举第二部分的开始和长度找出最大值即可。

C++代码如下:

#include <bits/stdc++.h>
using namespace std;

vector<int> Manacher(const vector<int> & str) {
    vector<int> t = {-1};
    for(auto i : str)
        t.push_back(i), t.push_back(-1);
    vector<int> res(t.size()+1, 0);
    int mx = 0, id = 0;
    for(int i = 0; i < t.size(); ++i) {
        res[i] = mx > i ? min(res[2*id-i], mx-i) : 1;
        while(t[i+res[i]] == t[i-res[i]]) ++res[i];
        if(i + res[i] > mx) {
            mx = i + res[i];
            id = i;
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    int T, kase = 0; cin >> T;
    while(T--) {
        int n; cin >> n; vector<int> v(n);
        for(int i = 0; i < n; ++i)
            cin >> v[i];
        vector<int> m = Manacher(v);
        int ans = 1;
        for(int i = 2; i < m.size()-1; i += 2)
            for(int j = ans; j <= m[i]; j += 2)
                if(m[i+j-1] >= j)
                    ans = max(ans, j);
        printf("Case #%d: %d\n", ++kase, ans/2*3);
    }
    return 0;
}

欢迎留言