Codeforces Round #626 部分题解

2023-11-09 17:27:34

A,B

咕了

不会做C，身败名裂……

考虑右边的点，如果一些点连的左边的集合相同，那么可以把他们缩在一起。然后我们再把空集删掉。

此时就有答案是所有点的\(\gcd\)。

证明：反证法。先全部除掉一个\(\gcd\)。设\(g\)为可以乘到答案上的一个数。如果\(sum\)不是\(g\)的倍数，那么全集不合法。否则，拿出不是\(g\)的倍数的一个点，如果有多个选对应集合最小的那个。此时，只要我们选他对应集合的补集就可以卡掉。

分不清any和every，身败名裂……

显然可以把计算答案看做一个二进制进位的东西。显然就是从后往前选怒气值单调不降的一个序列。

显然可以设\(dp_{i,j,k}\)表示考虑了后\(i\)个，目前考虑到的最高位是\(2^j\)，这一位有\(k\)个进位，的最大答案，随便转移。由于一个点对后两维的贡献是\(1+\frac 1 2+\frac 1 4+\cdots\)，显然这个状态是\(O(n^2)\)的。

显然做完了。显然代码咕了。

考虑01序列怎么做。容易发现只需要对每一个01交错的段分类讨论一下就行了。

那么我们从小到大枚举\(x\)，把\(\leq x\)的置为0，把\(>x\)的置为1，算出最后序列的样子。当一个位置在\(x-1\)和\(x\)的最终状态不同时，他的最终答案就是\(x\)。

感性理解一下，操作次数就是每个\(x\)对应的01序列的操作次数的最大值。

然后就是要维护这个01序列了。可以拿set维护01交错段，拿堆维护最长段的长度，然后使劲分类讨论。

咕了。