专栏文章

题解：P14256 平局（draw）

SSktn0089
P14256题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minkm9e7
此快照首次捕获于
2025/12/02 03:57
3 个月前
此快照最后确认于
2025/12/02 03:57
3 个月前
查看原文
容易想到大概率需要从左往右扫描，然后用一些 dp of dp 或者贪心 of dp 之类的做。
感受一下，这里大概率应该是贪心 of dp。下面记 A,B,C\mathtt {A,B,C} 分别为剪刀、石头、布，用 ss 表示整个字母串。
先把所有相邻相同的字母消除掉，然后发现我们其实是不断这样操作：选择两个相同的字母 si,sjs_i, s_j，比如都为 B\mathtt B，并且 si+1,si+2,…,sj−1s_{i + 1}, s_{i + 2}, \dots, s_{j - 1} 中至少存在一个 A\mathtt A，那么可以将 si,si+1,…,sjs_i, s_{i + 1}, \dots, s_j 合并成一个 B\mathtt B。我们需要求解的是操作次数的最大值。
首先我们观察：若存在形如 BAB\mathtt {BAB} 的子串，那么直接操作这两个 B\mathtt B 一定不劣。如果不操作，说明中间的 A\mathtt A 有用，这与放弃中间的 A\mathtt A 的操作转而对旁边两个 B\mathtt B 操作的答案相等。
剩下的只需要考虑 ABA\mathtt {ABA} 以及其他情况。
如果不存在形如 ABA\mathtt {ABA} 这样的形式，那么整个串可以用 ABC\mathtt {ABC} 或 ACB\mathtt {ACB} 的循环表示。设 fi,j,c,0/1f_{i, j, c, 0/1} 表示依次加入了字母 s1,s2,…,sis_1, s_2, \dots, s_i 后，当前串由形如 ABC/ACB\mathtt {ABC/ACB} 循环构成，长度为 jj，且最后一个字母为 cc 的方案数。
  • 如果当前串为形如 …ACBACBAC\mathtt {\dots ACBACBAC}，加入一个 B\mathtt B 后，直接令 jj 加一；加入一个 C\mathtt C 后，jj 不变，直接令答案加上对应贡献；加入一个 A\mathtt A 后，显然可以将 ACA\mathtt {ACA} 合并成一个 A\mathtt A 并将答案加上对应贡献。
  • 如果当前串为形如 …ABCABCAB\mathtt {\dots ABCABCAB}，加入一个 C\mathtt C 后，直接令 jj 加一；加入一个 B\mathtt B 后，jj 不变，直接令答案加上对应贡献；加入一个 A\mathtt A 后，此时两个 A\mathtt A 中间没有 C\mathtt C 所以无法操作。
