2015-2016 Petrozavodsk Winter Training Camp, SPb SU + SPb AU Contest

Problem B

Upsolved by kblack. (-2)

题意：给出平面上 $N$ 个点，他们相互连接的 $\binom{N}{2}$ 条线段与 $x$ 轴夹角的中位数。

题解：我们需要知道中位的一个或两个线段的夹角，考虑二分答案，问题转化为求夹角小于 $\theta$ 的线段的数量。如图，我们从右往左枚举点，并计算处于某个点 $A$ 区域的点数，计算方式是用 $l_1$ 右侧（枚举顺序）和 $l_2$ 下侧（排序）夹出 $B+C$，同理用 $l_1$ 右侧和 $l_3$ （顺时针旋转 $\theta$ 后排序）下侧夹出 $A+B+C$，树状数组维护一下，减一下就得到了 $A$ 区域的点数。这个方法只作用 $0 \leq \theta \leq \frac{\pi}{2}$，如果线段数不够，我们可以直接将整个平面顺时针旋转 $\frac{\pi}{2}$，特别注意与坐标轴平行的线段的计算。

Problem C

Unsolved. (-2)

Problem D

Solved by kblack. (+2)

题意：一堆物品，对于先手的价值是 $a_i$，对于后手的价值是 $b_i$，先手贪心，求后手最大保证获益。

题解：我们先将物品按 $(b_i, a_i)$ 排序，问题转化为前 $i$ 个物品中我们最多抢到 $\lfloor \frac{i}{2} \rfloor$ 个物品。我们贪心的选取物品，对于大于 $1$ 的奇数位的物品，如果他比我们之前选的某个物品价值更大，我们就可以放弃之前的物品选他，对于偶数位置的物品，由于正好多一个可以选的物品，直接选择，对于已经选择的物品维护一个 multiset 即可。

Problem F

Solved by ultmaster. 01:10 (+2)

Problem I

Unsolved. (-3)

Problem J

Solved by ultmaster. 03:13 (+)

Problem K

Solved by zerol. 01:39 (+)

题意：$f(l, r) = r - l + 1 - \max\{l, |S|-r-1\}$，问对于在 T 中出现过的 S 的子串，哪一个 f 的值最大。

题解：发现对于函数 f，如果子串 s 在 T 中出现过，那么选 s 的子串肯定不会更好。对 T 建后缀自动机，S 在转移边上跑，得到每个前缀能匹配的最长后缀，计算 f 即可。