挺不错的一场比赛，可惜被语法糖击杀了。

[A AppendAppendAppend]

solution

题意：给出串 ，求最小的 满足 包含 的子序列。

做法：每次贪心找最前面的，对每个字符二分后继即可。时间复杂度 。

[B Birthday Cake]

solution

题意：给出网格图上的 个二维点对，要求切一刀切出一个部分，使得其中没有后 个点，且包含前 个点的数量尽可能多。

做法：

[C COVID]

solution

题意：有 个人，进行了 次混管核酸检测，每次都是阳性。已知每个人初始阳的概率为 。给出每次混管检测的人员 ID，以阳的概率为第一关键字，ID 为第二关键字输出 ID 序列。

做法：只算分子即可，分母是一致的。分子直接 暴力 dfs 容斥即可，即枚举有哪几个不合法，容斥系数是容易的。但这个值会很大，毕竟是 。不过我们可以直接字典序贪心。时间复杂度 。

[D Divisible by 4 Spanning Tree]

solution

题意：给出一张图，问是否存在图的生成树，使得在树中的度为奇数的结点个数是 的倍数。

做法：

[E Exercise]

solution

题意：给出 个人，每个人有值 ，初始是 与 一组。现要求重新分 组，满足每组都不属于初始分组，且所有组内 之和最小，输出这个值。

做法：首先容易想到算 个 和 个 ，我开始想着判断二分图是否存在完美匹配，后来队友发现直接拆贡献比较简单。从大到小排序后，最优的贪心一定是前面最多两个多余的 ，那么直接 dp 转移即可。直接做是有可能前面那个多余的 刚好和当前同色，于是我们两个两个转移，这样 一定是 ，也就一定能匹配上了。时间复杂度 。

[F Fortune over Sportsmanship]

solution

题意：给 个人编号，编号小的人总能赢编号大的人。给出 矩阵 ，表示 和 比赛获得的价值。在 赢下 后， 与其他人比赛的价值会变成 、 中更大的那个。问如何安排 场比赛的顺序，使得总价值最大。

做法：队友说直接 prim 就行。

[G Gears]

solution

题意：给出 数组和 数组，问是否能排列 使得 。

做法：枚举 ，可以推导出整个 。发现可以立刻写成 ，直接加起来是不容易的，但平方和是可行的，平方和后是直接最多两个解。时间复杂度 。

[H Hanoi]

solution

题意：第一根杆可以任意顺序放置的汉诺塔问题（从杆 移到杆 ），要求总操作数不大于 .

做法：听说签到题，不知道。

[I Inadequate Operation]

solution

题意：给出数组 ，每次可以选两个相邻的最大值 0的数，把两个数都变为 ，问把 全变为 的最小操作数。

做法：每次贪心找最大的和它相邻的是对的，证明很感性可以理解。

[J Joyful Death]

solution

题意： 个精灵，你准备了 盘菜有健康值和美味度，每个精灵有个食物健康下限若吃得食物健康值 下限就会死，对于每个 ，问 的精灵来吃饭，使死掉精灵最多的情况下，最大化美味度和。

做法：显然的线段树模拟费用流，但写不完了。

[K Knowledge Testing Problem]

solution

题意： 个点 条边的图， 次询问 到 的最短距离，边的限制是端点编号之和的绝对值 。

做法：考虑询问分治，假设当前是 ，中点是 ，那么如果最短路经过了区间的另一边则一定经过了 ，所以用 作为起点跑最短路后，以它们为中转点取 。一个点存在于 个区间，所有边只跑 次，于是总复杂度就是 。

[L Level Up]

solution

题意： 层塔 个等级，初始为 级，每层有 个怪，可以选一个子集来打，怪的伤害等于攻击力，每回合每个怪攻击一次，你然后你杀死一个怪并升一级，打完一层回复 的体力，问升到 级并通关的最小初始血量。

做法：听队友说是决策单调性。

[M Mousetrap]

solution

题意：给出一棵树及每个点的权值，从 开始向下随机游走，每次按子节点的权值占比位概率，你可以给任意节点增加总和不大于 的权值最大化到达 点的概率。

做法：

[N Nusret Gökçe]

solution

题意：给出 个数 和 ，可以任意增加 ，问使 的最小增量。

做法：如果可以减少就是 slope trick，只能增加等价于每次加入一条直线，那么一直取凸包左端点即可。这东西等价于扫两遍。时间复杂度 。