联合省选2023

火车站

小丑题。直接从起点开始往左往右扫即可。

submission

城市建造

不开 long long间祖宗。

首先你手完一下可以发现一个点双上面要么不选，要么选一个，要么全选，并且一定是在圆方树上选一个联通块。

这样你就可以 \(O(n^2)\) 的 dp 了。就是说你可以枚举最小联通块的大小 \(p\)，然后对于每个如果要选的点，它周围的某个子树中如果不足 \(p\) 那么肯定不能选，如果 \(> p+k\) 那么肯定要选，剩下的只有选恰好一个大小为 \(p\) 的子树的情况，可以简单特判。

注意 \(k=1\) 的时候 \(k=0\) 被算了两次，要减掉。

显然 \(k=0\) 的时候 \(p\mid n\) 可以做到 \(O(n\sqrt n)\)，但是对于 \(k=1\) 貌似没有可拓展性。

观察一下发现联通块的大小非常平均，也就是说这和重心的定义其实是差不多的。那么重心一定被选在了这个联通块中。不妨把重心跑出来然后定为根。对于某个 \(p\) ，一个点可以继续递归下去 dp 要求这个点零散的有至少 \(p\) 个，且有一个子树大于 \(p\)，可以发现每次不会遍历超过 \(\frac{n}{p}\) 个点，因此复杂度优化成 \(O(n\ln n)\)。

submission

人员调度

首先你可以一眼秒了一个反悔贪心：每个点开一个堆维护这个点子树内当前选了什么，那么这个点多出来一个人之后，如果溢出了那么从子树内选一个最小的扔了。每次修改暴力启发式合并跑，时间复杂度 \(O(nm\log^2n)\)。但是看上去和正解没有什么关系。

或许你可能会想到这题可以流。假定我们已经选好若干个人，要判定这些人是否合法，根据 Hall 定理，当且仅当每个子树内选的人的个数都不超过 \(siz_{x}\) 时合法。这样的话假设我们插入了一个人，先无脑插入进去，然后找到最深的不满足 Hall 定理条件的，然后从这个点的子树内扔掉一个最小点。这样的话所有不满足条件的都改成满足条件了，并且答案最大。因此这个贪心是正确的。

实现细节的话就先线段树分治变成只有插入，然后树剖维护每个点子树内有多少个被选，最后用一颗 dfs 序上的线段树维护每个位置还在答案中的有哪些，就可以做到 \(O(n\log ^3n)\) 了。

submission

过河卒

观察到 \((nm)^3\) 处于可以接受的范围内，不妨把状态全部设出来。

然后建立反向的边便于拓扑。如果一个红方点在原图中有一条出边到红胜，那么这个点也是红胜，如果出边全部是黑胜，那么黑胜。如果成环，那么显然可以沿着环一直走下去导致平局。黑方同理。

因此可以直接拓扑排序，时间复杂度 \(O(T(nm)^3)\)，貌似有一些人因为常数退队了，默哀。

填数游戏

首先把 \(|S_i|=1\) 和 \(|T_i|=1\) 的变成可以选两个一样的点，方便处理。

容易想到把 \(T\) 集合的两个点之间连一条边，一个联通块有解的充要条件是 \(|E|\leq |V|\)。也就是说我们只需要考树和基环树两种情况。

基环树是平凡的，不是环上的边只有一种选法，A 可以对着 B 摁。环上也只有两种选法，\(A\) 显然会让 \(B\) 的两种选法尽量平均，也容易计算。

困难的是树。如果我们将树上没有被选的哪个点定为根，那么一条边是在深度较大的那个点被选的。因此我们可以计算一条边对每个节点作为根的贡献。随便定一个点为根，那么对于一条边，如果 \(A\) 的集合中只有较浅的那个点，那么会对较深的点子树内的点贡献加一，如果只有较深的点，那么会对除了较深点子树内的点贡献加一。如果两个都有，那么是可以选择到底给子树内加一还是子树外加一。

观察可以发现两个结论：

• 如果存在两条边对应的较深节点 \(x,y\) ，满足 \(x\) 是 \(y\) 的祖先，且 \(x\) 选择了子树外，\(y\) 选择了子树内。那么不如把 \(x\) 换成子树内， \(y\) 换成子树外这样更大。
• 如果 \(x,y\) 没有祖先关系，那么两个点都选子树内不如都选子树外。

因此整棵树要么没有边选择子树内，要么选择子树内的只有一条从根节点开始的链，在 dfs 的过程中用线段树维护即可。时间复杂度 \(O(n\log n)\)。

不过因为这个修改的区间是包含关系的，因此也可以不用线段树做到线性但没必要。

submission

染色数组

进队再更（