模拟赛想出来的贪心算法,求证伪
查看原帖
模拟赛想出来的贪心算法,求证伪
373530
Reply_楼主2023/7/23 18:59

考场上40pts,赛后交到你谷竟有70pts,求哪里错了

#include<bits/stdc++.h>
#define R register
#define F(i,a,b) for(R int i = (a);i<=(b);i++)
using namespace std;

inline int read()
{
	R int x=0,t=1;
	R char ch=getchar();
	for(;ch<'0' || ch>'9';){
		if(ch=='-') t=-1;
		ch=getchar();
	}
	for(;ch>='0' && ch<='9';){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*t;
}
const int N=1e5+10;
char s[N],res[N];
int ans;
inline void solve()
{
	scanf("%s",s+1);
	int L=strlen(s+1);
	for(int i = 1;i<=L;i++){
		int r=i;
		if(res[i]==s[i]) continue;
		for(int j = i+1;j<=L;j++) {
			if(s[j]==s[i]) r=max(r,j);
		}
	//	cout << i << "->" << r << '\n';
	//	res[i]=s[i];
		ans++;
		for(int j = i+1;j<=r;j++){
			if(res[j-1]==s[j-1] && res[j]!=s[j]){
			//	cout << j << '\n';
			//	res[j]=s[i];
				ans++;
			}
		//	if(res[j]!=s[j]) res[j]=s[i];
		}
		for(int j = i+1;j<=r;j++){
			if(res[j]!=s[j]){
			//	res[j]=s[i];
				res[j]=s[i];
			}
		//	if(res[j]!=s[j]) res[j]=s[i];
		}
		res[i]=s[i];
	//	cout << ans << '\n';
	//	for(int j = 1;j<=L;j++){
	//		cout << j <<" " << res[j] << '\n'; 
	//	}
	}
	cout << ans << '\n';
}
int main()
{
	solve();
	return 0;
}


每一个发现没填对的点i,找到出现它的最右边的地方,在i与r区间内搜,如果是填对的就分段,最后把所有都填上去

2023/7/23 18:59
加载中...