Codeforces 219C

==> 原题链接
实际上也是 LETTers 2014 Winter Round 1 Div 1 A 题

题目概述

给定长为n的字符串，和从A 开始的 K种字母，求通过最少的调整，使得得到的字符串任意相邻两字母不同。

思路

还是贪心。对于连续奇数个相同的字母，替换掉中间的(n-1)/2 个，对于偶数个相同字母，替换n/2个，特别的k == 2时，就是只有两种字母，则整个字符串只有ABABA... 或BABAB...两种样子，如果要写在通用匹配规则里面，异常麻烦。倒不如直接枚举判断ABABA 或BABAB那种成本小，直接输出即可。

代码

#include <stdio.h>
#include <string.h>

int n, p, ans = 0, ans1 = 0, ans2 = 0;
char row[500000 + 10], row1[500000 + 10], row2[500000 + 10];

void paint(int pos);


int main()
{
    freopen("A.in", "r", stdin);

    int i = 1, j, k, f;

    scanf("%d%d", &n, &p);
    scanf("%s", row);

    if (p == 2)
    {
        row1[0] = 'A';
        row2[0] = 'B';
        for (i = 1; i < n; i++)
        {
            row1[i] = 'A' + 'B' - row1[i - 1];
            row2[i] = 'A' + 'B' - row2[i - 1];
        }
        for (i = 0; i < n; i++)
        {
            if (row[i] != row1[i])
            {
                ans1++;
            }
            if (row[i] != row2[i])
            {
                ans2++;
            }
        }
        if (ans1 <= ans2)
        {
            printf("%d\n", ans1);
            printf("%s\n", row1);
        }
        else
        {
            printf("%d\n", ans2);
            printf("%s\n", row2);
        }
        return 0;
    }
    while(i < n)
    {
        if (row[i] == row[i-1])
        {
            j = i + 1;
            f = 2;
            while(row[j] == row[i])
            {
                j++;
                f++;
            }
            if (f & 1)
            {
                ans += (f - 1) / 2;
                for (k = i; k < j; k += 2)
                {
                    paint(k);
                }
            }
            else
            {
                ans += (f / 2);
                for (k = i; k < j; k += 2)
                {
                    paint(k);
                }
            }
            i = j - 1;
        }
        i++;
    }
    printf("%d\n", ans);
    printf("%s\n", row);

    return 0;
}

void paint(int pos)
{
    int i;

    for (i = 0; i < p && i < 26; i++)
    {
        if (pos + 1 < n)
        {
            if (i + 'A' == row[pos + 1])
            {
                continue;
            }
        }
        if (pos - 1 >= 0)
        {
            if (i + 'A' == row[pos - 1])
            {
                continue;
            }
        }
        row[pos] = i + 'A';
        return;
    }
}