题解：P13250 [GCJ 2014 #1B] The Repeater

· · 题解

先简述一下题意：

我们要通过添加或删除相邻重复字符的操作，使得所有字符串变得完全相同。对于当前测试点，如果可以完全相同输出最小操作次数，否则输出Fegla Won。

我们注意到操作的限制是只能添加或删除相邻重复字符，这意味着我们可以检验操作的可完成性，举个例子：

假如一个输入是这样的：

2
mmaw
maw

两个字符串转换为字符序列就是[('m',2),('a',1),('w',1)] [('m',1),('a',1),('w',1)]。

前面是记录这个字符，后面是记录这个字符的连续出现次数。

可以发现，当这两个字符串的字符序列项数相等和字符序列出现的顺序一致时，才能操作成功。

于是我们就可以先检验刚才提到的这两点性质，看他们是否满足，才继续操作，否则直接输出Fegla Won。

那我们如何求最小操作数呢？

其实这很简单，我们可以求两个字符串当前字符连续出现次数的中位数，这个字符的最小操作数就是这两个字符串中当前位置的连续出现次数分别减去中位数后的绝对值相加，那么总的最小操作数就是所有需要操作的字符的最小操作数累加而得。

总结一下，对于每个测试数据，主要的步骤是：

  1. 先对于满足有解的两个条件进行判断；
  2. 将两个字符串转换为上文提及的字符序列；
  3. 计算最小操作数，输出结果。

下面是代码实现：

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 100;
const int MAX_LEN = 100;

struct CharSeq {
    char c;
    int cnt;
};

int solve() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        int N;
        cin >> N;
        string strs[MAX_N];
        for (int i = 0; i < N; ++i) {
            cin >> strs[i];
        }

        // 生成字符序列
        bool possible = true;
        CharSeq seqs[MAX_N][MAX_LEN];
        int seq_len[MAX_N] = {0};

        for (int i = 0; i < N; ++i) {
            string &s = strs[i];
            int len = 0;
            if (!s.empty()) {
                seqs[i][len].c = s[0];
                seqs[i][len].cnt = 1;
                for (int j = 1; j < s.size(); ++j) {
                    if (s[j] == seqs[i][len].c) {
                        seqs[i][len].cnt++;
                    } else {
                        len++;
                        seqs[i][len].c = s[j];
                        seqs[i][len].cnt = 1;
                    }
                }
                seq_len[i] = len + 1;
            }
        }

        // 检查所有字符串的字符序列长度是否相同
        int base_len = seq_len[0];
        for (int i = 1; i < N; ++i) {
            if (seq_len[i] != base_len) {
                possible = false;
                break;
            }
        }

        // 检查每个位置的字符是否相同
        if (possible) {
            for (int pos = 0; pos < base_len; ++pos) {
                char c = seqs[0][pos].c;
                for (int i = 1; i < N; ++i) {
                    if (seqs[i][pos].c != c) {
                        possible = false;
                        break;
                    }
                }
                if (!possible) break;
            }
        }

        if (!possible) {
            cout << "Case #" << t << ": Fegla Won" << endl;
            continue;
        }

        // 计算最小操作次数
        int total_ops = 0;
        for (int pos = 0; pos < base_len; ++pos) {
            int cnts[MAX_N];
            for (int i = 0; i < N; ++i) {
                cnts[i] = seqs[i][pos].cnt;
            }

            // 排序后取中位数计算最小操作次数
            sort(cnts, cnts + N);
            int median = cnts[N/2];
            for (int i = 0; i < N; ++i) {
                total_ops += abs(cnts[i] - median);
            }
        }
        cout << "Case #" << t << ": " << total_ops << endl;
    }
    return 0;
}
int main() {
    solve();
    return 0;
}

主体逻辑就如上所述，注意输出的格式，以及有多组数据，不要以为只有一组。