我又来写游记了哈哈。 ## 入门组 今年的入门组格外简单。 进到机房，发现系统又返祖了，居然直接用上了 Windows 7 系统，去年还是 Windows 10 的（同样的金盆岭考场）。Dev-C++ 也没有中文，这倒不影响。Edge 没有了，不能冲浪了。 同样等了五分钟才下发解压密码。第一题，把所有的数字挑出来从大到小 #排序 就行了，无须特判因为保证至少有一个 $1\sim 9$ 的数字。最后我生怕 $10^6$ 的 $\mathcal O(n\log_2 n)$ 能 TLE，改成了桶排。 然后看 T2，好家伙，这是来搞笑的吗？比第一题还简单，数据范围也小得可怜，只有 $10$。直接拿去循环 #模拟 就行了，判判奇偶就做完了。大前年还是数学+二分，前年单调栈，怎么今年和去年 T2 就这么简单了？€€￡ 是不是想吸引更多人来报名 to CC /se/se。 接着再看 T3，我去，上难度了，高贵的区间异或，这怎么求最大值？想了下发现就是 ZRR #贪心 ，每次选择最大的下标配对即可，最开始写 `map`，后面又生怕 T 了改成数组 $\mathcal O(n)$。 最后看 T4，还是要点脑子的。首先 $2\max<\sum$ 可以拆成 $\max<\sum\limits_{其他部分}$，那么我们只需要先排个小序，这样往后枚举 $i$ 规定只能选 $i$ 即 $i$ 前面的（其中必须选 $i$），那么 $a_i$ 就是最大的了。 我们做个 $0/1$ #背包dp ，$dp_i$ 表示其他部分和为 $i$ 的方案数，这样就可以把大于 $a_i$（即 $\max$）的其他部分方案数求出。$n$ 和值域同阶，这样做就是 $\mathcal O\left(n^3\right)$ 的，当然过不了。 考虑优化，大于 $\max$ 做 #容斥 ，变成用总方案减去小于等于 $\max$ 的，这样背包就只用做 $\mathcal O(V)$ 了。时间复杂度 $\mathcal O(n^2)$。 我就这样不明不白地 AK 了。此时过去不到一个小时，我又睡了将近两个小时，起来玩小恐龙和华容道一个小时，最后就结束了。 最后也是如愿 AK J 组，不过这含金量也太低了。 ## 提高组 下午提高组还是有一丢丢强度的，比去年最简单场难一点，但比前年简单。 T1 还是有点实力的，一眼反悔 #贪心 。二十分钟写、调完代码，比较简单。正要开文件测大样例，不小心新建文件 `club.in` 自动补充成 `club.cpp`，还问我覆不覆盖。我不小心点了覆盖，此时编辑器当中我的代码仍在，结果我想确认是否真的没被覆盖则关闭编辑器，甚至未想拷贝代码至剪切板，就这样我的代码对我不辞而别了，只剩空空的文件。 我顿时骂出了可爱 ZRR，并愤慨地重写了代码，一遍过了所有大样例。然后我思考是否有连锁反悔的可能，发现没有，于是惊险地结束了 T1 的编写。 然后是 T2，一眼最小生成树，但是这 $k$ 个新加的城市就很烦，不管怎样我都始终无法把它们与正常的边相提并论。注意到 $n$ 很小，所以我顿时转变思路，考虑枚举 $2^k$ 种选择新城市的情况。 - [n] 这里均将 #并查集 操作视作常数级别。 这样新的边有 $m+nk=\mathcal O(m)$ 条。但是由于 $m$ 高达 $10^6$，$\mathcal O\left(2^k\times m\log_2 m\right)$ 的时间复杂度显然不现实。事实上，最初的 $m$ 条边当中只有 $n-1$ 条存在于原图最小生成树中的边有竞争力，其余边均不会考虑。 所以先在原图当中跑一遍最小生成树，这样子就只剩了 $n-1+nk=\mathcal O(nk)$ 条边。但是，单次 ${} \mathcal O\left(nk\log_2 (nk)\right)$ 的代价还是有些许高。 考虑预先对这 $k$ 个可能加入的边集进行排序，做多路归并。这样子就变成了 $\mathcal O(nk^2)$ 单次。网上传闻这其实是单次 $\mathcal O(nk)$ 的，因为一共是 $\mathcal O(nk)$ 条边，每条边只会访问一次。我不同意这个说法，或许是我的实现所致。每次我欲加新边时会先将所有已经联通的边的指针后移，接着取最小。这样对于 $\mathcal O(nk)$ 条边，每条边都是 $\mathcal O(k)$ 的复杂度加入，是 $\mathcal O(nk^2)$ 的。 不管怎么说，为了确保常数，我还为并查集加入了 #启发式合并 。 - 赛后我的多路归并确实获得了满分，但是 LRH 只有 $80$（TLE）。 - 我曾与她讨论，她是做 $k$ 次二路归并，每次将新的序列归并到之前的所有序列当中。 - 这种归并的时间复杂度是严格 $\mathcal O(nk^2)$ 的，因为第 $i$ 次归并是归并 $\mathcal O(i\times n)$ 和 $\mathcal O(k)$ 的序列， $\mathcal O\left(\sum\limits_{i=1}^k i\times n\right)=\mathcal O(nk^2)$。 - 而我也渐渐相信了我的算法的确是 $\mathcal O(nk)$ 的。毕竟我的常数比她大得多，寥寥启发式合并不可能做到渐进时间复杂度的超越。 - 事实上，最小生成树只会选取 $n-1$ 条边（这些边是 $\mathcal O(k)$ 选取的），其余的都被 $\mathcal O(1)$ 带过了（因为已联通）。所以复杂度实际上是 $\mathcal O((n-1)k+(nk-n+1))=\mathcal O(nk)$ 的。 真是瞎猫碰上死耗子，算劣自己算法的时间复杂度的也是个尤物了。这也提示我们实现上的小差异可能会造成复杂度的巨大差别。 接着我就去写 T4 暴力了。先写个 $\mathcal O(n!)$ 看看读题是否正确，然后发现可以直接转成 #状压dp 。$20$ 分真香🤪。 最后是 T3。我去，居然考多模式串匹配模板题？！定睛一看，才发现还是需要一些转化的。但是由于我平时根本不练 AC 自动机，赛时竟忘记怎么写了😅。 还得是 #哈希 。模式串按照长度排一排，查询的时候二分剪枝一下，用前缀和哈希匹配。最后也是如愿以偿地获得了 $50$ 分。 赛后一周发现模式串/询问串单个长度和 $L=\cfrac{5\times 10^6}{2}=2.5\times 10^6$，而模式串不同长度的种类数不会超过 $\mathcal O\left(\sqrt L\right)$。所以对于每种长度分别跑线性的哈希暴力匹配，这样子卡卡常直接能靠 €€￡ 新买的 Ultra 9 卡过所有测试点！ 最后 T1 不知哪里写错了 WA 10 分🤡，总分 $90+100+50+20=260$，也是为我必样的 OI 生涯填上了一个金币😍（神秘比喻句）。