社区讨论

求助!!!

灌水区参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m5ys6845
此快照首次捕获于
2025/01/16 11:38
去年
此快照最后确认于
2025/01/16 15:20
去年
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e7+10;
struct Node{
	int q,h;
}o[N];
char s[N];
int x[N],pri;
//x[] x的位置
int n,m,k;
int ansx;
//ansx x的数量
int ans;
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=n;i++){
		if(s[i]=='o'){
			o[i].q=o[i-1].q+1;
		}
		else o[i].q=0,ansx++,x[++pri]=i;
	}
	for(int i=n;i>=1;i--){
		if(s[i]=='o'){
			o[i].h=o[i+1].h+1; 
		}
		else o[i].h=0;
	}
	o[x[1]-1].q+=o[x[pri]+1].h;
	o[x[pri]+1].h=o[x[1]-1].q;
	if(k>ansx){
		if(k/ansx>m){
			cout<<n*m;
			return 0;
		}
		ans+=n*(k/ansx);
		k%=ansx;
		int maxt=INT_MIN;
		for(int i=1;i<=pri;i++){
			x[pri+i]=x[i]+n;
			o[x[pri+i]+1].h=o[x[i]+1].h;
			o[x[pri+i]-1].q=o[x[i]-1].q;
		}
		for(int i=1;i<=pri*2;i++){
			maxt=max(maxt,x[i+k-1]-x[i]+1+o[x[i]-1].q+o[x[i+k-1]+1].h);
		}
		ans+=maxt;
		cout<<ans;
	}
	else if(k==ansx){
		if(m==1){
			cout<<n;
		} 
		else{
			int maxt=INT_MIN;
			for(int i=1;i<=pri;i++){
				x[pri+i]=x[i]+n;
				o[x[pri+i]+1].h=o[x[i]+1].h;
				o[x[pri+i]-1].q=o[x[i]-1].q;
			}
			for(int i=1;i<=pri*2;i++){
				maxt=max(maxt,x[i+k-1]-x[i]+1+o[x[i]-1].q+o[x[i+k-1]+1].h);
			}
			cout<<maxt; 
		}
	}
	else{
		if(m==1){
			int maxt=INT_MIN;
			for(int i=1;i<=pri;i++){
				maxt=max(maxt,x[i+k-1]-x[i]+1+o[x[i]-1].q+o[x[i+k-1]+1].h);
			}
			cout<<maxt;
		}
		else{
			int maxt=INT_MIN;
			for(int i=1;i<=pri;i++){
				x[pri+i]=x[i]+n;
				o[x[pri+i]+1].h=o[x[i]+1].h;
				o[x[pri+i]-1].q=o[x[i]-1].q;
			}
			for(int i=1;i<=pri*2;i++){
				maxt=max(maxt,x[i+k-1]-x[i]+1+o[x[i]-1].q+o[x[i+k-1]+1].h);
			}
			cout<<maxt;
		}
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...