这就产生了新的状态：形如 …ABCABCABCABA\mathtt {\dots ABCABCABCABA} 这样的串，不妨用 fi,j,c,2f_{i, j, c, 2} 表示这样的状态，其中需要满足 j≥4j\ge 4（形如 ABA\mathtt {ABA} 这样的串会在下面归为 fi,j,c,3f_{i, j, c, 3}）。
那么我们考虑 fi,j,c,2f_{i, j, c, 2} 在加入一个新字母 si+1s_{i + 1} 后该如何转移，不妨令当前串为 …ABCABCABA\mathtt {\dots ABCABCABA}。
  • 加入一个 A\mathtt A 是简单的。加入一个 B\mathtt B 后，我们显然可以直接将 BAB\mathtt {BAB} 合并成一个 B\mathtt B。
    若原来 j=4j = 4，加入字母后仅看当前串的后缀 CABAC\mathtt {CABAC}，我们发现：令第一个 A\mathtt A 禁止和其他 A\mathtt A 进行合并，这样一定不劣。如果与其左边的 A\mathtt A 进行合并，那么不妨直接令第二 A\mathtt A 替代之进行合并；如果与第二个 A\mathtt A 右边的 A\mathtt A 进行合并，那么在该合并中，中间一定存在一个 C\mathtt C，那么我们不妨改为将那个 C\mathtt C 与 CABAC\mathtt {CABAC} 中第一个 C\mathtt C 进行合并。
    所以，我们可以忽略第一个 A\mathtt A，近似地表示成 CBAC\mathtt {CBAC}，应转移到 fi+1,4,C,1f_{i + 1, 4, \mathtt C, 1}。
    若 j=5j = 5，串变为 BCABAC\mathtt {BCABAC}，同样地忽略第一个 A\mathtt A，那么可以合并 BCAB\mathtt {BCAB}（忽略第一个 A\mathtt A 后可以看成 BCB\mathtt {BCB}，又由于两个 B\mathtt B 中间存在一个 A\mathtt A 所以可以合并），串变为 BAC\mathtt {BAC}。
    若 j=6j = 6，串变为 ABCABAC\mathtt {ABCABAC}，合并 BCAB\mathtt {BCAB} 后变为 ABAC\mathtt {ABAC}。
    若 j=7j = 7，串变为 CABCABAC\mathtt {CABCABAC}，合并 BCAB\mathtt {BCAB} 后变为 CABAC\mathtt {CABAC}，删掉第一个 A\mathtt A 后变为 CBAC\mathtt {CBAC}。可以发现，j=7j = 7 和 j=4j = 4 变成的最终串是相同的。又发现 jj 拓展到 j+1j + 1 时，只是在最前面加了一个字母，影响不大，所以模 33 相同的 jj 转移应该是相同的。
  • 对于 j=4,7,10,…j = 4, 7, 10, \dots，合并次数分别为 0,1,2,…0, 1, 2, \dots，最终串为 CBAC\mathtt {CBAC}，转移到 fi+1,4,C,1f_{i + 1, 4, \mathtt C, 1}。
  • 对于 j=5,8,11,…j = 5, 8, 11, \dots，合并次数分别为 1,2,3,…1, 2, 3, \dots，最终串为 BAC\mathtt {BAC}，转移到 fi+1,3,C,1f_{i + 1, 3, \mathtt C, 1}。
  • 对于 j=6,9,12,…j = 6, 9, 12, \dots，合并次数分别为 1,2,3,…1, 2, 3, \dots，最终串为 ABAC\mathtt {ABAC}，这又是一个新的状态，不妨使用 fi,j,c,3f_{i, j, c, 3} 表示这样形如 ABACBACBACB…\mathtt {ABACBACBACB \dots} 这样的状态，则转移到 fi+1,4,C,3f_{i + 1, 4, \mathtt C, 3}。
最后我们考虑 fi,j,c,3f_{i, j, c, 3} 加入一个字母 si+1s_{i + 1} 后如何转移，不妨令当前串为 ABACBACB…ACBACBA\mathtt {ABACBACB \dots ACBACBA}。
  • 若 j=3j = 3，即当前串为 ABA\mathtt {ABA}，加入 A\mathtt A 是容易的，加入 C\mathtt {C} 则转移到 fi+1,4,C,3f_{i + 1, 4, \mathtt C, 3}；加入 B\mathtt B 后，显然可以合并 BAB\mathtt {BAB}，串变为 AB\mathtt {AB}，转移到 fi+1,2,B,0f_{i + 1, 2, \mathtt B, 0}。
  • 若 j>3j > 3，加入 A,B,C\mathtt {A,B,C} 都是容易转移的。
加入完所有字母后，对最终得到的串不断进行操作直到不能操作为止。对于 fn,j,c,0/1f_{n, j, c, 0/1} 贡献为 ⌊j−13⌋\lfloor \frac {j - 1} 3 \rfloor，对于 fn,j,c,2/3f_{n, j, c, 2 / 3} 贡献为 ⌊j−23⌋\lfloor \frac {j - 2} 3 \rfloor。总时间复杂度为 O(n2)\mathcal O(n ^ 2)。
CPP
#include <bits/stdc++.h>
#define ll int
#define LL long long
#define uLL unsigned LL
#define fi first
#define se second
#define mkp make_pair
#define pir pair<ll, ll>
#define pb push_back
#define i128 __int128
using namespace std;
char buf[1 << 22], *p1, *p2;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF :
// *p1++)
template <class T>
const inline void rd(T &x) {
    char ch;
    bool neg = 0;
    while (!isdigit(ch = getchar()))
        if (ch == '-')
            neg = 1;
    x = ch - '0';
    while (isdigit(ch = getchar())) x = (x << 1) + (x << 3) + ch - '0';
    if (neg)
        x = -x;
}
const ll maxn = 3010, mod = 1e9 + 7, inf = 1e9;
ll power(ll a, ll b = mod - 2, ll p = mod) {
    ll s = 1;
    while (b) {
        if (b & 1)
            s = 1ll * s * a % p;
        a = 1ll * a * a % p, b >>= 1;
    }
    return s;
}
template <class T, class _T>
const inline ll pls(const T x, const _T y) { return x + y >= mod ? x + y - mod : x + y; }
template <class T, class _T>
const inline ll mus(const T x, const _T y) { return x < y ? x + mod - y : x - y; }
template <class T, class _T>
const inline void add(T &x, const _T y) { x = x + y >= mod ? x + y - mod : x + y; }
template <class T, class _T>
const inline void sub(T &x, const _T y) { x = x < y ? x + mod - y : x - y; }
template <class T, class _T>
const inline void chkmax(T &x, const _T y) { x = x < y ? y : x; }
template <class T, class _T>
const inline void chkmin(T &x, const _T y) { x = x < y ? x : y; }

