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

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