[CodeForces 593A] 2Char

可以毫不犹豫的说这场CF是我有屎以来最失败的一场了，比赛期间交了两发A题都是Wrong answer on test 3，最终放弃回去(wan)睡(shou)觉(ji)，然后愉快的挂了0而且获得了-108的Rating change，成功创下历史最大跌幅~

睡了一觉冷静了一下之后，开始思考为什么会出现这样的问题……至于这道题，原因还是从思路说吧。

题目不难，题意也不难理解，就是给你一些字符串，你要从中选出几个组成一篇文章，要求就是只出现两个字母并且文章要尽可能长。最后输出文章长度。

我也不是什么机智的人，没想到什么厉害的奇技淫巧，所以思路还是按照原始的题意走的。首先定义了一个结构体，用来表示一个字母出现的次数：

typedef struct {
    char ch;
    int n;
}CH;

然后呢，只要再用一个vector，就能很简单的描述单个字符串中每个字符出现的次数了。为了方便，再写一个typedef：

typedef vector WORD;

现在就可以开始处理题目了。首先是读取所有的字符串，把他转化成上面所写的描述方式，即出现了哪些字母，以及他们出现的次数：

int n;
cin >> n;
vector wd(n);
for (auto& w: wd) {
    string tmp;
    cin >> tmp;
    for (auto& c: tmp) {
        bool flag = false;
        for (auto& i: w) {
            if (c == i.ch) {
                i.n++;
                flag = true;
                break;
            }
        }
        if (!flag) {
            CH t;
            t.ch = c;
            t.n = 1;
            w.push_back(t);
        }
    }
}

按照题意，出现三个或者更多字母的字符串是不可能被计入的，于是就把他们筛掉，留下那些只有两个或者一个字母出现过的字符串。判断一个单词中字母出现的的次数很简单，直接用vector的成员函数size()就可以解决。与此同时，把所有的留下的字符串中出现的字母统计一下，放入all中：

WORD all;
vector sel;
for (auto& w: wd) {
    if (w.size() >= 3) continue;
    sel.push_back(w);
    for (auto& i: w) {
        bool flag = false;
        for (auto& c: all)
            if (c.ch == i.ch) {
                c.n += i.n;
                flag = true;
                break;
            }
        if (!flag) 
            all.push_back(i);
    }
}

经过这样一波处理后，sel内就保存了所有只出现过一个或两个字母的字符串，同时all里面统计了sel中所有的字符串中出现过的所有字母。

这样之后，答案所选的字符串毫无疑问就是all中抽出的一个或两个字母，问题也就在这出现了：比赛期间我没有考虑到所有字符串内都只有一个字母的情况！

int res = 0, tmp;
for (int i = 0; i < all.size(); i++) {
    char c1 = all[i].ch;
    tmp = 0;
    //这个循环是比赛后看到错误原因了才补上的
    for (auto& w: sel) {
        if (w.size() == 1 && w[0].ch == c1)
            tmp += w[0].n;
    }
    res = max(tmp, res);
    for (int j = i + 1; j < all.size(); j++) {
        char c2 = all[j].ch;
        tmp = 0;
        for (auto& w: sel)
            if (w.size() == 1 && (w[0].ch == c1 || w[0].ch == c2))
                tmp += w[0].n;
            else if ((w[0].ch == c1 && w[1].ch == c2) || (w[1].ch == c1 && w[0].ch == c2))
                tmp += w[0].n + w[1].n;
        res = max(tmp, res);
    }
}

出了这个问题只要一组很简单的数据就能轻松爆掉我的代码：

1
a

答案显然是1，但是如果按照我原来的代码，直接就跳出循环了，愉快的输出了0……

---

于是我就去看了王诗钧的代码，理解后立马把自己的代码改写了试试，全文：

#include 

using namespace std;

typedef struct {
    char ch;
    int n;
}CH;
typedef vector WORD;

int main()
{
    int n;
    int table[256][256];
    for (auto &i: table)
        fill(i, i + 256, 0);
    cin >> n;
    vector wd(n);
    for (auto& w: wd) {
        string tmp;
        cin >> tmp;
        for (auto& c: tmp) {
            bool flag = false;
            for (auto& i: w)
                if (c == i.ch) {
                    i.n++;
                    flag = true;
                    break;
                }
            if (!flag)
                w.push_back({c, 1});
        }
        if (w.size() >= 3) continue;
        if (w.size() == 1)
            table[w[0].ch][0] += w[0].n;
        else
            table[min(w[0].ch, w[1].ch)][max(w[0].ch, w[1].ch)] += w[0].n + w[1].n;
    }
    int res = 0;
    for (int i = 'a'; i <= 'z'; i++)
        for (int j = i + 1; j <= 'z'; j++)
            res = max(res, table[i][j] + table[i][0] + table[j][0]);
    cout << res ;
    return 0;
}

#待补充理解

不过就算是有了别人的方法，还是WA了一次……最后的两个for循环处z没有等号，然后也是愉快的一组数据爆掉代码……

2
z
z

#待补充整体分析