2021牛客暑期多校训练营#5:C-Cheating and Stealing

2021牛客暑期多校训练营#5:C-Cheating and Stealing

原题链接：https://ac.nowcoder.com/acm/contest/11256/C

题目大意

G和P两个人打乒乓，共打了$n(1\le n\le 10^6)$个球，比赛结果可以用长度为$n$的由“W”和“L”组成的字符串$S$表示，“W”表示G赢了一球，“L”表示P赢了一球。

1. 检查在当前$S$中，是否存在任意前缀的$max(cn{t}_W,cn{t}_L)\ge i,|cn{t}_W?cn{t}_L|\ge 2$,其中$cn{t}_W$表示前缀中“W”的数量，$cn{t}_L$表示前缀中“L”的数量。
2. 如果不存在这样的前缀，则结束。
3. 如果存在，选择最短的满足条件的前缀，若$cn{t}_W>cn{t}_L$,则$f_i(S)$加$1$,反之不变。然后删除这段前缀，回到第一步。

求对于任意$i{\sum }_{i=1}^{|S|}{f}_i(S)\times (|S|+1{)}^{i?1}\mathrm{m}\mathrm{o}\mathrm{d}998244353$

解题思路

首先我们要抓住时间复杂度，发现它只可能以$O(nlogn)$甚至$O(n)$的时间内完成。
根据题意，在不考虑拉分的情况，总局数$={\sum }_{i=1}^n\frac{n}{1}+\frac{n}{2}+\frac{n}{3}\dots +\frac{n}{n}$,可以看出这是一个调和级数，总局数肯定小于等于$nlogn$,为我们的枚举做了保障。
之后是找出用$O(1)$判断的方法，我们用$num{r}_i$记录 { 1 , 2 , 3 … i } \{1,2,3\ldots i\} { 1,2,3…i}中最后一个“L”,用$num{l}_i$记录 { 1 , 2 , 3 … i } \{1,2,3\ldots i\} { 1,2,3…i}中最后一个“W”；$p{r}_j$表示第j个“L”在哪，$p{l}_j$表示第j个“W”在哪；$d_k$表示第k个符合$S_i==S_{i?1}$的i，理解这些变量可以AC这道题。

代码如下

#include<bits/stdc++.h>
#define For(i,n,m) for(int i=n;i<=m;i++)
#define FOR(i,n,m) for(int i=n;i>=m;i--)
#define mod 998244353
using namespace std;
const int MAXN=1e6+5;
int n,numl[MAXN],numr[MAXN],pl[MAXN],pr[MAXN],d[MAXN];
char c[MAXN];int pm(int x,int p){
    int ret=1;while(p){
    if(p&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;p>>=1;}return ret;
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0);cin>>n;cin>>c+1;int u=0,v=0,last=n+1;For(i,1,n){
    numl[i]=numl[i-1]+(c[i]=='W');numr[i]=numr[i-1]+(c[i]=='L');if(c[i]=='W')pl[++u]=i;else pr[++v]=i;}d[n]=n+1;FOR(i,n-1,1){
    if(c[i]==c[i+1])last=i+1;d[i]=last;}int ans=0;For(k,1,n){
    int s=0,tt,sum=0;while(numl[s]+k<=u||numr[s]+k<=v){
    if(s>n)break;if(numl[s]+k>u){
    tt=pr[numr[s]+k];if((numr[tt]-numr[s])-(numl[tt]-numl[s])<2){
    while(abs((numr[tt]-numr[s])-(numl[tt]-numl[s]))<2){
    if(tt>n)break;tt=d[tt];}if(tt>n)break;s=tt;if(c[s]=='W')sum++;}else s=tt;}else if(numr[s]+k>v){
    tt=pl[numl[s]+k];if((numl[tt]-numl[s])-(numr[tt]-numr[s])<2){
    while(abs((numl[tt]-numl[s])-(numr[tt]-numr[s]))<2){
    if(tt>n)break;tt=d[tt];}if(tt>n)break;s=tt;if(c[s]=='W')sum++;}else s=tt,sum++;}else if(pl[numl[s]+k]<pr[numr[s]+k]){
    tt=pl[numl[s]+k];if((numl[tt]-numl[s])-(numr[tt]-numr[s])<2){
    while(abs((numl[tt]-numl[s])-(numr[tt]-numr[s]))<2){
    if(tt>n)break;tt=d[tt];}if(tt>n)break;s=tt;if(c[s]=='W')sum++;}else s=tt,sum++;}else{
    tt=pr[numr[s]+k];if((numr[tt]-numr[s])-(numl[tt]-numl[s])<2){
    while(abs((numr[tt]-numr[s])-(numl[tt]-numl[s]))<2){
    if(tt>n)break;tt=d[tt];}if(tt>n)break;s=tt;if(c[s]=='W')sum++;}else s=tt;}}ans=(ans+sum*pm(n+1,k-1)%mod)%mod;}cout<<ans;return 0;
}