Contest Info

practice link

Solutions

A. Two Squares

题目大意：给你两个正方形，其中一个与坐标轴平行，另一个与坐标轴成 \(45^{\circ}\) 角，判断它们是否相交。

题解：将与坐标轴成 \(45^{\circ}\) 角的正方形扩充到与坐标轴平行，若不相交，则原来的两个正方形也不相交；否则将平面旋转 \(45^{\circ}\)，再进行一次同样的判定，若不相交，则原来的两个正方形也不相交，否则此时一定相交。

另一个事实是，两正方形相交，等价于存在一个正方形的一个角或者中心点在另一个正方形内部。判断一个点是否在与坐标轴平行的正方形内是很好做的。

B. Open Communication

签到题。

C. Careful Maneuvering

题目大意：在直线 \(x=-100\) 上有 \(n\) 艘敌方飞船，\(x=100\) 上有 \(m\) 艘敌方飞船。现在你可以在 \(x=0\) 上任意放置两艘己方飞船，所有敌方飞船会同时向两艘己方飞船各射出一道直线激光，激光会直接射向对面的敌方飞船。最多能摧毁几艘敌方飞船？

题解：显然能够摧毁的位置只有 \(nm\) 条线段的中点，对于每个中点我们暴力 \(\mathcal{O}(n+m)\) 地处理出己方飞船放在该点能摧毁的敌方飞船，用 bitset 维护，之后再 \(\mathcal{O}(n^{2}m^{2})\) 地暴力枚举放置在哪两个位置即可。注意只能放在一个位置的情况。

D. Compute Power

题目大意：给出 \(n\) 个任务，每个任务有两种代价 \(a_{i},b_{i}\)，现在需要把这些任务分给若干台电脑，每台电脑至多分配两个任务，若有两个任务，第一个任务的 \(a\) 必须严格大于第二个任务的 \(a\)。最小化所有电脑的第一个任务的 \(\frac{\sum a}{\sum b}\) ，答案乘以 \(1000\) 后向上取整。

题解：首先将所有的 \(a\) 乘上 \(1000\)，之后二分答案。设 \(c_{i}=a_{i}-\text{mid}\cdot b_{i}\)，问题转化为验证是否能够找出一些任务作为第一个任务，且它们的 \(\sum c\le0\)。

考虑将所有任务以 \(a\) 为第一关键字，\(c\) 为第二关键字排序，按照 \(a\) 相同大小分组背包 \(\text{dp}\)。

设 \(\text{dp}[i][j]\) 表示当前正在处理第 \(i\) 个组，有 \(j\) 个未被分配第一任务的第二任务。

设该组的个数为 \(\text{cnt}\)，转移时我们枚举该组有 \(k\) 个任务作为第一任务，显然我们应取 \(c\) 最小的 \(k\) 个，这些第一任务应当分配给之前剩余的第二任务；剩余的 \(\text{cnt}-k\) 则作为第二任务留待之后分配，即我们应该转移到 \(\text{dp}[i+1][\max\{j-k,0\}+\text{cnt}-k]\)，最后 \(\sum c\) 的最优值即为 \(\text{dp}[组数 + 1][0]\)。

E. Nikita and Order Statistics

签到题。\(FFT\)。