Codeforces Global Round 15
C. Maximize the Intersections
题意
给定一个圆，圆上有 $2n$ 个点，问作 $n$ 条弦(所有弦的端点都不相同)最多能有多少个交点。其中有 $k$ 弦已经给出，且不考虑三线共点的情况。
题解
比赛时候直接蒙了结论，居然对了，补一下证明：
首先，通过手画例子分析，不难发现任意两条弦 $(a,b),(c,d)$ 如果不相交，则取 $(a,c)(b,d)$ 一定更优。
另外，对于剩下 $2n-2k$ 个点，不妨顺时针排序记为 $a_1,a_2\cdots a_{2n-2k}$。
易知作 $(a_i,a_{i+n-k})(i=1\sim n-k)$ 是唯一使得 $n-k$ 条弦两两相交的方法。
因为弦 $(a_i,a_j)$ 如果 $a_j\neq i+n-k$，则 $a_i,a_j$ 间的点少于 $n-k-1$，于是 $(a_i,a_j)$ 一定不能与其他 $n-k-1$ 条弦都相交。
E. Colors and Intervals
题意
给定 $n\times k$ 的序列，第 $i$ 个元素颜色为 $c_i$，其中 $1\le c_i\le n$，且每种颜色恰好出现 $k$ 次。
要求选择 $n$ 条线段，其中第 $i$ 条线段左右两端点颜色均为 $i$，且序列中任意一点最多被 $\lfloor \frac n{k-1}\rfloor$ 条线段覆盖。
题解
首先设颜色 $i$ 的出现位置为 $c(i,1),c(i,2)\cdots c(i,k)$，则不难发现最优方案一定是取 $[c(i,j),c(i,j+1)](1\le j\lt k)$ 的线段。
考虑将所有颜色先按 $c(i,2)$ 排序从小到大排序，取走前 $\lfloor \frac n{k-1}\rfloor$ 个颜色的 $[c(i,1),c(i,2)]$，然后删除该颜色，再依次考虑 $c(i,3)\cdots c(i,k)$。
这样操作轮数为 $k-1$，最多可以取走 $(k-1)\lfloor \frac n{k-1}\rfloor\ge n$ 种颜色，因此可以保证每个颜色都被选取。
另外第 $i$ 轮操作后考虑当前取走的颜色 $a$ 和剩下的颜色 $b$，一定有 $c(a,i)\lt c(b,i)$。
然后接下来第 $j$ 轮中取颜色 $b$ 的线段 $[c(b,j-1),c(b,j)]$ 时一定有 $c(a,i)\lt c(b,i)\le c(b,j-1)$。
所以 $[c(a,i-1),c(a,i)]$ 与 $[c(b,j-1),c(b,j)]$ 一定不相交。进一步，即任意两轮之中取的线段都不相交。
而同一轮的线段最多只有 $\lfloor \frac n{k-1}\rfloor$ 条，所以对任意一个点最多覆盖 $\lfloor \frac n{k-1}\rfloor$ 次。
于是上述构造满足题目约束，时间复杂度 $O(nk\log n)$。
