洛谷秋令营Day2-模拟赛

实况记录

• 下午 1 点 50，拿到了题目和样例的压缩包，但是需要 2 点才能拿到密码解压，于是趁这会儿把代码模板敲了一下，并且写了一下对拍的 gen.cpp 和 check.cpp 的框架。后来发现虽然不能打开压缩包里面的东西，但能看到压缩包的结构，于是把比赛时要用的目录也建好了。
• 2 点解压，按照比赛前的准备，先把 4 个题目都看一下。
• T1 是个图论题，很容易想到一个 $O(n^4\log n)$ 的暴力做法，理论上能拿 40 分，更进一步的做法暂时没想到；T2 感觉很不擅长的样子，最暴力的分数也不知道该怎么打，暂时跳过；T3 是一个异或相关的题目，发现最低一档的暴力分可以强行枚举每个位置的值，从而把所有的序列都枚举出来，然后判断是不是每个位置都符合题意，这样可以拿 20 分；T4 是个字符串题，我挺不擅长的，发现最低一档的 5 分暴力大概是可以做的，强行枚举拼接，并进行暴力字符串匹配即可解决，另外注意到性质 A 说字符串仅有 a 这种字母，感觉会变成一道组合数学题，等会儿做到这个题写了暴力之后再继续想想。至此，过去了 25 分钟，大概知道了 65 分的做法，很寄，第一次开局这么差。
• 开始写 T1，很快就写好了 40 分的暴力，把 3 个样例测了下都过了，然后去看 T2。
• T2 看了几分钟，实在是不会做，还是写 T3 吧。
• T3 较快地写出了暴力，测了样例没问题。
• 我评估 T4 的 5 分暴力写起来好像也不是很好写，感觉整个人还没进入状态，于是先没去写 T4，回去想了一下 T1 和 T2。
• 现在是 16 点，赛程过半，T1 目前是理论上能得 40 分，想花时间一下 60 分的做法，而 T2 目前是毫无头绪，感觉后边至少应该能在这个题上拿到 15 分的暴力。稍微想了一下，感觉还是 T1 更有可能做出来，就去看 T1 了，规定 16 点 25 之前如果 T1 还没想到 60 分思路，就去看 T2。
• T1 用了十几分钟，大概想到了一个 $O(n^3 \log n)$ 的算法，能过 $n \le 200$ 的情况，至少能拿 60 分。感觉和最短路算法有点像，更新了度数之后看是否度数之和大于 $k$ 了，是的话就标记一下并放到一个结构里面等待处理。这个做法写起来估计比 T4 还难写，于是先回去把 T4 的 5 分暴力写了。
• 回来写 T1 的 60 分做法，写好之后测了下样例，没问题，然后开始写对拍，拍了 10 分钟左右没发现错误，感觉应该稳了。100 分做法感觉想不出来，于是 T1 就这样了。
• 到现在，还剩下 1.5 小时左右，T2 还没做，我估计剩下所有没得的分里面应该 T2 的是最好得的了，于是去做 T2。
• 发现 T2 好像就是求逆序对的样子，然后注意到有一个数据点是保证给的是排列，好像可以树状数组维护前后缀的逆序对 + 枚举中间最大值的位置做。
• 写了一下，发现样例都过不去，本来这个错误在写这个做法前通过手玩样例应该就能发现的，这损失了 20 分钟，目前已经快 4 点 50 了。
• 接着，发现好像最暴力的分会做了，只需要枚举全排列，假如这个排列是我们想要的，就暴力从左到右模拟一下交换过程，看看需要多少次。
• 花了 15 分钟左右写了一下这个做法，测了几个样例都过了，然后我又自己造样例，发现单调递增和递减的情况算错了，把 bug 修复了一下。
• 这时已经 5 点 20 了，我感觉我也没有别的分数可以做了，于是检查了一下文件读写、MLE、RE、溢出之类的问题，检查了一下提交的目录结构，压缩之后 5 点半直接提交了，相当于提前半小时交卷，我实在是没可以写的分数了。
• 赛后评测，发现 T1 居然拿了 96 分，$n = 500$ 的 $O(n^3\log n)$ 本来不应该过的，结果或许是数据太水了导致过了好多点，后边 T3 有人注意到可能无解，直接输出无解居然拿了 40 分的高昂分数，比我写暴力 20 分强多了，这模拟赛真挺模拟的，连题目数据水了都模拟到了。最后我总分 156 分，大概排前十名（共 30 多人），我觉得还是挺不错的，毕竟理论上预期得分应该是 100 分。
• 出题人评难度为绿绿蓝紫，体感上我是赞同的，如果不能切绿的话很可能 4 个题加起来拿不了 100 分，就很惨了。

讲题

题解与标程

T1

首先注意到按照 d[u] + d[v] 从大到小贪心去连边，这个是显然的。

如果暴力维护连了 (u, v) 之后其他边的度数之和，则需要 $O(n)$ 的时间，由于我们要处理 $O(n^2)$ 条边，外面还有一个二分答案，所以总的复杂度就是 $O(n^3 \log n)$ 了，这也是我赛时的做法。

