The 3rd Universal Cup 做题记录 (2)

The 3rd Universal Cup 做题记录

Stage 0 - Stage 9：The 3rd Universal Cup 做题记录 (1)

Stage 10 - Stage 19：The 3rd Universal Cup 做题记录 (2)

The 3rd Universal Cup. Stage 10: West Lake

A. Italian Cuisine

复制一遍，枚举 \(i\) 维护右端点 \(j\)。要求 \((x,y)\) 到过 \((a_i,b_i),(a_j,b_j)\) 的直线距离大于 \(r\) 或 等于 \(r\) 且交点不在线段上，即 \(\angle OIJ\) 和 \(\angle OJI\) 至少一个为钝角，即两个向量的数量积小于零。要求 \((a_i,b_i),(x,y),(a_j,b_j)\) 的夹角和 \((a_i,b_i),(x,y),(a_{j-1},b_{j-1})\) 的夹角同正负，即两个向量的叉积同正负。三点坐标求面积 \(S=\frac{\lvert x1y2+x2y3+x3y1-x1y3-x2y1-x3y2\rvert}{2}\)。

C. Permutation

大概在 \(\frac{2}{3}n\log n\) 级别。线段树维护区间 \([l,r]\) 有什么数，每次随机取出两个数，将左半边设为 \(u\)，右半边设为 \(v\) 询问。如果 \(ans=0/2\) 可以将 \(u,v\) 放入左右儿子，否则如果这是第一次，就把 \(u,v\) 放回去重来，否则一定找得到一个数 \(x\)，将某半边设为 \(x\) 再问一遍。理论上是 \(\frac{3}{4}n\log n\)，加上剪枝次数就差不多刚好了，偶尔会超。

D. Collect the Coins

按 \(t_i\) 排序，二分答案 \(x\)。设 \(dp_{i,j}\) 为前 \(i\) 个询问，另一个人在询问 \(j\)。如果 \(\lvert p_i-p_{i-1}\rvert\le x\times (t_i-t_{i-1})\)，\(dp_{i,j}\) 继承 \(dp_{i-1,j}\)。然后再考虑 \(j\) 更新 \(dp_{i,i-1}\)。拆绝对值有 \(p_i+xt_i\ge p_j+xt_j\) 且 \(p_i-ct_i\le p_j-xt_j\)。维护对应的 \(mn\) 和 \(mx\) 即可。

K. Palindromic Polygon

复制一遍，设 \(dp_{i,j,0/1/2}\) 为区间 \([i,j]\) 中选了 \(i,j\) 且是回文串、除了 \(i\) 是回文串，除了 \(j\) 是回文串的最大面积。