首页 > 其他分享 >ARC099

ARC099

时间:2023-10-26 19:33:06浏览次数:35  
标签:hash 子图 补图 ARC099 mathcal omega

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 就行了。出题人很有素质地卡了单哈希。不懂怎么提高正确率。

标签:hash,子图,补图,ARC099,mathcal,omega
From: https://www.cnblogs.com/Royaka/p/17790199.html

相关文章

  • ARC099F题解
    被杀了,记录一下好了。对于他那个数组是否相等,直接判断复杂度很高,考虑通过哈希映射之后判断是否相等。对数组的Hash可以类似字符串Hash那样去做。于是判断一个区间是......