2018-2019 ICPC, NWERC

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

Records

[Contest]

Solutions

A

横纵坐标独立,我们做两遍.

问题等价于要求$$a_1 \leq a_2 \leq \cdots \leq a_n$$,最小化$$\sum_{i=1}^n (a_i - x_i)^ 2$$.

显然应该把$$x_i$$分成若干段,每一段的$$a_i$$都取一样的值,为$$x_i$$的平均值.

我们用一个栈记录这些段,如果合并更优,就合并,即可.

B

很有趣的题目,显然答案具有二分性质,我们假设先二分答案.

那么我们就知道了DAG上每个点最晚应该出现的位置,我们反向DP这个DAG.

具体形式为DP出每个点最晚放置的位置,如果该点有后继,那么需要考虑每个后继的顺序,即最晚放置位置越晚的点越靠后,然后做DAG上的DP更新.

更新完毕之后我们会发现,对于一个点,其后继摆放的顺序是固定的.

进一步地,所有点摆放的最优顺序都是固定的,因此我们甚至可以不需要二分.

模拟一遍放置的过程后,从前向后扫一遍即可得出答案.

C

把$$1$$号点放在原点

把角度按子树size划分开来,递归下去即可

D

我们先跑正反两遍最短路,然后二分答案$$k$$,下面判定$$k$$是否可行.

考虑妹子在$$A$$时刻就叫人的情况,那么我们$$d(1, u) + d(u, n) > A + k$$的点都不能去.

此时能去的点,我们记最晚时刻为$$A + k - d(u, n)$$,因为你可以在家等一会再走(一开始忘了这个直接错飞了).

接下来我们考虑哪些边是能走的,对于一个能走的点$$u$$的出边$$(u, v, w)$$,如果有$$w + d(to, n) \leq k$$,那么这条边是可行边,同时点$$v$$也是能走的,重复更新.

接下来如果可行边有环,则$$k$$是可行的,否则可行边构成DAG,那么需要让最晚到的某个可行点的到达时间$$\geq B$$.

E

关键操作在于shuffle的suiji随机排列

而正确做法是将其转化为确定排列,即对于每一次的shuffle操作,我们都把它当成升序排列操作,最终得到的两个序列如果不相等则显然not equal

如果相等就再把所有shuffle当成降序操作跑一遍,如果还相等则equal

F

显然是个最小树形图,套$$O(V^2)$$的模板就能过

$$O(V^2)$$做法:考虑枚举每一个点,如果这个点和根不相连,那么就想办法打通一条到根的路径

对于每个点集,用暴力堆维护其他点到这个点集的最小距离

然后每次找最小入边,沿着最小入边跑,其他入边减去这个权值(可以用一个tag维护)

然后遇到环就缩起来,当然要merge这些堆

直到找到根为止,merge这些点集即可

如果要$$O(V+ElogV)$$的做法,就把这个暴力堆换成可并堆

G

考虑边界范围,每次转弯90°时就将边界扩大一倍(*2),然后在边界对应位置上放障碍

从(0,0)出发,最后输出答案时做一下偏移即可

H

$$c$$为奇数的话$$1$$号点为$$1$$,否则为$$0$$

后面贪心构造就行了

I

签到题

J

我们考虑将除了主人公以外的其他人按分数分段.

观察到假设目前最高分的有$$k$$人,那么经过$$\lfloor \log k \rfloor + 1$$轮之后,每个人的分数都涨了$$\lfloor \log k \rfloor$$分.

其中分数最高的人在最后一轮不涨分,其余人分别在某一轮没有涨分.

因此我们可以利用$$O(\log)$$的时间求出$$\log k$$之后,直接计算模拟这个过程,然后合并两段分数不同的人.

总复杂度$$O(n \log)$$

K

签到题,算算编码即可.