Contest Info

date: 2019.01.15 15:10-20:10

practice link

Solutions

A. Access Points

题目大意：平面上有 \(n\) 个整点，要求你给每个整点按照输入顺序各分配一个点（可以不是整点），并且这些点的两维必须分别不降，使得点对之间欧氏距离的平方和最小。

题解：显然两维可以分别计算。

对于某一维，设 \(f_{i}(x)\) 表示第 \(i\) 个点放在 \(x\) 时的最小值，我们维护 \(f'_{i}(x)\)。开始时 \(f'_{1}(x)=2x-2a_{1}\)，但是我们要对 \(f(x)\) 求前缀最小值，因此在 \(f'_{1}(x)\) 等于 \(0\) 之后，即 \(x\ge a_{1}\) 时，有 \(f’_{1}(x)\equiv 0\)。

从 \(i\) 转移到 \(i+1\) 时也类似。我们首先有 \(f'_{i+1}(x)=f'_{i}(x)+2x-2a_{i+1}\)，然后再将大于 \(0\) 的部分置 \(0\)。这里我们只需要记录一个偏移量即可用单调栈维护。

最后求一个积分即可。

时间复杂度 \(\mathcal{O}(n)\)。

coldwater’s comment:

有一个跟今年 CCPC 桂林 A idea接近的做法。重新描述一边题目，我们有 \(a_1,a_2,\dots,a_n\)，需要找一个 \(x_1\leq x_2\leq \dots \leq x_n\)，使得 \(\sum(a_i-x_i)^2\) 最小。

我们一个一个考虑 \(x_i\)。对于 \(x_i\)，我们当然是希望它取 \(a_i\) 最好，如果 \(a_i \geq x_{i-1}\)，那么我们就取 \(a_i\)。否则，\(a_i < x_{i-1}\)，我们先把 \(x_i\) 达到 \(x_{i-1}\)，然后把 \(x_{i-1}\)（可能不止 \(x_{i-1}\)） 往左边“推”一段距离。那么连在一起的这一段 \(x_j,\dots,x_i\) 的取值 \(x\) 应该满足：\(\sum_{k=j}^i(x-a_k)^2\) 最小，那么 \(x=\text{avg}(a_j,\dots,a_i)\)。

注意如果最后两块不满足单调不减的关系，那么要不断合并最后两块。

B. Brexit Negotiations

题目大意：给出一个 DAG，让你对其拓扑排序。每个点有一个 \(e_i\)。设其在拓扑序中的顺序是 \(p_i\)，那么它的代价是 \(p_i - 1 + e_i\)。让你最小化最大的权值。

题解：二分答案。假设答案为 \(m\)，那么每个点的合法区间就是 \(p_i\in [1, m+1-e_i]\)。我们逆拓扑序更新一遍区间右端点，然后再正向扫一遍拓扑排序。每次取出最小的右端点，判断是否合法。二分答案不会改变右端点的偏序关系，所以不用二分，直接扫一遍即可。

另一个做法：

排在最后的节点希望有最小的 \(e_i\)，我们逆拓扑排序，每次取出入度为 \(0\) 的最小的 \(e_i\) 即可。

C. Circuit Board Design

题目大意：要求你在平面上画一棵与输入的树同构的树，使得边不相交，且边的长度为 \(1\)。

题解：首先在原点画根，设当前可行的角度区间为 \([l,r]\)，那么将 \([l,r]\) 按照子树的 size 划分为若干个子区间，在每个区间的角平分线上画对应的儿子。

初始区间要注意小于 \(\pi\)，否则在一条链后接很多结点时会出现问题。

E. Equality Control

题目大意：定义4种 vector 操作：

• \([a_1,\cdots,a_k]\)：初始化一个 vector
• \(\text{sorted}(X)\)：返回\(X\)排序后的 vector
• \(\text{shuffle}(X)\)：等概率随机返回\(X\)的一个排列后的 vector
• \(\text{concat}(X,Y)\)：返回\(X\)和\(Y\)连接后的 vector

给出两个以上四种操作组成的函数，判断对于任意可能的结果 vector，它们是否都有相同的概率得到。

题解：对于 \(\text{shuffle}\) 以外的操作，得到的结果都是固定的。并且在 \(\text{sort}\) 和 \(\text{shuffle}\) 内部的任何操作都是没有意义的。这样可以化简得到固定的结果和被 \(\text{shuffle}\) 的区间。一个被 \(\text{shuffle}\) 的区间，如果只含有一种数，本质上也是固定的，可以去掉 \(\text{shuffle}\) 的影响。否则剩下的 \(\text{shuffle}\) 区间，两个操作函数要等价，必须是这些区间完全相同。因此只需要处理一下输入，将 \(\text{sort}\) 和 \(\text{shuffle}\) 区间内部都排序，连着这个位置的属性（是否固定，属于第几个 \(\text{shuffle}\) 区间）进行比较即可。时间复杂度 \(\mathcal{O}(n\log{n})\)。

F. Fastest Speedrun

题目大意：有一个游戏，有 \(n\le2500\) 个关卡。初始时，玩家只有编号为 \(0\) 的道具，可以按照任意次序挑战这 \(n\) 个关卡，当通过关卡 \(i\) 后就能获得编号为 \(i\) 的道具。玩家的道具不会消耗，如果挑战关卡 \(i\) 的时候持有编号为 \(j\) 的道具，那么用时为 \(a_{i,j}\)，如果持有编号为 \(x_i\) 的道具，那么用时为 \(s_i\)，并且 \(a_{i,0}\ge a_{i,1}\ge\cdots\ge a_{i,n}\ge s_i\)。问最速通关所有关卡需要多少时间。

题解：对每种道具建一个点，建点 \(j\) 到点 \(i\) 的边权为 \(a_{i,j}\) 的有向边（表示用 \(j\) 道具攻关关卡 \(i\)），\(x_i\) 到 \(i\) 的边权为 \(s_i\) 的有向边，则问题转化为求以 \(0\) 为根的最小树形图。

考虑朱刘算法求解，但是常见的实现方法的复杂度是 \(\mathcal{O}(VE)\) 的，这题中 \(\mathcal{O}(E)=\mathcal{O}(n^2)\)，显然是不可接受的。但是我们可以简单地改写算法，做到一般图 \(\mathcal{O}(E\log{E}+V^2)\)，如果像本题中一样输入的边是有序的话，可以省去排序，做到 \(\mathcal{O}(E+V^2)\)。

朱刘算法的一种常见实现方法为：对于根以外的每一个点，选择一条最小的入边，然后检查是否构成了环，如果没有，就求得了答案，否则，将每条边的权值减去其终点的入边的权值，然后将环缩点，不断重复直到没有环存在。因为每次缩点后点数至少减少 \(1\)，所以最多进行 \(V\) 次，每次需要遍历每条边来求最小的入边，以及修改边权，这部分的复杂度为 \(\mathcal{O}(VE)\)，缩环需要的复杂度为 \(\mathcal{O}(V^2)\)，因此总的时间复杂度为 \(\mathcal{O}(V(V+E))\)。如果我一开始将终点相同的边分组排序，由于同一组边每次减去的权值是相同的，它们的偏序不会发生改变，则每次选择时只需要遍历一遍每个点就可以找到最小的入边，如果这个最小入边的起点和终点在当前被缩掉的点集合中，就删掉检查下一个，删除的总复杂度是 \(\mathcal{O}(E)\) 的，因此最终的时间复杂度为 \(\mathcal{O}(E\log{E}+V^2)\)。

G. Game Design

题目大意：让你在一个足够大的棋盘上摆放一些障碍物，且选择一个小球的起点。使得小球按照给定的移动方向序列可以移动到 \((0,0)\) 的洞口处。小球朝一个方向运动直到碰到障碍物位置。小球落入洞口之后不可以移动，不可以呆在原地不动。

题解：每次移动的步长乘 \(2\)，如果该方向有障碍物，那么不新增障碍物而是直接移动到该处。最后判断一下洞口是不是在一个之前经过的位置。

另一个做法：

一开始考虑一个 \(3\times 3\) 的棋盘，小球起点在中间。每次在移动方向和其反向边界外各放一个障碍物。每次运动方向改变 \(90\) 度，就把棋盘每一边扩展两个格子。

H. Hard Drive

签到题。

I. Inflation

签到题。

J. Jinxed Betting

题目大意：一些人在赌博，赌赢了分值会加 \(1\)，赌输了分值不变。现在 Julia 是第一名，她现在每次采取如下策略：选择剩下的人里分值最高的人中的多数意见下注，如果有分值最高的人中两种选择的人数恰好相等，那么她会随机选一种下注。现在问最坏情况下，她至少能保持第一名多少轮。

题解：显然每次最坏情况是：设有 \(x\) 个人分值最高，Julia 和 \(\lceil\frac{x}{2}\rceil\) 个人一起赌输，剩下的人赌赢。我们把所有人的分值一起减 \(1\)，每次的结果就变为：Julia 和 \(\lceil\frac{x}{2}\rceil\) 个人一起扣 \(1\) 分，其他人不变。

\(x\) 个人分值最高时需要多少轮使得所有人分值减一可以很容易地预处理。之后我们对于每个 \(i\in[2,n]\)（Julia 是第一个人），计算第 \(2\) 到 \(i\) 个人的分值都变为第 \(i\) 个人的分值时，Julia 是否还是第一，这样我们可以知道 Julia 是在哪个区间失去第一的。之后在这个小区间二分即可。

K. Kleptography

签到题。