题目描述
甲乙两个人比赛乒乓，已知每一个回合的胜负的描述序列$S$，现在设$f_i(S)$表示当局点分为$i$时甲赢得比赛的次数，求：
其中赢得比赛是指该人已经超过局点分且超过对手至少两分。一局比赛结束后，下一局比赛的情形继续沿回合序列进行。
数据范围
分析与解
这个题最朴素的思路就是针对一个局点分来分析赢球的局数。其实这样也是可行的，因为分析复杂度，假设当前分析的局点分是$i$，那么场次不会超过$\frac{|S|}{i}$,因此如果我们能够在$O(1)$的复杂度内完成下一局的分析，那么总复杂度就是$O(|S|log|S|)$
下面考虑怎么来$O(1)$知道每一局在序列中的起始和终止位置。首先我们用前缀和$sumW,sumL$来维护到序列某个位置$i$,两人分别能赢多少回合，同时记录下来每个人赢第几个回合是对应序列中的哪个位置$posW,posL$。然后我们枚举下一个局点分到底由谁来得（这里见文末代码即可知）。
这里需要加速的地方在于两人交替赢球使得没有人能够超过对方两分的情形。这种局面可以预处理，即$tiebreak[i]=(s[i]==s[i+1]) ?i+1:tiebreak[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
| #include <bits/stdc++.h>
using namespace std;
#define min(a,b) (a)<(b) ? (a) : (b)
#define max(a,b) (a)>(b) ? (a) : (b)
typedef long long LL;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
#define MAXN 1001000
const int MOD = 998244353;
int n;
char s[MAXN];
int sumL[MAXN],sumW[MAXN];
int posW[MAXN],posL[MAXN];
LL quick_pow(int a,int b) {
LL ret=1;
while(b) {
if(b & 1)ret=ret*a%MOD;
a=1ll*a*a%MOD;
b>>=1;
}
return ret;
}
int tiebreak[MAXN];
int main() {
LL ans=0;
int k;
n=mread();
scanf("%s",s+1);
for(int i=1; i<=n; i++) {
sumL[i]=sumL[i-1];
sumW[i]=sumW[i-1];
if(s[i]=='W') {
sumW[i]++;
posW[sumW[i]]=i;
} else {
sumL[i]++;
posL[sumL[i]]=i;
}
}
int now,res,nxt;
int winL,winW;
tiebreak[n+1]=tiebreak[n]=n+1;
for(int i=n-1;i>=1;i--)
tiebreak[i]=(s[i]==s[i+1]) ? i+1 : tiebreak[i+2];
for(int i=1; i<=n; i++) {
now=0;
res=0;
while(now<n) {
nxt=n+1;
if(sumW[now]+i <= sumW[n])nxt=min(nxt,posW[sumW[now]+i]);
if(sumL[now]+i <= sumL[n])nxt=min(nxt,posL[sumL[now]+i]);
if(nxt>n)break;
winL=sumL[nxt] - sumL[now];
winW=sumW[nxt] - sumW[now];
if(abs(winL-winW)==1)nxt=tiebreak[nxt];
if(nxt>n)break;
winL=sumL[nxt] - sumL[now];
winW=sumW[nxt] - sumW[now];
if(winW>winL)res++;
now=nxt;
}
ans=(ans+1ll*res*quick_pow(n+1,i-1)%MOD)%MOD;
}
printf("%lld\n",ans);
return 0;
}
|