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 （思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。