AGC050C Block Game

考虑第一次操作,必然会放在当前 Snuke 的任意一边。

然后考虑第二次操作,必然放在当前 Snuke 的另一边。

然后现在 Snuke 就被圈起来了,仔细考虑一下会发现,它的决策必然是往尽量中间的位置靠。因为在下一次放方块的操作中,你肯定会让 Snuke 的活动范围尽量减少。也就是说,设你放方块的时候 Snuke 到左边长度是 $l$ ,到右边是 $r$ ,那么放完后他的范围肯定是变为 $\min(l,r)$ 。

我们考虑什么样的 B 操作,会导致能确定之后必然能堵死 Snuke 。对于最后两次放块,显然当且仅当这两次 B 连着的时候,Snuke 必定被堵住,如果在最后一次之前 Snuke 已经在一个范围为 $2$ 内左右横跳了,那么说明之前就已经被确定能堵死 Snuke 了。因为在倒数第二次放块操作时,如果可以把 Snuke 确定在一个 $2$ 的范围内,也就是距离上一次 B 操作仅隔了一个 S ,这样可以肯定之后无论进行多少次 S ,Snuke 都一定会被堵死。然后考虑倒数第三次放块,会发现和倒数第四次隔了 $3$ 个 S ,倒数第四次是 $7$ ,理性分析一下会发现是 $2^{k-1}-1$ 。具体过程画一下图即可。

于是就可以 $dp$ 了。设 $dp[i][k]$ 表示当前从右到左考虑到第 $i$ 个位置,到现在一共放了 $k$ 个方块即可。转移 $O(1)$ ,总复杂度 $O(n\log n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
int n , m;
char s[MAXN];

int dp[MAXN][25] , S[MAXN] , qm = 0 , bm = 0;

void solve() {
scanf("%s",s + 1);
n = strlen( s + 1 );
rep( i , 1 , n ) S[i] = S[i - 1] + ( s[i] == 'B' );
int flg = 0;
dp[n + 1][0] = 1;
per( i , n , 1 ) {
qm += s[i] == '?';
bm += s[i] == 'B';
if( s[i] != 'B' ) dp[i][0] = dp[i + 1][0];
if( s[i] != 'S' ) dp[i][1] = dp[i + 1][0];
rep( k , 1 , 22 ) {
if( k > 1 && i + ( 1 << k - 2 ) + 1 > n ) break;
if( s[i] != 'B' )
dp[i][k] = ( dp[i][k] + dp[i + 1][k] ) % P;
if( k > 1 && s[i] != 'S' && S[i + ( 1 << k - 2 )] - S[i] == 0 )
dp[i][k] = ( dp[i][k] + dp[i + ( 1 << k - 2 ) + 1][k - 1] ) % P;
}
}
int as = 1;
rep( i , 1 , qm ) as = as * 2 % P;
rep( k , 0 , 22 ) as = ( as + P - dp[1][k] ) % P;
cout << as << endl;
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}


文章作者: yijan
文章链接: https://yijan.co/2021/03/21/agc050c-block-game/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog