P8908 [USACO22DEC] Palindromes P 题解
算是好题,虽然没什么人做(
简单地,我们考虑如何将一个字符串改变为回文串。显然如果我们判定所有 \(\texttt{G}\) 组成的是回文串,那么整个串一定是回文的。于是我们只考虑改变 \(\texttt{G}\) 的位置。
那么由这类题的套路不难知道最优的变换一定不改变 \(\texttt{G}\) 的先后顺序。于是我们只考虑改变后一半的 \(\texttt{G}\),让这些个 \(\texttt{G}\) 和前一半的 \(\texttt{G}\) 相对应。
具体地,对于一个长度为 \(n\) 的串 \([l,r]\) 有 \(m\) 个 \(\texttt{G}\),记这 \(m\) 个 \(\texttt{G}\) 的位置分别为 \(a_1,a_2,\cdots,a_m\),那么对于 \(a_i(i> \dfrac{m}{2})\),它变换后的对应位置就是 \(r-a_{n-i+1}\)。那么它走过的路径就是 \(|r-(a_{n-i+1}-l)-a_i|=|l+r-a_{i}-a_{n-i+1}|\)。那么我们可以 \(O(m)\) 地求出一个串的最优决策。这样复杂度是 \(O(n^3)\) 的。
考虑优化这个过程。我们发现 \(i\) 和 \(n-i+1\) 相搭配的形式意味着可以向两边递推扩展,具体地,我们枚举 \(i\) 作为序列的中点(中点唯一或不唯一均可),从 \(i\) 分别向 \(1\) 和 \(n\) 扩展,枚举当前范围内的每个区间 \((l,r)\),将 \(l+r\) 加入树状数组就可以方便地维护 \(<l+r\) 和 \(>l+r\) 的数了。
实现的时候注意中点唯一时中点位置固定且不计入 \(l+r\) 的贡献。时间复杂度 \(O(n^2\log n)\)。
题目的关键是发现 \(|l+r-a_i-a_{n-i+1}|\) 的式子和扩展的转移方式。
代码:
#include <bits/stdc++.h>
#define N 7505
using namespace std;
int n;
string s;
int a[N];
struct BIT {
int lowbit(int x) {
return x & (-x);
}
#define M 15005
int tree[M];
void add(int x, int v) {
while (x < M) {
tree[x] += v;
x += lowbit(x);
}
}
int ask(int x) {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
void clear() {
memset(tree, 0, sizeof tree);
}
} A, B;
int g[N], cnt;
int sum[N], sm[N];
long long ans;
int main() {
cin >> s;
n = s.size();
s = " " + s;
for (int i = 1; i <= n; i++) {
if (s[i] == 'G') {
a[i] = 1;
g[++cnt] = i;
}
else
++sm[i];
sm[i] += sm[i - 1];
sum[i] = sum[i - 1] + a[i];
}
g[cnt + 1] = n + 1;
for (int mid = 1; mid <= cnt; mid++) {
for (int j = 0; mid - j >= 1 && mid + j <= cnt; j++) {
int L = g[mid - j - 1] + 1, R = g[mid + j + 1] - 1;
int tmp = g[mid - j] + g[mid + j];
if (j) {
A.add(tmp, tmp);
B.add(tmp, 1);
}
for (int l = L; l <= g[mid - j]; l++)
for (int r = g[mid + j]; r <= R; r++) {
if ((r - l + 1) % 2 == 0)
continue;
int tmp = l + r;
int num = B.ask(tmp), as = A.ask(tmp);
ans += tmp * num - as
num = B.ask(M - 1) - B.ask(tmp), as = A.ask(M - 1) - A.ask(tmp);
ans += as - tmp * num;
ans += abs((tmp >> 1) - g[mid]);
}
}
A.clear();
B.clear();
}
for (int mid = 1; mid <= cnt; mid++) {
for (int j = 0; mid - j >= 1 && mid + 1 + j <= cnt; j++) {
int L = g[mid - j - 1] + 1, R = g[mid + j + 2] - 1;
int tmp = g[mid - j] + g[mid + j + 1];
A.add(tmp, tmp);
B.add(tmp, 1);
for (int l = L; l <= g[mid - j]; l++)
for (int r = g[mid + j + 1]; r <= R; r++) {
int tmp = l + r;
int num = B.ask(tmp), as = A.ask(tmp);
ans += tmp * num - as;
num = B.ask(M - 1) - B.ask(tmp), as = A.ask(M - 1) - A.ask(tmp);
ans += as - tmp * num;
}
}
A.clear();
B.clear();
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (((sum[j] - sum[i - 1]) & 1) && ((sm[j] - sm[i - 1]) & 1))
--ans;
cout << ans << "\n";
return 0;
}
标签:Palindromes,P8908,int,题解,texttt,tree,mid,ans
From: https://www.cnblogs.com/Rock-N-Roll/p/18434360