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

Problem A

Upsolved by kblack.

题意：环上 $n$ 个点，要求造 $k$ 个集中点，每个点分配到一个集中点以后，集中点到分配的点的距离和的最大值最小。

题解：显然二分最大值，考虑如何验证。先把环变成两份，可以通过前缀和快速地求从某个点开始，往右最多吃到 $r_i$。通常这里就要枚举起点了（从 $1$ 到 $r_i$），但是因为这里的区间有性质，不会出现如 $i<j$ 且 $r_i>r_j$ 这样整个跨越的情况，我们可以找到使得 $r_i-i$ 最小的 $i$，只验证 $i$ 到 $r_i$，又因为每一步最小跳 $r_i - i$ 复杂度是 $(r_i-i)\frac{n}{r_i-i} = O(n)$。

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

Upsolved by zerol. (-2)

题意：在模意义下输出一个分数（分子分母都是很多很大的数连乘）的值或者输出不能。

题解：对于询问的模数的所有素因子，在分子分母上约分，剩下部分就可以直接算了（分母要用 exgcd 取逆）。问题是模数会很大，那么处理掉 $10^6$ 之内的素因子后，与分子分母取 gcd 进行约分，gcd 可能的值有

1. $p$

2. $p, p^2$

3. $p, q, pq$

中的若干个，一通特判就好了。

Problem D

Solved by kblack. 00:57 (+2)

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

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

Problem E

Upsolved by kblack.

题意：给一个上下文无关文法，终结符只有单字母，问是否能从 $1$ 号非终结符生成一个奇数长度的字符串。

题解：对于每个非终结符和产生式，我们记录他的唯一取值或记录他可以任取，从终结符开始遍历所有包含他的非终结，然后用类似拓扑排序的方式更新，最后看 $1$ 号是不是唯一取 $1$ 或可以任取。

kblack: 其实挺简单的一道题，为什么当时没做？可能被吓到了/模拟了现场降智？

Problem F

Solved by ultmaster. 01:10 (+2)

题意：走方格问题。每个格子上有一个颜色和一个花费。先求给定花费内最少经过多少个不同的颜色。

题解：枚举可以选择的 $c$，然后跑 1024 遍 DP 即可。常数是大了点，贴着时限过的。

Problem I

Upsolved by ultmaster. (-3)

题意：有 $n+1$ 个 $\{1,2,3,\ldots,2n\}$ 的 $n$ 子集。找出两个子集使得交集大小不小于 $n/2$。

题解：貌似有的话就很多。随机一下就好了。

居然因为 cin TLE 了。难以置信。

Problem J

Solved by ultmaster. 03:13 (+)

题意：给一个排列 $p$，对于所有长度为 $n$ 的 $!$ 到 $n$ 的数组，如果这个数组里出现的数在排列中是有序的，则称是好的。求有多少个好数组。

题解：如果能求出长度为 $k$ 的上升子序列有 $g_k$ 个的话，答案就是 $\displaystyle \sum_{k=1}^n g_k k^n - \binom{k}{1} (k-1)^n + \binom{k}{2} (k-2)^n - \cdots$。

那么怎么求上升子序列的个数呢？考虑 DP。DP 状态是 $f(i,j)$ 表示以 $i$ 为结尾的长度为 $j$ 的上升子序列有多少个。从左往右扫，$f(i,j)$ 可以从 $f(k,j-1)$ ($k < i$) 进行转移。对于每个 $j$ 用一个树状数组维护计数即可。其实这种方法非常类似于求上升子序列的过程。只不过进入了错误的转化，自闭了好久。

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 即可。