ARC099

发布时间 2023-10-26 19:34:26作者: Skylakes

shaber round。

A

显然都会变成 1。枚举穿过 1 的那次操作在哪,剩下两边的答案直接算出来就行。

B

不会。

C

完全子图 的判定,直接考虑建立补图。那么补图一定是一张二分图。染色判定。

如果我们划分为了 \(n=x+y\) 两个大小的完全子图那么答案就是 \(\frac{x(x-1)+y(y-1)}{2}\),显然我们要让 \(x,y\) 尽量接近。这是一个经典问题。直接 bitset 优化可行性背包即可。时间复杂度 \(\mathcal O(n^2/\omega)\),如果闲得无聊可以用 [BalticOI 2015] Tug of War 的套路做到 \(\mathcal O(n\sqrt n\log n/\omega)\),不过没啥意义。

D

一看就是 hash 啊啊。考虑一开始 \(x=1\)+ 就加上 \(x\)- 就减去 \(x\)>\(x\gets x\times base\)<\(x\gets x/base\),然后整个 hash 就行了。出题人很有素质地卡了单哈希。不懂怎么提高正确率。