CF 1288 题解

A

(x) 取在 (sqrt d) 附近,枚举一下就行了。

B

对于任意一个二元组 ((x,y)),设 (y) 的位数为 (t),那么合法的 (x) 当且仅当满足 (xy+x+y = x imes 10^t + y)

化简一下可以得到 (y = 10^t - 1)。而发现这个式子对 (x) 是没限制的,也就是说如果 (y) 合法那么 (x) 可以任意选。

所以 (y) 其实只能取形如 (9,99,999,ldots) 这样的数,设 $ leq B$ 这样的数有 (c) 个,答案就是 (A imes c)

时间复杂度 (O(T log B))

C

只需要保证 (a_n leq b_n) 就好了,于是枚举 (a_n,b_n) 剩下的就是个组合数。

D

最小值最大,考虑二分答案,将 (geq k) 的位置设置为 (1),否则设置为 (0)

现在问你是否有两行满足它们按位或是全集。

(m leq 8) 可以开个桶+高维前缀和直接做(其实直接 (3^n) 子集和也没事)

E

最靠上的位置:如果发过消息,那么一定是 (1),否则只会一直往下顺延,最靠上的位置就是最初的位置。

最靠下的位置:考虑按照这个数的出现次数分段,答案是每一段去重后的数的个数。在第一次发消息之前的答案是区间内出现了几个比它大的数。区间颜色数,经典主席树操作。

官方解法是在前面添加 (m) 个虚点用来存放移动过去的东西,当前这个数的排名就是前缀 (1) 的个数,每次移动相当于对应区间加减,发现每次最大值更新只会在移动这个点之前达到最大,直接维护就可以了。

F

神奇的网络流,没见过的模型。。

网络流模型大多数都是考虑流量平衡或者增广路的意义。

这个题我们考虑流量平衡:如果这条边选择红色就从左往右流,选择蓝色就从右往左流。那么一个点的颜色就可以用入流和出流的差来刻画了,直接写一个上下界费用流即可。

原文地址:https://www.cnblogs.com/rainair/p/14305873.html