A

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

B

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

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

所以 $y$ 其实只能取形如 $9,99,999,\ldots$ 这样的数,设 $ \leq B$ 这样的数有 $c$ 个,答案就是 $A \times 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

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

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

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

Last modification:September 17th, 2020 at 08:12 am
如果觉得我的文章对你有用,请随意赞赏