2018-2019 ICPC Northwestern European 区域赛

rank solved A B C D E F G H I J K
115 6 Ø O Ø Ø O . O O O Ø O

A

UpSolved by XLor.

注意到两维独立,问题转化为给定 $y_1, y_2, \dots, y_n$,构造 $x_1 \le x_2 \le \dots \le x_n$,最小化 $\sum_{i=1}^n (x_i-y_i)^2$。

函数 $f(x)=\sum_{i=1}^n (x-a_i)^2$ 的最小值,在 $x=\frac{\sum_{i=1}^n a_i}{n}$ 处取到。

我们没加入一个新的目标点 $a_i$,显然其最值在 $a_i$ 处取到,若其在前一次的点的右侧,那么没有问题。否则,应该将两个二次函数的最值点合并,即合并二次函数个数和 $a_i$ 之和。于是,我们得到了一系列点,根据此计算出最小值。

B

Solved by miaojie (01:31).

C

UpSolved by miaojie.

将角度分成 $n-1$ 份即可,按照类似于 $(dep(i), dfn(i))$ 的方式构造。

赛中的方案,如果非二度结点的层数过多,导致分母过大,两个点重合。

D

UpSolved by XLor.

给定一个有向带权图,一个人从起点开始等待一段时间后出发,在图上随意游走,当时间处于 $[A,B]$ 中的任意一个时刻,终点发出信号,他会立马(若他正在边上,则会在到达后出发)沿着最短路走到终点,求这个最短路的最大值。

显然,答案必定不大于最短路,因为可以一直在起点等待,发出信号才开始出发。

二分答案,令终点等待的时间为 $\delta < d(S,T)$。

我们考虑终点前的一个点 $x$,若 $d(S,x)+d(x,T)>A+\delta$,那么走到 $x$ 点必然无用,其实从一开始就走,在 $d(S,x)$ 收到信号,他也不能在 $A+\delta$ 时刻到达。因此,我们令满足 $d(S,x)+d(x,T) \le A+\delta$ 的点 $x$ 为好点。然后,若我们从好点出发走一条长度为 $l$ 的边,走到 $v$ 点,满足 $l+d(v,T)$ 不超过 $\delta$,也就是我们可以从好点出发走一条边来消磨时间。

根据上述过程,扣出一个子图,若子图中有环,那么可以一直在环上消磨时间,直到信号发出。

或者图是一个 DAG,我们希望尽量在起点多等一会,使得在 $[A,B]$ 这个时间段内,都能响应信号的发出。

一开始,每个点的最晚到达时间是 $A+\delta-dis(x,T)$,然后考虑在边上走消磨得时间,也就是在拓扑序上 DP 出每个点的最晚到达时间,若其不小于 $B$,则合法。

E

Solved by XLor (02:13, +4).

注意到,要么 Shuffle 单一元素,要么必须 Shuffle 的方式完全相同,才可能等价。

使用递归下降分析器,构造出语法树,然后将语法树等价于一堆的 ListSortedShuffle 拼接在一起,将序列打平后,判断是否完全相同。

G

Solved by miaojie (04:24, +6).

从原点开始,螺旋构造,注意避免不同层之前产生冲突。

H

Solved by miaojie (00:27).

I

Solved by miaojie (00:11).

J

UpSolved by XLor.

题意是,给定一个数 $x$ 和一个长度为 $n-1$ 的数组,数组所有数不大于 $x$,每次选择数组中最大数的一半(上取整),其他位置均 $+1$,求多长时间后最大值大于 $x$。

观察这个过程,可以发现如果当前最大值有 $y$ 个,那么连续操作 $\log_2(k)$ 次,每次最大值 $+1$,此时只剩一个最大值,再操作一次,最大值匀平,且次大值和最大值的差距缩小 $1$。

因此,维护最大值的合并过程即可。

K

Solved by XLor (00:25).