传送门
tricks from
- 三分在计算几何中应用
- 蒙特卡洛算法：给每个点赋随机权值，用集合权值和判断关系。（和哈希）
- cin 会把换行符留给之后的读入，getline(cin,s) 则会读取换行符，但不会把换行符放入 s 中。所以，使用 cin 后加 getline，要在 cin 后加 cin.ignore() 或 getchar() 来读取换行符。
- 含 max 的式子，注意观察 max 里面是否还隐含着 max，可以把里面的 max 提前。eg. max (众数出现次数)
A （三分）
在四个方向上各保留最边界的 \(3\) 个点，矩形只可能和这些点的位置有关。
不妨枚举最后边界上会留几个点。若是 \(4\) 个点，各点的 \(r\) 一定向边界方向延伸，可以 \(O(1)\) 计算。
若留 \(3\) 个点，则必然有点在拐角处。此点的 \(r\) 往矩形内侧延伸一定不优，设最终点与圆心连线与 \(y\) 轴夹锐角为 \(x\)，易得 \(x \in [0,\frac{\pi}{2}]\)，矩形面积 \(f(x)\) 为关于 \(x\) 的函数。注意到 \(f(x)\) 是单峰的，可以三分求。
留 \(2\) 个点同理。运用三角函数芝士可得，两点与各自圆心这四个点共线最优，同上三分即可。code
B
无脑 DP。（题面挺有意思的） code
D （蒙特卡洛算法）
题意就是说数据随机。把字符串 \(4\) 个字符分一组，操作 random 更容易使同一组内的元素分离开。考虑对每个组的多重集记录其在 \(n\) 个串中的出现次数，将出现次数 \(>1\) 的组个数定为该串的权值，最后取权值最大的 \(\frac{n}{2}\) 个作为 block。code
E
以样例出发，考虑 \(3\) 条链两端共 \(6\) 个点，至少有 \(3\) 个不同的编号，在上面加上新加入的两个点，从 \(i\) 递推到 \(n\) 即可。 code
简解：直接构造。code
F（DP 优化技巧）
考虑 DP，定义 \(f_{i,j}\) 表示把 \([1,j]\) 划分成 \(i\) 段的最大收益，则 \(f_{i,j} = \max_\limits{j=0}^{i-1}\{f_{i-1,j} + val(j+1,i)\}\)。\(val(l,r)\) 表示区间 \([l,r]\) 的众数出现次数。然后你发现 \(val(l,r)\) 满足四边形不等式，可以 wqs 二分做到 \(O(n \sqrt{n} \log n \log V)\) 的搞笑复杂度。
枚举 \([j+1,i]\) 中的所有 \(x\)，有 \(val(j+1,i) = \max_\limits{x}\{ cnt_{i,x}-cnt_{j,x} \}\)。放回原式并把 \(\max_x\) 提前，有 $f_{i,j} = \max_\limits{x}{ \max_\limits{j} {f_{i-1,j} -cnt_{j,x}} + cnt_{i,x}} $。
事实上，对每个可能的 \(k\)，其对 \(j\) 只可能有 \(x=a_{k}\) 的贡献，其余 \(x\) 显然把 \(j\) 增大到下一个 \(x\) 的位置一定不劣。因此 \(f_{i,j} = \max_\limits{k} \{ f_{i-1,k} + cnt_{i,a_k}-cnt_{k}\}\)。
考虑若 \(a_k \neq a_j\) 则 \(k\) 对 \(j\) 的贡献等于对 \(j-1\) 的贡献。因此只需考虑 \(a_k=a_j\) 的所有 \(k\)，用桶记录每个 \(a_j\) 的最优答案即可。时间复杂度 \(O(nk)\)。code
上面的做法启发我们改变 DP 状态：定义 \(g_{i,j}\) 表示把某段前缀划分成 \(i\) 段，钦定 \(a_j\) 为最后一段最靠后的众数的最大收益。令 \(lst_i\) 表示与 \(a_i\) 相同的上一个数位置。（若无则为 \(0\)）考虑区间内有几个众数，有转移 \(g_{i,j} =\max \{ \max_\limits{k}{g_{i-1,k}}+1, g_{i,lst_j}+1 \}\)。code