2022 International Collegiate Programming Contest, Jinan Site

时间不太够啊，只能遗憾八题了。

[A Tower]

solution

题面：签到题。

做法：队友写了个两就轻松通过了。

[B Torch]

solution

题面：胖子的火炬有秒持续时间，点火需要秒，瘦子则分别为。瘦子不能越过胖子，两人都是一秒走一步，点火时不能走路，无火了就要点。次询问，问秒时瘦子最多走的路程。

做法：

[C DFS Order 2]

solution

题面：存在不同的访问儿子顺序，现给出一棵树，问每个节点在序的第个位置出现的方案数。

做法：容易写出个简单 dp，即表示作为第个位置的方案数，转移就是，其中表示不包含的子树的其他子树在之前走的大小和为的方案数。注意到不同儿子间的顺序也有个系数，这迫使我们写个表示的儿子子树大小和为，有个儿子的方案数。这东西的转移是背包，经典的。利用这东西求，等价于一个退背包，也即这种东西，做个背包减法即可。注意儿子之间的顺序，那个系数显然就是两个阶乘和阶乘逆元的乘积。于是就转移完了。总时间复杂度。

[D Frozen Scoreboard]

solution

题面：有道题，告诉你封榜后的总榜和过题数以及总罚时数，问是否存在一种方案满足。

做法：枚举哪些题是通过的，那么其实等价于将分配到若干个数里，每个数有类似的限制，那将全部减去下界后，直接前面选择最大的贪心就是正确的了，时间复杂度。

[E Identical Parity]

solution

题面：给出，问是否存在的排列满足任意大小为的连续子段和的奇偶性都相同。

做法：这等价于奇偶性相同，首先和是显然正确的，这选择就可以了。否则就是有一些下标同余类的大小是，有一些是，枚举哪些是奇数的，可以解出，也可以直接不等式推一下算出答案。时间复杂度。

[F Grid Points]

solution

题面：给出一个简单多边形，将里面的整点按排序，问第小的点。

做法：二分斜率二分横坐标后就是等价于多边形内整点个数，拆出梯形算一算，剩下的就都是类欧的东西了，感觉很难写，赛时没写。

[G Quick Sort]

solution

题面：给出个快排程序，问交换次数。

做法：关键性质：快排交换次数是，证明就是，这东西利用琴生不等式等分析一下就是。模拟这过程等价于找左边的第一个大于等于和右边第一个小于等于，这些线段树上二分即可，时间复杂度。

[H Set of Intervals]

solution

题面：初始有一个线段可重集，每次取出两个线段，选择两个线段分别的端点，塞回去这个新线段。问最终线段的方案数。

做法：可以发现最多四个线段有用。然后可以暴搜或状压，然而队友写了个大讨论，而且没有写出来。

[I Shortest Path]

solution

题面：给出一张无向边带权图，问最短路径从开始到经过条边，对分别求出再加起来输出。

做法：

[J Skills]

solution

题面：一个人有三种属性，每天给出三个道具，分别可以提升对应的属性点，而若一个属性在之前有天没提升，则会减少，问天后的最大属性值和。

做法：容易证明空置天数不超过，这可以归纳考虑。考虑第一次提升某种属性，若轻松让它变成零，那我宁愿这一天不提升它，于是就证完了。而仍然有减到负数的情况，这该怎么办呢？同样的考虑手段，如果会变成负数，我宁愿从来没提升过这种属性。所以只要记录没提升过这种属性这个状态即可。暴力总有一维是，所以只用记录两维，时间复杂度。