竞赛总览

竞赛题解

贝博士最近收到了一些来自外星的信号，它们看起来是一些字符。经过贝博士的转码，把这些字符用26个小写拉丁字母表示。贝博士叫来了助手艾小姐，请她把这些字母中出现次数最多者挑出来，并按字母表顺序排列出来（忽略空格）。

创建一个结构体，用来统计字符出现的次数。

struct node {
    int index;
    int count;
};

node data [256];

结构体包含两个字段，第一个字段是字符的编号，第二个字段是字符出现的次数。

然后初始化一下：for (int i = 0; i < 256; i++) data [i].index = i;

使用循环逐个字符输入：while (scanf ("%c", &c) != EOF);

while (scanf ("%c", &c) != EOF) {
    if (c == ' ') continue;
    data [c].count += 1;
}

使用桶排序的方式，统计每种字符的数量。

int cmp1 (node x, node y) {
    return x.count > y.count;
}

std::sort (data, data + 256, cmp1);

按字符数量进行降序排序。

int index, max = 0;
for (index = 1; index < 256; index++) {
    if (data [index].count != data [max].count) {
        break;
    }
}

再统计出现次数最多的字符数量。

int cmp2 (node x, node y) {
    return x.index < y.index;
}

std::sort (data, data + index, cmp2);

最后，将出现次数最多的这些字符，按照字典序进行升序排序，得到最终答案。

给定一已排序的正整数组成的数组，求需要在中间至少插入多少个数才能将其补全成为一等差数列。在中间插入的意思是不能在第一个数之前或最后一个数之后插入数据。

数据已经排好序了，只需逐个输入便可直接使用。

int data [100005], len = 0;

while (scanf ("%d", &data [len]) != EOF) len++;

将数据输入到数组中。如果输入数据的长度小于2，无需插入数据，直接输出0即可。

再令数据的差值初值为 int d = data [1] - data [0]。

注意：如果这里得到的第一个差值就是 0，无需进行后续差值计算，直接进入特判流程（下文有解释）。

然后从第二项开始计算新的差值：

for (int i = 2; i < len && d != 0; i++) {
    int dis = data [i] - data [i - 1];
    if (dis == 0) return def ();
    d = gcd (d, dis);
}

这里便是本题解法的关键部分了。

给定的等差数列有如下几种形式：

类型1、相同差值型：1 3 (5) (7) 9。这种类型的等差数列，差值非常典型。1 和 3 差值为 2，3 和 9 差值为 6，两种差值的最大公约数为 2，这意味着只要以 2 为公差，将缺失的数据补足即可。

类型2、不同差值型：1 (3) 5 (8) 11。这种类型的等差数列，根据相邻数据求出差值，再计算差值之间的最大公约数，发现最大公约数是 1，这意味着只能以 1 为公差。补齐之后，数据变为 1 (2 3 4) 5 (6 7 8 9 10) 11。

以第一种类型为例，1 和 9 之间相差 8，以 2 来补，需要补 3 项。已经有一项了，最终需要补 2 项。

以第二种类型为例，1 和 11 之间相差 10，以 1 来补，需要补 9 项。已经有一项了，最终需要补 8 项。

以此得到补齐数据时的项数计算方法：(data [len - 1] - data [0]) / d - len + 1。

此外，还有一种类型的等差数列，公差为 0，特征是相邻元素之间的差值出现过 0。

例如：2 2 2 就可以构成一组公差为 0 的等差数列。这种情况下，每一项数据必须都一致才行。

如果遇到这种情况，必须对整个数列进行相邻两两比较。

如果在比较过程中，遇到不一致的数据，说明无法构成等差数列（这种情况非常特殊，无法补充任何值使其成立，即使补 1 也不行）。反之，数据都一致，说明数列本身就是等差数列，不需要补充新的数据，输出 0 即可。