因【牛客版权】不放题面了
B.炸鸡块君与FIFA22 简化题意每次询问有一个初始分数，求经过字符串S[l,r]的操作之后，分数为多少
| S i S_i Si | Δ Delta Δ |
|---|---|
| W | +1 |
| L | -1(如果之前分数为3的倍数，则不-1) |
| D | +0 |
不论起始分数为多少，区间[l,r]中的W,D操作是不受影响的，只有L操作会因为起始分数不同而导致在不同的点满足L失效条件： ( s + Δ ) % 3 = 0 (s+Delta)%3=0 (s+Δ)%3=0
可以利用ST表，预处理出区间[l,r]在[0,1,2]作为起始分数（因为起始分数对后面的影响只关于它是不是3的倍数）的情况下的区间贡献 Δ Delta Δ
转移方程：
d
p
[
i
]
[
j
]
[
z
]
=
d
p
[
i
]
[
j
−
1
]
[
z
]
+
d
p
[
i
+
(
1
<
<
(
j
−
1
)
)
]
[
j
−
1
]
[
(
(
z
+
d
p
[
i
]
[
j
−
1
]
[
z
]
)
%
3
+
3
)
%
3
]
dp[i][j][z]=dp[i][j-1][z]+dp[i+(1<<(j-1))][j-1][((z+dp[i][j-1][z])%3+3)%3]
dp[i][j][z]=dp[i][j−1][z]+dp[i+(1<<(j−1))][j−1][((z+dp[i][j−1][z])%3+3)%3]
#includeK.冒险公社 简化题意using namespace std; #define ll long long const ll maxn = 2e5 + 10; char arr[maxn]; int dp[maxn][21][3], mi[21]; int main() { int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> arr[i]; for (int i = 1; i <= n; i++) { for (int z = 0; z < 3; z++) { if (arr[i] == 'W') dp[i][0][z]++; else if (arr[i] == 'L' && z != 0) dp[i][0][z]--; } } mi[0] = 1; for (int i = 1; i <= 20; i++) { mi[i] = mi[i - 1] * 2; } for (int j = 1; j <= 20; j++) { for (int i = 1; i + mi[j] - 1 <= n; i++) { for (int z = 0; z < 3; z++) { dp[i][j][z] = dp[i][j - 1][z] + dp[i + mi[j - 1]][j - 1][((z + dp[i][j - 1][z]) % 3 + 3) % 3]; } } } while (q--) { int l, r, s; cin >> l >> r >> s; int z = s % 3; int res = 0; for (int j = 20; j >= 0; j--) { if (l + mi[j] - 1 <= r) { res += dp[l][j][z]; z = ((z + dp[l][j][z]) % 3 + 3) % 3; l += mi[j]; } } cout << res + s << "n"; } }
给你一个字符串 A A A， A i A_i Ai 表示 a i − 2 , a i − 1 , a i a_{i-2},a_{i-1},a_i ai−2,ai−1,ai的颜色组合情况
| A i A_i Ai | 颜色组合 |
|---|---|
| R R R | R > G R>G R>G |
| G G G |
R
<
G
R |
| B B B | R = G R=G R=G |
求在给定的罗盘预测颜色字符串sta的情况下，原岛屿的颜色组合中，绿色最多的那种情况下的绿色数量为多少
思路因为对于一个预测 s t a i sta_i stai决定了 a i − 2 , a i − 1 , a i a_{i-2},a_{i-1},a_i ai−2,ai−1,ai的颜色组合情况， s t a i + 1 sta_{i + 1} stai+1决定了 a i − 1 , a i , a i + 1 a_{i-1},a_{i},a_{i+1} ai−1,ai,ai+1的颜色组合情况，从状态 s t a i sta_i stai转移到 s t a i + 1 sta_{i + 1} stai+1， s t a i + 1 sta_{i + 1} stai+1复用了 a i − 1 , a i a_{i-1},a_i ai−1,ai，而 a i − 2 a_{i-2} ai−2对于 s t a i + 1 sta_{i + 1} stai+1是没有影响的，所以我们只需要在满足 s t a i sta_i stai的所有{a}的情况下，枚举 a i + 1 a_{i+1} ai+1，判断{{a}+ a i + 1 a_{i+1} ai+1}是否合法。
转移方程：
d
p
[
i
]
[
c
2
]
[
c
3
]
[
c
4
]
=
m
a
x
(
t
h
i
s
,
d
p
[
i
−
1
]
[
c
1
]
[
c
2
]
[
c
3
]
)
dp[i][c2][c3][c4]=max(this,dp[i-1][c1][c2][c3])
dp[i][c2][c3][c4]=max(this,dp[i−1][c1][c2][c3])
#includeusing namespace std; #define ll long long const int maxn = 1e5 + 10; int dp[maxn][3][3][3]; void add(vector vt, int vis, int &res){ for(auto &te: vt) if(te == vis) res++; return; } void max(int &x, int y){ if(x < y) x = y; return; } int main(){ int n; cin >> n; string sta; cin >> sta; memset(dp, -1, sizeof dp); for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++){ for(int z = 0; z < 3; z++){ int R = 0, G = 0, B = 0; add({i, j, z}, 0, G); add({i, j, z}, 1, R); add({i, j, z}, 2, B); if(sta[2] == 'G' && G > R || sta[2] == 'R' && R > G || sta[2] == 'B' && R == G){ dp[2][i][j][z] = G; } } } } for(int index = 3; index < n; index++){ for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++){ for(int z = 0; z < 3; z++){ if(dp[index - 1][i][j][z] == -1) continue; for(int k = 0; k < 3; k++){ int R = 0, G = 0, B = 0; add({j, z, k},0, G); add({j, z, k}, 1, R); add({j, z, k}, 2, B); if(sta[index] == 'G' && G > R){ max(dp[index][j][z][k], dp[index - 1][i][j][z] + (k == 0)); } if(sta[index] == 'R' && R > G){ max(dp[index][j][z][k], dp[index - 1][i][j][z] + (k == 0)); } if(sta[index] == 'B' && R == G){ max(dp[index][j][z][k], dp[index - 1][i][j][z] + (k == 0)); } } } } } } int res = -1; for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) for(int z = 0; z < 3; z++) max(res, dp[n - 1][i][j][z]); cout << res; }
