Contest Info

date: 2017.10.08 13:00-18:00

practice link

Solutions

A. Assigning Workstations

题目大意 ：有 \(n\) 个使用电脑的需求，每个需求是一个区间。如果一台电脑超过 \(m\) 时间没人使用，就会关闭。有无数台电脑，问最少开多少次机。

题解 ：对需求排序之后贪心即可。

B. Better Productivity

题目大意： 给你 \(n\) 个区间，要求将他们分为 \(p\) 个非空子集，使得每个集合内的区间交不为空，并且这些区间交的和尽可能大。

题解 ：我们将区间分为两类：第一类是不包含任何区间的区间，第二类就是包含了至少一个区间的区间。我们分别称它们为小区间和大区间，设它们分别有 \(A,B\) 个。

单独考虑小区间，我们先将它们排序，那么在同一个集合中的区间，一定是连续的一段。很容易写出 dp 方程。我们设 \(dp[i][j]\) 表示前 \(i\) 个小区间分成 \(j\) 个子集的最大价值。可以 \(\mathcal{O}(n^2p)\) 得到（可以用线段树优化到 \(\mathcal{O}(np\log n)\) ）。

再考虑大区间。对于一个大区间来说，它有两种决策。第一个是将其和它包含的子区间分在同一个集合中，这样不会对答案产生影响。第二个是单独作为一个集合的唯一元素。于是我们把大区间按照区间长度从大到小排序，然后枚举前 \(i\) 个大区间使用第二个决策，剩下的大区间使用第一个决策，那么答案为 \(dp[A][p-i]+\sum_{j=1}^{i}\text{len}_j\) 。从这个式子中，我们可以看到：多个大区间放在一个集合一定不会更优。

C. Cleaning Pipes

题目大意 ：有 \(w\) 道水渠以及 \(p\) 根水管，水渠是二维平面上的点，水管的一端为一个水渠，另一端为平面上的点。保证水管在除了水渠以外的交点，最多只有两根水管相交。现在要清理这些交点，同一个交点的两根水管，只能选择一根放置机器人。现在问你是否可以一次性选择一些水管放置机器人，使得所有的交点都被清理。

题解 ：先处理线段相交，然后相交的两个水管，有且仅有一个需要放置机器人。我们转成二分图染色就可以了。注意处理线段相交的时候，不能简单地把平行给判掉。两根平行的水管可以在除了水渠的另一端相交。

D. Debugging

题目大意：一个 \(n\) 行的代码中有一个 bug ，你可以在它们中间插入一些 printf 并运行代码来判断 bug 出现的位置。插入一个 printf 需要 \(p\) 的时间，运行一次需要 \(r\) 的时间。问最坏情况下具体找到 bug 在哪一行至少需要多少时间。

题解： dp 。设 ​\(dp(i)\) 表示 ​\(i\) 行代码的答案，则 ​\(dp(i)=\min\limits_{2\le j \le i}\big(dp(\lceil\frac{i}{j}\rceil)+(j-1)\cdot p+r\big)\) 。由于本题只要求 ​\(dp(n)\) 的答案，所以可以使用记忆化搜索来降低复杂度。使用类似杜教筛的方法（只对相同的 \(\lceil\frac{i}{j}\rceil\) 中最小的 \(j\) 计算）可以进一步降低复杂度，打表可知复杂度低于 \(\mathcal{O}(n)\) 。

E. Elementary Math

题目大意 ：给出 \(n\) 个表达式 \(a\text{ op } b=c\) 的 \(a,b\) ，要求你给每个式子的 \(\text{op}\) 分配 \(+,-,\times\) 中的一个，使得这 \(n\) 个表达式的 \(c\) 互不相同。

题解 ：将表达式和所有可能的取值建二分图，求最大匹配即可。

F. Flight Plan Evaluation

题目大意：在一个球面上有一些简单多边形，现在给出球面上的一条折线段，问它不在这些多边形中的部分占比多少。保证所有的简单多边形之间严格不相交，保证折线段的所有顶点与多边形的边有一段距离，保证多边形的所有顶点和折线段的边有一段距离，保证折线段开始和结束的顶点在某一个多边形内（但不一定是同一个）。

题解：这个算是一道 old 题的球面几何版。由于题目的保证排除掉了各种特殊情况，因此折线段只要和多边形的边交一次，它在多边形内/外的情况就一定会改变，于是主要的问题就变成了求球面上两条线段的交。这个也非常简单，只需要把这两条线段所在的（欧式空间的）平面的交线求出来，交线与球的交点就是可能的两个交点。然后再判断这两个交点是否在线段上就好了。

G. Guessing Camels

题目大意 ：陌上花开。三维偏序。

题解 ：cdq分治 + 扫描线 + 树状数组。

H. Hole in One

题目大意：一个高尔夫球场上有一些水平或者竖直的墙，球只要撞到它就会被反弹（按照反射定律），并且墙会消失。现在从原点往某个方向打出一颗高尔夫球，问它在进洞前最多能撞碎多少堵墙。允许中间经过洞而不进入洞。

题解：由于墙的数量很少，我们可以枚举所有撞墙的顺序然后验证是否合法。打出去的方向用反射定律对称一下随便搞搞就好了。

I. Identifying Map Tiles

签到题

J. Jumbled Communication

签到题

K. Kitchen Combinatorics

签到题