联合省选 2023 题解

· · 个人记录

Day 1

火车站

模拟。

城市建造

建出圆方树，一个合法的方案相当于删去若干方点，使得每个连通块恰有一个点存在邻接点被删，且任意两个连通块圆点个数之差不超过 k。

下文定义一个连通块的大小为其中圆点数量。

考虑 k=1 的情况，枚举 i，计数所有连通块大小为 i 或 i+1 的方案。注意所有连通块大小相同的方案会被重复计数，减掉一个 k=0 的问题即可。

设 f_x 表示 x 子树中删去若干方点满足条件的方案数，且当 x 为方点时 x 必须被删，否则 x 的父亲必须被删。

转移时选取 x 的若干个子树，作为最终方案 x 所在连通块的其余点。

本质不同的 i 只有 \sqrt n 种，暴力实现的复杂度为 O(n\sqrt n)。

注意到转移时没有被选的子树大小不能小于 i。因此选中的子树必须是 x 的子树中最小的若干个子树。特殊处理只选一种子树的情况。如此一来，只有 O(deg(x)) 个 i 会使得 f_x 不等于 0。

只在这些状态之间转移，复杂度 O(n\log n)。

人员调度

对每个点 x，记 t_x 表示 x 的子树大小减去子树内被钦定的员工数。一个钦定有贡献的员工的方案是合法的，当且仅当任意 t_x 非负。

如果加入了一个人 (x,v)，先强制钦定他，这会对所有 x 的祖先 y 造成 t_y:=t_y-1 的影响，但这样做可能会导致某些 t_y 变负。

考虑反悔贪心，找到这样的 y 中最深的一个，记为 y_0，将 y_0 的子树中权值最小的、被钦定的员工取消钦定。

插入、删除、子树最小值可以用线段树实现。

祖先修改，最深负祖先可以用全局平衡二叉树实现。

对于有删除的情况，将操作离线下来，套一个线段树分治，这样删除变为撤销，而后者只需要记录被撤销的操作的影响，撤销时将影响消除即可。

时间复杂度 O((n+k+q)\log n\log q)。

Day 2

过河卒

可能的状态由三个棋子的位置描述，只有 n^3m^3 种。

将转移图建出来，考虑从终止状态开始不断确定每个点的胜负状态与步数。

如果一个点指向的点都被确定了，这个点自然也可以确定。但还有一些情况也可以被确定。

我们将已经确定状态的点放进一个队列，每次取出步数最小的点更新别人。这样一旦发现一个胜点，它的答案就不可能再改变了，即使它指向的点没有被确定完。

复杂度 O(Tn^3m^3)。

注意红棋重合问题。

填数游戏

如果某个 |t_i|=1，我们将它扩充为具有两个相同元素的可重集。

建图，在每个可重集内的两个元素间连一条边。

每条边需要选择一个端点且被选择的点两两不同，因此有解当且仅当任意联通块边数不超过点数。不难发现这意味着它是基环树或树。前者平凡，只考虑后者。

以某个点 rt 为根，将 Bob 的选法看成给边定向，选择出点。不难发现 Bob 的定向方案一定形如以某个点 r 为根的外向树。而 Alice 能做的，是对于那些 |s_i|=|t_i| 的边，对这条边向上或者向下的方案，造成 1 的贡献。

如果 Alice 选择将某条边 (u,fa_u) 向上的方案 +1，则会对所有 u 子树里的 r 造成贡献。否则会对子树外的 r 造成贡献。

由调整法易得，最优决策下所有选择向上的边构成一个包含 rt 的连通块。

考虑贪心，每次将当前答案最小的 r 的最浅的向下的祖先边改为向上。用优先队列实现即可。

复杂度 O(n\log n)。

染色数组

不会。