拿到了我在 CF 历史上的最高排名。

非常惊险刺激。

非常惊的经历，开局 $5$ 分钟过了第一题，第二题一个神奇的细节题，交了一发 WA 掉，交第二发继续 WA 掉。想着细节题也不太好调，于是跳过直接去做第三题，似乎是一个简单贪心，交了一发 WA 掉，发现了贪心的错误，修改后又 WA 掉。

当时排名已经掉到三千五了，这样肯定要掉分掉成 Pupil 了，真的要 WA 的一声哭出来。调了很久的第三题又没有结果，找不出任何的数据来 hack 我的程序。于是一边想着放弃一边喊着“翘翘加油”逼着自己去调题。

本来觉得 C 题会更好调，但很久后未果，又去看 B 题。终于，转机出现了，我找到了一个使我错误的数据，是一个判断错了，具体的下面题解里会讲。看到 Pretests Passed 的那一刻我真的叫出来了。

最后十五分钟，调 C 题还有希望吗？当然要奋战到最后一刻！最后五分钟，终于找出了 hack 数据，最后三分钟的时候通过了 Pretests。

极限改出成功，翘翘真棒！

所以任何时候都不要丧失奋斗的勇气，转机总在不经意间出现。

A

xhf 违反了隔离规定，被关起来了，他被关在 $n\times m$ 的网格中，最少需要打通几面墙，才能让每一件囚室都有通向外面的通道？

易得，答案是 $n \times m$。

证明：

将囚室们看成 $n \times m$ 个块，外部空间看成一个块，题目要求就是要让所有的 $n \times m + 1$ 个联通块并成一个。

因为至少要打掉一面墙才可以让两个联通块并成一个，且打掉一面墙总能让联通块个数减少一个，所以至少需要联通块个数减去一次操作，即答案为 $n \times m + 1- 1 = n \times m$

B

输入一个序列，请通过下面的方式构造它： $a_1 = s \mod m$ 且对于任意 $1 < i \le n$ 满足 $a_i = (a_{i-1} + c) \mod p$, 求最大的 $m$ 并输出一个合适的 $c$, 若没有答案输出 -1, $m$ 可以无限大输出 0.

首先考虑一些显而易见的 -1 的情况。

因为每次都对 $m$ 取模了，所以每次要么没有减去 $m$，要么加上 $c$ 减去 $m$ ，所以每组增加的相邻两个的增加量必须相同，减少的减少量也必须相同，不然就是 -1。

然后考虑显而易见的 0 的情况，只有增加的和只有减少的 $m$ 肯定可以无限大了，增加的则一直不取模即可，减少的设每次减少的是 $rec$, 则只要满足 $c-m = rec$ 就可以， $m$ 也可以无限大。

然后可以考虑正常情况了，显然，每次增加的就是 $c$ , 而这个条件也可以完美地限制住 $m$, 若 $a_i < a_{i-1}$，$m$ 只能是 $a_{i-1} + c - a_i$ 了，因为其中所有数都是小于 $m$ 的，所以这种情况只能是 $a_i = a_{i-1} + c - m$, 移项可得。

这样的做法真的对吗，增加也有可能取模过了啊！但这样子显然可以把 $m$ 调的更大而满足所有条件，不可能称为最大解。

记得还要判断 $m$ 是否有冲突和是否有数大于等于了求得的 $m$。

考场代码如下。

#include <cstdio>
#define int long long
const int N = 100005;
int T, n, m, c, rec, a[N];
signed main() {
    scanf("%lld", &T);
    while(T--) {
        scanf("%lld", &n);
        c = -1, rec = -1, m = -1;
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        bool flag1 = false, flag2 = false, flag3 = false, flag4 = false;
        for(int i = 2; i <= n; i++) {
            if(c == -1 && a[i] >= a[i-1]) c = a[i] - a[i-1];
            else if(a[i] >= a[i-1] && a[i] - a[i-1] != c) {flag1 = true; break;}
            if(rec == -1 && a[i] < a[i-1])  rec = a[i-1] - a[i];
            else if(a[i] < a[i-1] && a[i-1] - a[i] != rec) flag2 = true;
        }
        if(flag1 || flag2) { puts("-1"); continue; }
        if(c == -1 && !flag2 || rec == -1 && !flag1) {puts("0"); continue; }
        for(int i = 2; i <= n; i++) 
            if(m == -1 && a[i] < a[i-1]) m = a[i-1] + c - a[i];
            else if(a[i] < a[i-1] && a[i-1] + c - a[i] != m) { flag3 = true; break;}
        if(flag3) { puts("-1"); continue; }
        for(int i = 1; i <= n; i++) 
            if(a[i] >= m) flag4 = true;
        if(flag4) puts("-1");
        else printf("%lld %lld\n", m, c);
    }
}

