Solution of CF1108C

题目链接

本题要我们修改最少的字符使 \(s_i=s_j\) 且 \(i\equiv j\) (mod 3).用人话来讲就是使令'R' 'G' 'B'三个字母构成的循环节构成一个字符串 \(s'\)。使

\[\sum[{s_i\neq s'_i]} \]

最小。

由于RGB只有三个字母,构成的循环节只有6种可能,分别为RBG,RGB,GRB,GBR,BRG,BGR.我们只需枚举这六种情况组成的字符串。判断其与原始字符串不相同的个数。最后取个min即可。

#include <bits/stdc++.h>
#define AK 1
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define per(i,a,b) for(register int i=a;i>=b;--i)

namespace FastIOstream{
	template <typename T> inline void read(T &x){//Fast read
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);){if(c=='-')f=-1;c=getchar();}
		for(;isdigit(c);){x=(x<<1)+(x<<3)+c-48;c=getchar();}
		x*=f;return;
	}
	template <typename T> void print(T x){//Fast print
		if(x<0){x=-x;putchar('-');}if(x>9)print((x>>1)/5);
		putchar(x%10+48);return;
	}
}

using namespace std;
using namespace FastIOstream;

string s[7],m;
string a[7];
int n,pos,num=1e9;

signed main(){
	s[1]="RGB";s[2]="RBG";s[3]="BRG";
	s[4]="BGR";s[5]="GBR";s[6]="GRB";
	read(n);
	cin >> m;
	int k=n/3+1;
	for(register int i=1;i<=6;++i){
		for(register int j=1;j<=k;++j){
			a[i]+=s[i];
		}
		int sum=0;
		for(register int j=0;j<n;++j){
			if(m[j]!=a[i][j])sum++;
		}
		if(sum<num){
			num=sum;
			pos=i;
		}
	}
	print(num);
	putchar('\n');
	for(register int i=0;i<n;++i){
		putchar(a[pos][i]);
	}
	putchar('\n');
	return 0;
}
上一篇:剑指offer计划4(查找算法简单版)---java


下一篇:单调队列优化DP