Three Blocks Palindrome (hard version)

发表于 更新于 分类于 ，

    定义三段式回文数组：回文数组中最多两种元素，不妨设这两种元素为a和b，形如$[\underbrace{a, a, \dots, a}{x}, \underbrace{b, b, \dots, b}{y}, \underbrace{a, a, \dots, a}_{x}]$为三段式回文串，其中x和y大于等于0。

    有一个长度为n的数组，数组中的值在1到200。求最长子序列使其为三段式回文数组。

Three Blocks Palindrome (hard version)

Created by LXC on Fri Jun 16 11:36:36 2023

https://codeforces.com/problemset/problem/1335/E2

ranting: 1800

tag: brute force, data structures, dp, two pointers

problem

定义三段式回文数组：回文数组中最多两种元素，不妨设这两种元素为a和b，形如$[\underbrace{a, a, \dots, a}{x}, \underbrace{b, b, \dots, b}{y}, \underbrace{a, a, \dots, a}_{x}]$为三段式回文串，其中x和y大于等于0。

有一个长度为n的数组，数组中的值在1到200。求最长子序列使其为三段式回文数组。

solution

枚举1到200内的数x，然后用相向双指针l和r。当l和r都指向x时，我们统计开区间(l,r)内出现最多的数mx。当前两个指针所经过的x的个数+mx就是一种三段式回文串的长度，维护其最大值即是答案。

也就是说只需要200次双指针，每次双指针时间复杂度$O(n)$。

关键在于统计区间的众数。如果已知区间[l,r]内的众数，我们只需哈希表记录每个数出现的频次，以及频次的频次。就可以实现$O(1)$求出相邻区间[l+1,r],[l,r-1],[l-1,r],[l,r+1]内的众数。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> cnt(201);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    int ans = 1;
    for (int i = 1; i <= 200; i++) {
        if (!cnt[i])
            continue;
        // cout << i << endl;
        int mx = *max_element(cnt.begin(), cnt.end());
        // cout << "mx " << mx << endl;
        vector<int> c = cnt, h(n + 1);
        for (int i = 1; i <= 200; i++)
            h[c[i]]++;

        int l = -1, r = n, stp = 1;
        while (l < r) {
            // cout << l << " " << r << endl;
            do {
                l++;
                int v = c[a[l]]--;
                h[v]--;
                if (v)
                    h[v - 1]++;
                if (mx == v && h[v] == 0) {
                    while (v >= 0 && h[v] == 0)
                        v--;
                    mx = v;
                }
            } while (l < r && a[l] != i);
            if (l == r)
                break;
            do {
                r--;
                int v = c[a[r]]--;
                h[v]--;
                if (v)
                    h[v - 1]++;
                if (mx == v && h[v] == 0) {
                    while (v >= 0 && h[v] == 0)
                        v--;
                    mx = v;
                }
            } while (l < r && a[r] != i);
            if (l < r) {
                ans = max(ans, stp * 2 + mx);
                // cout << "ans " << ans << endl;
                stp++;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}