ll n, a[maxn], f[maxn][maxn][3][4], suf[maxn], ans;
char str[maxn];

int main() {
	rd(n), scanf("%s", str + 1);
	for(ll i = 1; i <= n; i++) a[i] = str[i] - '0';
	for(ll c = 0; c < 3; c++)
		if(a[1] & (1 << c)) f[1][1][c][0] = 1;
	suf[n + 1] = 1;
	for(ll i = n; i; i--)
		suf[i] = 1ll * suf[i + 1] * __builtin_popcount(a[i]) %mod;
	for(ll i = 2; i <= n; i++) {
		for(ll j = 1; j < i; j++)
			for(ll p = 0; p < 3; p++)
				for(ll u = 0; u < 4; u++)
					for(ll q = 0; q < 3; q++) {
						if(!(a[i] & (1 << q)) || !f[i - 1][j][p][u]) continue;
						if(p == q) {
							add(ans, 1ll * f[i - 1][j][q][u] * suf[i + 1] %mod);
							add(f[i][j][q][u], f[i - 1][j][p][u]);
						} else {
							ll z = (q == (p + 1) % 3);
							if(u == 2) {
								if(z) {
									add(ans, 1ll * f[i - 1][j][p][2] * suf[i + 1] %mod);
									add(f[i][j - 1][q][0], f[i - 1][j][p][2]);
								} else {
									add(ans, (j - 2) / 3 * 1ll * f[i - 1][j][p][2] %mod * suf[i + 1] %mod);
									if(j % 3 == 0) add(f[i][4][q][3], f[i - 1][j][p][2]);
									else if(j % 3 == 1) add(f[i][4][q][1], f[i - 1][j][p][2]);
									else add(f[i][3][q][1], f[i - 1][j][p][2]);
								}
							}
							if(u == 3) {
								if(z) {
									add(ans, 1ll * f[i - 1][j][p][3] * suf[i + 1] %mod);
									if(j == 3) add(f[i][2][q][0], f[i - 1][j][p][3]);
									else add(f[i][j - 1][q][3], f[i - 1][j][p][3]);
								} else add(f[i][j + 1][q][3], f[i - 1][j][p][3]);
							}
							if(u == 0) {
								if(z) add(f[i][j + 1][q][0], f[i - 1][j][p][0]);
								else {
									if(j == 1) add(f[i][j + 1][q][1], f[i - 1][j][p][0]);
									else if(j == 2) add(f[i][3][q][3], f[i - 1][j][p][0]);
									else add(f[i][j + 1][q][2], f[i - 1][j][p][0]);
								}
							}
							if(u == 1) {
								if(z) {
									add(ans, 1ll * f[i - 1][j][p][1] * suf[i + 1] %mod);
									add(f[i][j - 1][q][j > 2], f[i - 1][j][p][1]);
								} else add(f[i][j + 1][q][1], f[i - 1][j][p][1]);
							}
						}
					}
	}
	for(ll i = 1; i <= n; i++)
		for(ll c = 0; c < 3; c++) {
			add(ans, (i - 1) / 3 * 1ll * (f[n][i][c][0] + f[n][i][c][1]) %mod);
			add(ans, (i - 2) / 3 * 1ll * (f[n][i][c][2] + f[n][i][c][3]) %mod);
		}
	printf("%d\n", ans);
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...