CF--思维练习--CodeForces - 219C Color Stripe （思维）

ACM思维题训练集合
A colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.

Input
The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

Output

Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

Examples
Input
6 3
ABBACC

Output
2
ABCACA
Input

3 2
BBB
Output
1
BAB

题目很简单，类比平面图的四色定理，线性上有3色定理，即如果k>=3那么无论遇到什么情况AABB的时候，我们都可以将相同的变成第三种颜色，所以这里要特判K=2的时候，我一开始想了很久，就是不知道怎么处理，但是k=2的串只有ABABA……和BABABA……这两种情况，判断当前穿变成这两种那种花费少，就是答案了。

#include <bits/stdc++.h> using namespace std; int n, m, cnt = 0; char check(char a, char b) {for (char i = 'A'; i <= 'A' + m - 1; i++){if (i == a || i == b)continue;elsereturn i;} } int main() {cin >> n >> m;string s;cin >> s;if (m == 2){int cnt1 = 0, cnt2 = 0;for (int i = 0; i < n; i++){if (s[i] != ('A' + (i % 2)))cnt1++;elsecnt2++;}if (cnt2 > cnt1){cout << cnt1 << endl;for (int i = 0; i < n; i++)if (i % 2 == 0)putchar('A');elseputchar('B');}else{cout << cnt2 << endl;for (int i = 1; i <= n; i++)if (i % 2 == 0)putchar('A');elseputchar('B');}puts("");return 0;}for (int i = 1; i < s.length();){if (s[i] == s[i - 1]){s[i] = check(s[i - 1], s[i + 1]);i = i + 2;cnt++;}elsei++;}cout << cnt << endl<< s << endl; }

总结

以上是生活随笔为你收集整理的CF--思维练习--CodeForces - 219C Color Stripe （思维）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。