C题：Cheating and Stealing
题目大意
solution
乍一看题目非常简单，枚举
i
:
1
→
n
i :1\to n
i:1→n,然后把整个字符串扫一遍求出所有
f
i
(
S
)
f_i(S)
fi(S)。但这样的时间复杂度是
O
(
n
2
)
O(n^2)
O(n2)。而题目的测试数据范围是
1
≤
n
≤
1
0
6
1\leq n\leq 10^6
1≤n≤106，显然不允许。需要换个思路。
根据题意Gromah想要在分数上限为
i
i
i时获胜。
则需满足
得
分
的
次
数
≥
i
，
并
且
得
分
次
数
−
失
分
次
数
（
即
对
方
得
分
）
≥
2
得分的次数\geq i ，并且得分次数-失分次数（即对方得分）\geq 2
得分的次数≥i，并且得分次数−失分次数（即对方得分）≥2
对于得分，使用前缀和可以解决这个问题。某一区间[x,y]内的得分为W[y]-W[x]
再开一个数组储存在一个区间内的得失分的差值。从而实现
O
(
1
)
O(1)
O(1)的询问时间复杂度。总共的局数
=
n
i
(
i
为
)
=\large\frac{n}{i}(\small i为)
=in(i为)呈现调和级数的形式。就能做到把时间复杂度降到
O
(
n
l
o
g
n
)
O(n\ log\ n)
O(n log n)
c o d e \large code code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+7,mod=998244353;
char s[N];
int n,L[N],W[N],d[N],pL[N],pW[N],f1[N],f2[N];
void pre()
{
int k;
for(int i=n;i>=1;i--){
k=i+1;
while(k<=n&&d[k]<=d[i]) k=f1[k];//f1[i]表示i点后Gromah得分的最近的点下标
f1[i]=k;
k=i+1;
while(k<=n&&d[k]>=d[i]) k=f2[k];//f1[i]表示i点后Gromah失分的最近的点下标
f2[i]=k;
}
}
void solved()
{
ll ans=0,p=1;
for(int i=1;i<=n;i++)
{
int endit=1e9+7,x=1;
ll sum=0;
while(W[n]-W[x-1]>=i||L[n]-L[x-1]>=i)
{
endit=1e9+7;//endit是该局比赛结束（有一人已经获胜）的末尾下标
if(W[n]-W[x-1]>=i) endit=min(endit,pW[W[x-1]+i]);
if(L[n]-L[x-1]>=i) endit=min(endit,pL[L[x-1]+i]);
if(abs(d[endit]-d[x-1])<2){//还不存在两分的分差，继续向后
int o1=endit,o2=endit;
while(o1<=n&&d[o1]-d[x-1]<2){
o1=f1[o1];
}
while(o2<=n&&d[o2]-d[x-1]>-2){
o2=f2[o2];
}
endit=min(o1,o2);//更新末尾下标
if(endit>n) break;//全部遍历完成，跳出循环
}
if(d[endit]-d[x-1]>0)//Gromah这一局获得胜利
sum++;
x=endit+1;//开始下一局
}
ans=ans+sum*p%mod;//计算结果
p=p*(1+n)%mod;
}
cout<<ans<<"\n";
}
int main()
{
cin>>n>>(s+1);
for(int i=1;i<=n;i++){
L[i]+=L[i-1];//统计前缀和，到i点为止已经有多少个L或W
W[i]+=W[i-1];
if(s[i]=='L'){
L[i]++;
pL[L[i]]=i;//记录各个为L的点的下标
}
if(s[i]=='W'){
W[i]++;
pW[W[i]]=i;//记录各个为W的点的下标
}
d[i]=W[i]-L[i];
}
pre();
solved();
return 0;
}