P9192 [USACO23OPEN] Pareidolia P 题解
首先自然考虑不带修的情况。
考虑问题的本质就是求序列中 尽量短 的 bessie
序列个数。对于 尽量短 的理解是对于 bessiebessie
序列,不考虑其由 \(1,8\sim 12\) 构成的序列,只考虑 \(1\sim 6,7\sim 12\) 组成的序列。
于是考虑 dp:设 \(dp_{i,j}\) 表示前 \(i\) 个字符,下一个匹配的是 bessie
第 \(0\sim 5\) 位置的数量。注意 dp 时维护 尽量短 的序列要求是维护新的字符转移后删去原有字符的贡献,这样的 dp 记录的是每一个 bessie
结尾处的贡献,于是对答案前缀和。具体见代码:
#include <bits/stdc++.h>
#define N 200005
#define M 6
#define int long long
using namespace std;
int T;
int n;
string s;
int dp[N][M];
void keep() {
int res = 0;
int ans = 0;
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < M; j++)
dp[i][j] = dp[i - 1][j];
if (s[i] == 'b') {
dp[i][1] += dp[i][0];
dp[i][0] = 0;
}
else if(s[i] == 'e') {
dp[i][2] += dp[i][1];
dp[i][1] = 0;
ans += dp[i][5];
dp[i][0] += dp[i][5];
dp[i][5] = 0;
}
else if(s[i] == 's') {
dp[i][4] += dp[i][3];
dp[i][3] = 0;
dp[i][3] += dp[i][2];
dp[i][2] = 0;
}
else if (s[i] == 'i') {
dp[i][5] += dp[i][4];
dp[i][4] = 0;
}
if (s[i] == 'b') ++dp[i][1];
else ++dp[i][0];
res += ans;
}
cout << res << "\n";
}
signed main() {
cin >> s;
n = s.size();
s = " " + s;
cin >> T;
keep();
while (T--) {
int x;
char v[4];
scanf("%lld%s", &x, v);
s[x] = v[0];
keep();
}
return 0;
}
对于带修的情况,考虑 dp 的转移维度很少,是近似线性的,考虑矩阵优化,建出矩阵线段树维护动态 dp 即可。
代码:
#include <bits/stdc++.h>
#define N 200005
#define M 9
#define int long long
using namespace std;
string s;
int T;
int n;
struct Mat {
int a[M][M];
Mat() {
memset(a, 0, sizeof a);
}
};
Mat operator * (Mat a, Mat b) {
Mat res;
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < M; k++)
res.a[i][j] += a.a[i][k] * b.a[k][j];
return res;
}
Mat newnode(char c) {
Mat a;
for (int i = 0; i < M; i++)
a.a[i][i] = 1;
if (c == 'b') {
a.a[8][1] = 1;
a.a[0][1] = 1;
a.a[0][0] = 0;
}
else if(c == 'e') {
a.a[8][0] = 1;
a.a[1][2] = 1;
a.a[1][1] = 0;
a.a[5][6] = 1;
a.a[5][7] = 1;
a.a[5][0] = 1;
a.a[5][5] = 0;
}
else if(c == 's') {
a.a[8][0] = 1;
a.a[3][4] = 1;
a.a[3][3] = 0;
a.a[2][3] = 1;
a.a[2][2] = 0;
}
else if(c == 'i') {
a.a[8][0] = 1;
a.a[4][5] = 1;
a.a[4][4] = 0;
}
else a.a[8][0] = 1;
a.a[6][7] = 1;
return a;
}
#define lc (p << 1)
#define rc (lc | 1)
Mat e[N << 2];
void push_up(int p) {
e[p] = e[lc] * e[rc];
}
void build(int p, int l, int r) {
if (l == r)
return e[p] = newnode(s[l]), void();
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
push_up(p);
}
void update(int p, int l, int r, int x) {
if (l == r && l == x)
return e[p] = newnode(s[l]), void();
int mid = (l + r) >> 1;
if (x <= mid) update(lc, l, mid, x);
else update(rc, mid + 1, r, x);
push_up(p);
}
void kudo() {
Mat bas;
bas.a[0][8] = 1;
bas = bas * e[1];
cout << bas.a[0][7] << '\n';
}
signed main() {
cin >> s;
n = s.size();
s = " " + s;
build(1, 1, n);
kudo();
cin >> T;
while (T--) {
int x;
char v[4];
scanf("%lld%s", &x, v);
s[x] = v[0];
update(1, 1, n, x);
kudo();
}
return 0;
}
标签:USACO23OPEN,P9192,return,Mat,int,题解,序列,dp,define
From: https://www.cnblogs.com/Rock-N-Roll/p/18534095