赛时的两次 WA 一次是因为没有判断数都小于 $m$ 的情况，一次是因为判断只上升出错了，认为 rec == -1 时只有 c == 0 才输出 0,且下降不均匀判 -1 需要只下降。 而实际上，只下降不均匀就可以判断 -1, 仅上升均匀无下降就可以判断 0。

C

$m$ 天， $n$ 个数，每天只有一些数能取，每个数取的次数不能超过 $\lceil \frac{m}{2} \rceil$ 次，有方案输出任意一种，没有方案输出 NO

很容易想到一个贪心，就是尽可能先满足出现次数少的，且已经选取次数小于 $\lceil \frac{m}{2} \rceil$ 的，但这样显然是错的。

可以被这样的数据卡掉: 有很多出现次数相等的，但一个是在最后唯一能取的，这样用贪心做就会把有解的情况判成 NO。

比如下面这组数据:

3 5 
1 1
2 1 3
2 1 3
2 1 3
1 3

如果你找最小时等号也更新，那么就会因为前面用了三次 $3$ 导致后面没得用而输出 NO。

怎么解决这个问题呢？

换一个处理顺序，先满足能取的个数少的再满足能取的多的，因为能取的多的能满足的希望肯定比能取的少的要大，所以这样的顺序只会变得更优而不会变得更差。

考虑怎么实现。

我的做法是写一个结构体，里面有一个 vector 用来存每一个可以取的，另用 id 记录这一个原来的编号，直接 sort 就可以了。这样的时间复杂度是不会有问题的，因为题目中保证了所有的 $k$ 的和不超过 $200000$ , 所以排序中交换所需时间和遍历所需时间段的积不会超过 $2000000$, 以快排的复杂度可以通过。

代码如下。

#include <cstdio>
#include <vector>
#include <algorithm>
const int N = 100005;ss
int T, n, m, num[N], in[N], x, k, ans[N];
bool flag;
struct twt {
    std::vector<int> a;
    int id;
    bool operator < (twt b) const {
        return a.size() < b.a.size();
    }
} f[N];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);

        for(int i = 1; i <= m; i++) f[i].a.clear(), ans[i] = 0;
        for(int i = 1; i <= n; i++) in[i] = 0, num[i] = 0;
        flag = 0;

        for(int i = 1; i <= m; i++) {
            scanf("%d", &k);
            f[i].id = i;
            for(int j = 1; j <= k; j++)
                scanf("%d", &x), f[i].a.push_back(x), num[x] ++;
        }
        std::sort(f+1, f+1+m);
        for(int i = 1; i <= m; i++) {
            int minj = -1, min = m+1;
            for(int j = 0; j < (signed)f[i].a.size(); j++) 
                if(num[f[i].a[j]] < min && in[f[i].a[j]] < (m+1)/2)  {
                    minj = f[i].a[j];
                    min = num[f[i].a[j]];
                }
            if(minj == -1) {flag = 1; break;}
            in[minj] ++;
            ans[f[i].id] = minj;
        }
        if(flag) puts("NO");
        else {
            puts("YES");
            for(int i = 1; i <= m; i++) printf("%d ", ans[i]);
            puts("");
        }
    }
    return 0;
}

第二次 WA 的原因我原来 min 直接赋值为 f[i].a[0], 但这个实际上可能是不能取的。

真是非常惊险的比赛体验。希望我以后的学习中能静下心来，想清楚每一个问题再去写代码，不要再这样自己给自己倒扣 $200$ 分了。

加油。

意外之喜。😄

有人被 Skip 了。排名又上升了。