被榜骗了，想 想了一年，罚坐了最后一小时，输。

[A Bridge]

solution

题面： 的网格图， 向 连边，有 次操作，修改操作为给出 ， 向 连边，询问操作为给出 ，从 出发，设当前在 ，若可以走到 则走到 ，否则走到 ，每条边在一次询问中只能使用一遍，最后停留在 ，求 。

做法：注意到其实等价于维护一个 个链表，每个链表长度为 。修改操作等价于将 的地方， 与 进行一次交换，查询就是就是 的链表的末尾是谁。发现点数很多，不容易直接维护。所以离线下来，每个点表示区间，用 FHQ Treap 维护即可，时间复杂度 ，假设 同阶。

[B Cells Coloring]

solution

题面： 的方格表，有些一开始有障碍其他则为空，选择一个 给所有的空格子染成 之一的颜色。同行或同列的格子非零颜色不能相同。给出 和 ，记 为最后 颜色的格子数，则花费为 ，求最小花费。

做法：容易想到网络流，黑白染色建出二分图后，枚举 等于增广几次， 等于减去的最大流，直接就做完了。时间复杂度 。

[C Clone Ranran]

solution

题面：签到。

做法：

[D Contests]

solution

题面： 个 的排列，第 个点可以走到第 个点当且仅当存在一个排列中 在 前面。 次询问 ，问 走到 的最小步数。

做法：注意到暴力是 的边数，过不了。考虑每个点是为长度为 的状态，那么一个状态拓展到另一个状态一定是在每个排列中取后缀状态的 ，感受一下这样的状态数不会太多，我猜测是不超过 的。所以暴力拓展状态，直到无变化，这样的图的点数和边数都是 的，然后倍增一下，每次跳到第一个不能查询 的点即可。时间复杂度 。

[E Find Maximum]

solution

题面： 次询问，每次询问 ，问 内三进制下每位数的和加上位数最大值是多少。

做法：感觉有显然的分类讨论做法，不过直接数位 dp 更简单。

[F Hotel]

solution

题面：酒店有 批人入住，每批有三个人，三个人可能属于不同的阵营。有双人房和单人房，花费分别为 ，只有同阵营才可以住双人房，问最小代价。

做法：注意下双人房可以被一人住，且双人房可能比单人房便宜即可。

[G Perfect Word]

solution

题面：签到。

做法：

[H Power of Two]

solution

题面：给出一个序列 ，和 表示有 个 ， 个 ， 个 ，重排 和安排 的位置，使得 最大， 定义为 ，并构造方案， 均为 的幂次。

做法：

[I Square Grid]

solution

题面： 次询问，每次给出矩形，走 步从一个顶点走到另一个顶点（上下左右），不能跨出矩形，问方案数。

做法：

[J Strange Sum]

solution

题面：签到。

做法：

[K Streets]

solution

题面：给出 条水平直线和 条竖直直线，每条直线有权值，一个长方形的权值为四条边所在的线段的权值和，线段的权值定义为所在直线的权值乘上长度，求最大面积的长方形权值不超过 。

做法：

[L Tree]

solution

题面：给出一棵树， 为根，一个集合 被称为好当且仅当它满足其中两个要求之一：

  1. 对任意的 ， 是 的祖先或 是 的祖先。

  2. 对任意的 , 不是 的祖先且 不是 的祖先。

    对 个节点进行划分，求最小划分集合数。

做法：可以注意到，第二个要求是删除所有叶子，第一个要求是删除一条链。设 表示 的子树内最深的叶子与 的距离，容易证明 会被第 条反链覆盖。枚举操作二数量，一下子就求出答案了。