2021-2022 BUAA XCPC Team Supplementary Training 02

排名	当场过题数	至今过题数	总题数
3/20	11	12	12

D

solved by JJLeo 2sozx

题意

ACM比赛，随机开题，你是 tourist 你全会做，你比 tourist 还🐂🍺还知道每道题要写多长时间，你更厉害的是你一下子能秒看随机的 \(k\) 道题，然后做一道最水的，在随机把一道题去看，继续做这 \(k\) 道题最水的，然后一直做，问你所有情况下罚时总和是多少。 \(k\le n\le300\)

题解

考虑第 \(i\) 道题在前 \(j\) 个被解决的方案数，显然 \(i\) 的位置在前 \(min(n, j + k - 1)\) 并且比 \(i\) 题水的个数小于 \(j\) ，因此 \(n^3\) 枚举转移即可，恰好在第 \(j\) 个被解决的方案数即可直接差分，总复杂度即为 \(O(n^3)\)

E

upsolved by Bazoka13 2sozx

题意

平面 \(n\) 个点，有 \(k\) 个特殊点，选择一个非特殊点的点使得 \(k\) 个特殊点于这个点构成的凸包面积最大。 \(n\le 10^5\)

题解

先求两个凸包，显然选择的点一定在大凸包上，考虑枚举点，与特殊点构成的凸包可以通过双指针来计算被覆盖的面积，其余点构成的面积可以通过前缀和面积计算，复杂度是 \(O(n\log{n})\) 。

L

solved by 2sozx

题意

给你一堆点，规定你每次移动的旋转方向为左还是右，找一条不相交的路径经过所有点。\(n\le50\)

题解

只能说是个非常经典的问题了。

从凸包上走每次走最左最右的点就可以了。

记录

0～1h：疯狂签到

2h：MJX开写L，用了个nt写法，磨磨唧唧的

3h：MJX过了L，CSK开始冲E，ZYF看D也很水交换冲

4h：CSK开始调E，MJX左右横跳，看看E，看看D，听ZYF讲了好几遍算法，听的懵逼，看着最后好像有个结论有点问题，改了就过了。MJX开始魔改CSK代码，没改明白，CSK开调最后调TLE了

总结

传参一定要注意是否是引用

Dirt

H(+1)：交接没开ll

F(+1)：ZYF多加了个1