$n = 500$ 时，上述做法到底能过多少取决于数据强度，以及可能需要一点点卡常。在民间测试我过了 96 分，在官方评测机上跑了 100 分，可能有一些运气的成分。

如果要稳稳地通过，复杂度至少要降到 $O(n^3)$，赛时我甚至认为要降到 $O(n^2 \log^2n)$，因为我一直认为二分答案是不可缺少的。

这时，我们去想，反正已经确定了每次找最大的 d[u] + d[v] 去连边，那不妨我们就先不管 k 到底是多少了，我们每次枚举到最大的 d[u] + d[v]，就连边，并且把相关的其他边的度数之和给更新了，本质上我们要处理 $O(n^3)$ 条边。

假如我们能按照 d[u] + d[v] 递减的顺序去遍历就好了，于是我们考虑用 2n 个桶，把 (u, v) 加到 d[u] + d[v] 这个桶里，每次遇到一条边处理完就加边，一直不回头地遍历，就能 $O(n^3)$ 处理完了。

T2

这个题的一个关键切入点在于，意识到排序时邻项交换次数和逆序对关系非常密切，所以应该想到这个题目可能要从逆序对的角度入手。这个点我考场上想到了。

第二个关键的观察，在于考虑一个先增后减的数组是怎么来的。考虑原数组排好序，从小到大，依次看每个数放到另一个初始为空的序列的左边还是右边，这样最后放出来一定是一个先增后减的序列。

有了第二个观察，我们考虑每个数如何选择往左还是往右放。为了方便，我们先假设无重复元素。我们考虑某个数 val，考虑其在原序列中出现的位置，我们考虑为了调整 val，需要交换多少次，为了交换计数不重不漏，我们把一次交换贡献在较小的数头上。

有了这样的约定，考虑 val 要交换多少次，假如要放到左边，则原序列中在 val 左边的比 val 大的数字必须得交换，所以 val 头上的贡献就是左边因为 val 产生的逆序对数。如果要放到右边，则原序列中在 val 右边且比 val 大的数字必须得交换，这样就是右边数组因为 val 产生的顺序对数。这样每个数只需要关心自己放左边还是右边就好了，交换次数只记自己小的时候的。

接下来考虑有重复元素怎么搞，我们注意到重复元素是不应该交换的，所以本身并不产生贡献，做法和上面完全一样。

T3

假如我们是已知 a 然后求 p，怎么做？很简单，直接对 a 建一个 01trie，然后枚举 i 从 [0, 2^m - 1] 贪心就好了。

由于我们枚举的是 [0, 2^m - 1] 中所有数，且 a[i] 也是 [0, 2^m - 1] 内的数，所以我们会把所有 a[i] 都遍历到的。所以如果是已知 p 求 a，但 p 中并没有出现 [1, n] 里每个数，那么说明给的 p 是不合法的。

进一步考虑，我们发现 [0, 2^m - 1] 的左半边的最高位是 1，右半边的最高位是 0，假如 a 的 trie 中这一位有 1 也有 0，则左半边的数和右半边的数走的一定是 trie 上不同的分叉，且左半边内部的所有数在 trie 上走这一步一定是走的同一个分叉，右半边也是一样的。

这意味着我们可以考虑用下面的做法去求解 [0, 2^m - 1] 对应多少种 a 序列：

• 考虑 p[0, 2^(m - 1) - 1] 和 p[2^(m - 1), 2^m - 1] ，假如对所有的 p[i]，有 p[i] = p[i + 2^(m - 1)]，则说明 a[p[0, 2^m - 1]] 在这一位只有 0 或者只有 1，所以左右两边的方案数应该是一样多的，我们只算一边然后乘 2 就好了。
• 假如存在 p[i]，使得 p[i] != p[i + 2^(m - 1)]，则 a 的这一位既有 0 也有 1，则肯定是左半边为 1，右半边为 0，这时就要分别递归下去求解。注意，假如左边某个 p[i] 等于右边某个 p[j]，这肯定是矛盾的，无解。

T4

太超模了，500 的部分分就得用 AC 自动机搞了，不是考场上能做的题，拿 5 分就是考场上尽力能做到的最好的结果。

经验教训

• 站在出题人的角度，如果觉得一个题目的数据不好造，那么一定要大胆猜测数据造得比较弱，可以骗分，比如直接输出无解，或用复杂度不是最优的做法卡卡常，能多拿很多分。另外，如果觉得一个题的复杂度不太好分析，那么大胆猜测出题人也卡不满。
• 有同学提交代码时压缩文件结果是空的，没有检查文件字节数就交了，导致 0 分，这告诉我们检查字节数是很重要的。
• 好多同学在赛后讨论时似乎都很厉害，想出了后边 3 题的更高档暴力，但是可能是因为测试不足，导致一大片一大片的挂分，而我一分都没有挂，预期内的分数全部拿到了，这可能和我对拍以及测试有关系，我应该后续备赛时继续延续这一点。