2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

签到, 记录每个位置是谁, 以及谁在哪个位置, 单次修改$$O(1)$$

B

将所有的队伍按人数排序

枚举轮数, 那么就是一个前缀两两配对, 一个后缀一队一轮, $$O(k^2)$$计算即可.

C

考虑扫描线,然后把价值加在左端点上

要维护的式子变成了$$\sum{p_i}+k*l -k*r-k$$

把$$k*l$$挂在左端点上就可以线段树维护了

D

E

考虑每个将每个串看成一个点, 黑白色分别表示是否翻转.

两个点之间可能有两种约束

  • 必须同色
  • 必须异色

那么对于每个连通块, 只需要枚举一个点的颜色就能染色了, 最后更新答案即可.

F

面积给定的矩形长宽最接近的时候周长最小

G

考虑最后一次拍在什么时候

我们之前可以贪心做,快挂的时候拍一下

然后枚举最后一次拍不拍,二分朝后延伸的区间端点

如果形成一个区间就合法

各种情况判一判

H

对于非$$0$$字符, 那么不能构成的数是$$C_i + 1$$个$$i$$

对于含$$0$$的字符串, 只需要一个存在非$$0$$字符搭配上$$C_0 + 1$$个$$0$$

以上这些数字取个最小值即可

I

这题有意思的地方在于,人数多的应该排在前面.

所以直接从$$1$$个数开始扩展的方案是不行的.

我们换个角度考虑,枚举人数,那么就解决了人数多少的问题.

现在我们应该考虑相同人数的所有方案,怎么按权值和从小到大扩展.

首先对所有人排序,然后我们记录以下几个内容 :

  • 当前的权值和,用来做优先队列的关键字
  • 当前集合的人数,其实可以不记,因为都是一样的
  • 当前的指针,意思之后解释
  • 当前指针所指的人的位置
  • 当前指针所指的人的上界位置

考虑当前的方案,我们要么让当前指针的人下标$$+1$$,要么将指针前移一位,即固定当前人不动,将要动的人调整为他之前的那个

所有的扩展过程中,指针单调不增,观察发现可以不重不漏地遍历所有方案

J

考虑二分这个答案

然后贪心选取前面的就好了

K

L

二分答案, 然后进行一些简单判断即可.

M

zscoder属实构造鬼才= =

问题等价于覆盖的点不能出现$$(x, x), (x, x + 1)$$

一个很容易想到的point在于,如果两个数不同,那么他们必存在某一二进制位不同.

依据这个思路,我们可以让$$x$$的某一位为$$p$$,然后$$y, y + 1$$的对应为都为$$1 - p$$.

这样会使用掉$$2\log n$$次操作.

但是这样会漏掉一些情况,观察发现我们会在$$y$$的二进制表示为$$\cdots 011\cdots 11$$的时候忽略掉一些,就是$$y$$的二进制表示存在一个后缀为$$0$$开头然后全$$1$$,我们构造这些情况,然后让所有能覆盖的$$x$$都覆盖它们即可.

总共需要耗费$$3\log n$$次操作.

N

对于一个连通块, 只要找一条非割边, 或者一个端点度数为$$1$$的边

然后将其度数为$$1$$的端点或者非割边的一个端点记作移动点, 该边的另一端点记作接受点

对于一系列的连通块, 只需要后一个的移动点接到前一个的接受点即可