关于今晚 ARC B 题
查看原帖
关于今晚 ARC B 题
541069
SuperCowHorse楼主2022/9/11 22:00

看出贪心,总是会 WA 两个点,求调.

//chenye3
#include<bits/stdc++.h>
#define ll long long
#define do double
#define re register
#define mt mt19937
#define pb push_back
#define il inline
#define lowbit(x) (x&(-x))
#define sqr(x) (x*x)
using namespace std;
int n,len;
char s[5005],ans[5005];
int solve(){
	int u=0,mx=0,pos;
	for(int i=n-1;i>=0;--i){
		if(s[i]=='p')
			++u;
		else{
			if(u>=mx){
				mx=u;
				pos=i+u;
			}
			u=0;
		}
	}
	if(u>=mx){
		mx=u;
		pos=u-1;
	}
	return pos;
}
signed main(){
	scanf("%d%s",&n,s);
	int pos=n;
	for(int i=0;i<n;++i){
		if(s[i]=='d') ans[len++]='d';
		else{
			pos=solve();
			for(int j=pos;j>=i;--j)
				ans[len++]=s[j]=='p'?'d':'p';
			break;
		}
	}
	for(int i=pos+1;i<n;++i)
		ans[len++]=s[i];
	char tmp[5005];bool f=0;
//	cout<<ans<<'\n';
	for(int i=0;i<n;++i)
		tmp[i]=s[i];
	for(int i=0;i<n;++i){
		if(tmp[i]=='d'){
			if(f){
				for(int j=0;j<i;++j)
					tmp[j]='d';
				break;
			}
		}
		else f=1;
	}
//	cout<<ans<<'\n'<<tmp<<'\n';
	for(int i=0;i<n;++i){
		if(ans[i]=='d'&&tmp[i]=='p'){
			cout<<ans;
			return 0;
		}
		if(ans[i]=='p'&&tmp[i]=='d'){
			cout<<tmp;
			return 0;
		}
	}
	cout<<ans;
	return 0;
	int rp=0;
	while(1) rp++;
}
2022/9/11 22:00
加载中...