Three Blocks Palindrome (hard version)
思路
考虑到每个数字的范围是(1 ~ 200)，于是我们可以通过枚举两侧的元素来寻找最优答案。
我们有一个贪心策略，两侧都以我们枚举的元素作为结尾点，假如我们当前枚举的数字是1，于是我们将构成(……1|…………|1……)这种分界线，这样可以保证两边对中间的影响最小，于是我们就可以从(1 ~ n)来枚举我们左侧的结尾点，然后通过寻找其右侧的结尾点来得到中间的最优值。
我们(vector<int> pos[i])中记录的是，值为(i)的元素从开始到结尾出现的原数组下标，(num[i])记录的是，值位(i)的元素在原数组中出现的次数，也就是(pos[i].size())是同一个东西。
为了方便查找值，在这里还记录用了一个树状数组来记录(tree[i][j])， 表示值为(i)的元素在原数组中的第(j)个位置出现过，也就是通过这个来更新我们的树状数组。
写完后发现好像可以不用树状数组，直接用一个前缀和数组就行，具体的更新过程也是同树状数组类似。
详细的解析看代码注释，有些细节不好描述。
树状数组版本——代码
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
const int N = 2e5 + 10;
int tree[210][N], a[N], num[210], n;
inline int lowbit(int x) {
return x & (-x);
}
void update(int value, int pos) {
while(pos <= n) {
tree[value][pos]++;
pos += lowbit(pos);
}
}
int query(int value, int pos) {
int sum = 0;
while(pos) {
sum += tree[value][pos];
pos -= lowbit(pos);
}
return sum;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = read();
while(_--) {
n = read();
vector<int> pos[210];
for(int i = 1; i <= n; i++) {
a[i] = read();//普通的输入更新。
num[a[i]]++;
pos[a[i]].pb(i);
update(a[i], i);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
int pre = query(a[i], i);//得到包括这个点及其前面有多少个a[i],
ans = max(ans, pre);//没这个就会wa，如果想删去这个的话，初始的ans应该设置为max_element(num);
//如果出现我们在后面找不到分解线的话，就会wa.
int last = num[a[i]] - pre;//右侧分界线的元素在pos[a[i]]数组中的位置
if(last < pre) continue;//如果两侧没法对称则不用继续下面步骤了。
int l = pos[a[i]][pre - 1], r = pos[a[i]][last];
for(int j = 1; j <= 200; j++)//找到区间(l, r)中的元素的最多出现次数。
ans = max(ans, pre * 2 + query(j, r - 1) - query(j, l));//简单的答案更新。
}
printf("%d
", ans);
for(int i = 1; i <= 200; i++) {
num[i] = 0;
for(int j = 1; j <= n; j++)
tree[i][j] = 0;
}
}
return 0;
}
前缀和——代码
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
const int N = 2e5 + 10;
int tree[210][N], a[N], n;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _ = read();
while(_--) {
n = read();
vector<int> pos[210];
for(int i = 1; i <= n; i++) {
a[i] = read();
pos[a[i]].pb(i);
for(int j = 1; j <= 200; j++)
tree[j][i] = tree[j][i - 1] + (a[i] == j);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
int pre = tree[a[i]][i];
ans = max(ans, pre);
int last = pos[a[i]].size() - pre;
if(last < pre) continue;
int l = pos[a[i]][pre - 1], r = pos[a[i]][last];
for(int j = 1; j <= 200; j++)
ans = max(ans, pre * 2 + tree[j][r - 1] - tree[j][l]);
}
printf("%d
", ans);
}
return 0;
}
对比
第一个的时间复杂度是(200 * n * log(n))的，第二个是(200 * n)的。
