BZOJ2958 序列染色
题意
给出一个长度为 \(n\),由 \(\tt B,W,X\) 三种字符组成的字符串 \(S\),你需要把每一个 \(\tt X\) 染成 \(\tt B\) 或 \(\tt W\) 中的一个。
Solution
字符串,染色,方案数,一眼 \(dp\)。
要求前半段是 B
,后半段是 W
。考虑容斥。
\(f_{i, 0/1}, g_{i, 0/1}, h_{i, 0/1}\) 代表选到第 \(i\) 位的方案,\(0\) 代表填 B
,\(1\) 代表填 W
,\(f\) 代表没有长度为 \(k\) 的带 B
字符串,\(g\) 代表有长度为 \(k\) 的带 B
字符串但没有长度为 \(k\) 的带 W
字符串,\(h\) 代表既有长度为 \(k\) 的带 B
字符串,又有长度为 \(k\) 的带 B
字符串。
显然,只有 X
和 B
可以填 B
,只有 X
和 W
可以填 W
。所以从 \(i - 1\) 转移时只需分类讨论填 B
和 W
,即:
从 \(i - k\) 转移时只需保证 $\left [ i - k, i \right ] $ 中可以全填 B
或 W
,即:
Code
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string.h>
#include <cstring>
using namespace std;
#define Maxn 1000005
#define Mod 1000000007
#define fo(i, l, r) for(int i = l; i <= r; ++i)
int n, k, a[Maxn], sum[Maxn][2], f[Maxn][2], g[Maxn][2], h[Maxn][2]; // f : no B, g : have B && no W, h : have B && have W
char s[Maxn];
void Input_data()
{
scanf("%d%d%s", &n, &k, (s + 1));
fo(i, 1, n) sum[i][0] = sum[i - 1][0], sum[i][1] = sum[i - 1][1], (s[i] == 'B') && (++sum[i][0], a[i] = 1, 0), (s[i] == 'W') && (++sum[i][1], a[i] = 2, 0);
// fo(i, 1, n) cerr << a[i] << " " << sum[i][0] << " " << sum[i][1] << " " << endl;
}
void Solve()
{
f[0][1] = 1;
fo(i, 1, n) {
if(a[i] != 2) f[i][0] = (f[i - 1][0] + f[i - 1][1]) % Mod, g[i][0] = (g[i - 1][0] + g[i - 1][1]) % Mod, h[i][0] = (h[i - 1][0] + h[i - 1][1]) % Mod;
if(a[i] != 1) f[i][1] = (f[i - 1][0] + f[i - 1][1]) % Mod, g[i][1] = (g[i - 1][0] + g[i - 1][1]) % Mod, h[i][1] = (h[i - 1][0] + h[i - 1][1]) % Mod;
// cerr << "f[" << i << "][0] : " << f[i][0] << " " << "f[" << i << "][1] : " << f[i][1] << endl;
if(i < k) continue;
if(sum[i][0] == sum[i - k][0]) g[i][1] = (g[i][1] - g[i - k][0] + Mod) % Mod, h[i][1] = (h[i][1] + g[i - k][0]) % Mod;
if(sum[i][1] == sum[i - k][1]) f[i][0] = (f[i][0] - f[i - k][1] + Mod) % Mod, g[i][0] = (g[i][0] + f[i - k][1]) % Mod;
}
}
void Print_ans()
{
printf("%d", (h[n][0] + h[n][1]) % Mod);
}
int main()
{
Input_data();
Solve();
Print_ans();
return 0;
}
标签:题解,tt,染色,字符串,长度,include,sum,BZOJ2958
From: https://www.cnblogs.com/naughty-naught/p/18532262