Three Blocks Palindrome (hard version)

思路

考慮到每個數(shù)字的范圍是$1200$，于是我們可以通過枚舉兩側(cè)的元素來尋找最優(yōu)答案。

我們有一個貪心策略，兩側(cè)都以我們枚舉的元素作為結(jié)尾點(diǎn)，假如我們當(dāng)前枚舉的數(shù)字是1，于是我們將構(gòu)成$\dots \dots 1|\dots \dots \dots \dots |1\dots \dots$這種分界線，這樣可以保證兩邊對中間的影響最小，于是我們就可以從$1n$來枚舉我們左側(cè)的結(jié)尾點(diǎn)，然后通過尋找其右側(cè)的結(jié)尾點(diǎn)來得到中間的最優(yōu)值。

我們$vector<int>pos[i]$中記錄的是，值為$i$的元素從開始到結(jié)尾出現(xiàn)的原數(shù)組下標(biāo)，$num[i]$記錄的是，值位$i$的元素在原數(shù)組中出現(xiàn)的次數(shù)，也就是$pos[i].size()$是同一個東西。

為了方便查找值，在這里還記錄用了一個樹狀數(shù)組來記錄$tree[i][j]$， 表示值為$i$的元素在原數(shù)組中的第$j$個位置出現(xiàn)過，也就是通過這個來更新我們的樹狀數(shù)組。

寫完后發(fā)現(xiàn)好像可以不用樹狀數(shù)組，直接用一個前綴和數(shù)組就行，具體的更新過程也是同樹狀數(shù)組類似。

詳細(xì)的解析看代碼注釋，有些細(xì)節(jié)不好描述。

樹狀數(shù)組版本——代碼

#include <bits/stdc++.h> #define mp make_pair #define pb push_backusing 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);//得到包括這個點(diǎn)及其前面有多少個a[i],ans = max(ans, pre);//沒這個就會wa，如果想刪去這個的話，初始的ans應(yīng)該設(shè)置為max_element(num);//如果出現(xiàn)我們在后面找不到分解線的話，就會wa.int last = num[a[i]] - pre;//右側(cè)分界線的元素在pos[a[i]]數(shù)組中的位置if(last < pre) continue;//如果兩側(cè)沒法對稱則不用繼續(xù)下面步驟了。int l = pos[a[i]][pre - 1], r = pos[a[i]][last];for(int j = 1; j <= 200; j++)//找到區(qū)間(l, r)中的元素的最多出現(xiàn)次數(shù)。ans = max(ans, pre * 2 + query(j, r - 1) - query(j, l));//簡單的答案更新。}printf("%d\n", 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_backusing 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\n", ans);}return 0; }

對比

第一個的時間復(fù)雜度是$200?n?log(n)$的，第二個是$200?n$的。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的E：Three Blocks Palindrome(hard and easy)(树状数组 ？ 前缀和？)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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