30pts
考场上看到这个题时，第一反应就是全部展开man慢算
诶，刚好有30分部分分可以 \(O(n)\) 维护
那么使用 \(tot\) 来记录遍历到哪一位了，当 \(tot\) 遍历到结尾时直接让他归0即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,len,tot,a,b,A,B;
char t[100100];
int main(){
cin>>n>>len>>t+1;
for(int i=1;i<=n;i++){
if(tot==len){
tot=0;
}
if(t[++tot]=='A'){
a++;
}
else{
b++;
}
if(a>=11&&a-b>=2){
A++;
a=b=0;
}
if(b>=11&&b-a>=2){
B++;
a=b=0;
}
}
cout<<A<<":"<<B<<endl;
}
50pts
发现如果某一次遍历完整个串之后恰好打完了一局，那么显然是一个循环节，于是可以每次结束时判断如果此时小红和 zwh 的得分都被清空了，就跳出循环。
有注意到3点：
- if 会增加时间复杂度
- 我们一个循环节的长度无法表示
- 不知道一个循环节的得分情况
对应的解决：
- 特判 \(n≤1e7\) 的情况
- 记录 \(last\) 表示跳出循环时的 \(i\) ，那么循环节的长度就是 \(last\) 了
- 记录 \(mapp[i]\) 和 \(mbpp[i]\) 分别表示 zwh 和 小红的得分情况
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,len,tot,flag=1,fff,a,ff,zxc=1e9,b,cnt1,cnt2,A,B,last;
map<int,int> mapp,mbpp;
char t[200100];
signed main(){
cin>>n>>len>>t+1;
if(n<7e7){
for(int i=1;i<=n;i++){
if(tot==len){
tot=0;
}
if(t[++tot]=='A'){
a++;
}
else{
b++;
}
if(a>=11&&a-b>=2){
A++;
a=b=0;
}
if(b>=11&&b-a>=2){
B++;
a=b=0;
}
}
cout<<A<<":"<<B<<endl;
return 0;
}
for(int i=1;i<=n;i++){
if(tot==len){
if(A==0&&B==0&&flag&&a==b){
cout<<"0:0";
return 0;
}
if(fff){
break;
}
if(a==0&&b==0){
fff=1;
break;
}
tot=0;
}
if(t[++tot]=='A'){
a++;cnt1++;
}
else{
b++;cnt2++;
}
if(a>=11&&a-b>=2){
A++;
a=b=0;
}
if(b>=11&&b-a>=2){
B++;
a=b=0;
}
if(abs(a-b)>=2){
flag=0;
}
mapp[i]=A;
mbpp[i]=B;
last=i;
}
if(!fff){
cout<<mapp[n]<<":"<<mbpp[n]<<endl;
return 0;
}
int ans=n/last*A+mapp[n%last],bns=n/last*B+mbpp[n%last];
cout<<ans<<":"<<bns<<endl;
}
100pts
叕发现当之前遍历完字符串之后和目前 zwh 和 小红 的得分一样，那么就也是一个循环节
以样例2为例(左侧zwh):
以 \(len\) 为周期比分变化为：
3 3
6 6
9 9
1 3
4 6
7 9
1 1
4 4
7 7
10 10
1 3
4 6
7 9
1 1
4 4
7 7
10 10
。。。
那么，只需要去除前3次遍历，就是一个完美的循环了！
最后剩余的部分也在循环里，所以可以直接求出！
时间复杂度：\(O(能过就行了应该是不大于1000的常数乘k吧)\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,len,tot,flag=1,fff,a,ff,zxc=1e9,b,cnt1,cnt2,A,B,last,mapp[3000100],mbpp[3000100];
char t[200100];
map<int,map<int,int> >ma;
signed main(){
cin>>n>>len>>t+1;
ma[0][0]=1;
for(int i=1;i<=n;i++){
if(tot==len){
if(A==0&&B==0&&flag&&a==b){
cout<<"0:0";//特判ABABABABABABABABABABABAB……的情况
return 0;
}
if(a==0&&b==0){
fff=1;
break;
}
if(ma[a][b]){
ff=ma[a][b];//记录循环的开始
zxc=i-ff-1;//记录循环节长度
fff=1;
break;
}
ma[a][b]=i-1;
tot=0;
}
if(t[++tot]=='A'){
a++;cnt1++;
}
else{
b++;cnt2++;
}
if(a>=11&&a-b>=2){
A++;
a=b=0;
}
if(b>=11&&b-a>=2){
B++;
a=b=0;
}
if(abs(a-b)>=2){
flag=0;
}
mapp[i]=A;
mbpp[i]=B;
last=i;
}
if(!fff){//当n特别小时
cout<<mapp[n]<<":"<<mbpp[n]<<endl;
return 0;
}
if(!ff){//当n比较小时
int ans=n/last*A+mapp[n%last],bns=n/last*B+mbpp[n%last];
cout<<ans<<":"<<bns<<endl;
}
else{
//重点！接下来两行相当难，建议自己思考懂，我只解释一点
// 解释：n-ff 是除去非循环部分，A-mapp[ff]同理
// mapp[ff+(n-ff)%zxc]-mapp[ff]是计算剩余部分
int ans=mapp[ff]+(n-ff)/(zxc)*(A-mapp[ff])+mapp[ff+(n-ff)%zxc]-mapp[ff];
int bns=mbpp[ff]+(n-ff)/(zxc)*(B-mbpp[ff])+mbpp[ff+(n-ff)%zxc]-mbpp[ff];
cout<<ans<<":"<<bns<<endl;
}
}
<details> <summary>点击查看代码</summary>
</details>