【思维】2021牛客暑期多校训练营5 C Cheating and Stealing
2021-09-07 21:06:00 # ACM

题链

题目解析

当局分为 $i$，局数是 $O(n/i)$ 的，如果可以 $O(1)$ 地处理每一局，那么复杂度是 $O(nlogn)$ 的；

具体思路为记录前缀数组：
  $qz[1][i]$ 表示 $W$ 的前缀和；
  $qz[0][i]$ 表示 $L$ 的前缀和；
记录位置数组：
  $pos[1][i]$ 表示第 $i$ 个 $W$ 所在位置；
  $pos[0][i]$ 表示第 $i$ 个 $L$ 所在位置；
那么就可以 $O(1)$ 地找到某个位置后面第 $k$ 个 $W$ 或 $L$ 的位置；
  $pos[sum[i-1] + k]$

如果出现平分也就是 $\vert cntW-cntL \vert <= 1$ 的情况，就是需要知道从第 $i$ 轮开始，到第几轮才会打破平均；
  $p[i]$ 表示从第 $i$ 局开始什么时候打破平局；
  $p[i] = (s[i] == s[i+1])?i+1:p[i+2]$；

代码实现

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-6
	#define mod 998244353
	#define MAXN 1e9
	#define MS 1000009

int n,m;
char s[MS];
int qz[2][MS];
int pos[2][MS], cnt[2];
int p[MS];
int f[MS];
int a[MS];

void init(){
	a[1] = 1;
	for(int i=2;i<=n;i++){
		a[i] = (LL)a[i-1]*(LL)(n+1)%mod;
	}
}

int jdg(int l,int x){
	int r1 = n+1, r2 = n+1;
	if(qz[1][n] - qz[1][l-1] >= x){
		r1 = pos[1][ qz[1][l-1] + x ];
	}
	if(qz[0][n] - qz[0][l-1] >= x){
		r2 = pos[0][ qz[0][l-1] + x ];
	}
	int r = min(r1, r2);
	if(r > n) return 0;
	
	int cnt1 = qz[1][r] - qz[1][l-1];
	int cnt2 = qz[0][r] - qz[0][l-1];
	
	if(abs(cnt1-cnt2) >= 2){
		if(cnt1 > cnt2) f[x]++;
		return r+1;
	}
	else{
		if(cnt1 == cnt2) r = p[r+1];
		else r = p[r];
		if(r == -1) return 0;
		else{
			cnt1 = qz[1][r] - qz[1][l-1];
			cnt2 = qz[0][r] - qz[0][l-1];
			if(cnt1 > cnt2) f[x]++;
			return r+1;
		}
	}
}

void cal(int x){
	int l = 1;
	while(l < n && l){
		l = jdg(l,x);
	}
}

void solve(){
	cin >> n; init();
	cin >> s+1;
	for(int i=1;i<=n;i++){
		if(s[i] == 'W'){
			qz[1][i] = qz[1][i-1] + 1;
			qz[0][i] = qz[0][i-1];
			pos[1][++cnt[1]] = i;
		}
		else if(s[i] == 'L'){
			qz[0][i] = qz[0][i-1] + 1;
			qz[1][i] = qz[1][i-1];
			pos[0][++cnt[0]] = i;
		}
	}
	p[n] = p[n+1] = -1;
	for(int i=n-1;i>=1;i--){
		if(s[i] == s[i+1]) p[i] = i+1;
		else p[i] = p[i+2];
	}
	for(int i=1;i<=n;i++){
		cal(i);
//		cout << f[i] << " ";
	}
	
	LL ans = 0;
	for(int i=1;i<=n;i++){
		ans += (LL)f[i]*(LL)a[i]%mod;
		ans %= mod;
	}
	cout << ans%mod << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	int ce;
//	cin >> ce;
	ce = 1;
	while(ce--){
		solve();
	}



	return 0;
}
/*




*/
Prev
2021-09-07 21:06:00 # ACM
Next