联合省选2023

火车站

显然可行当且仅当轨道连续且存在以其为对应方向端点的轨道

差分判定即可，时间复杂度为\(O(n+m)\)

城市建造

\(G-E'\)为\(|V'|\)个连通块当且仅当\(V'\)中的点两两不连通，则：

• \(E'\)为\(V'\)的导出子图（\(V'\)内部的边需被删除）

• 对于路径\(a_{0},a_{1},...,a_{k}\)，若\(a_{0},a_{k}\in V'\)，则\(a_{i}\in V'\)（否则显然连通）

  在此基础上，若某个点双内选了两个点，则所有点均需选择

建立圆方树，问题即选择一个连通块，满足"外围"均为圆点，且删除所有方点后连通块大小合法

枚举连通块大小集合，两个问题即分别形如\(\{s\}\)或\(\{s,s+1\}\)（后者还需容斥减去前者）

• 对于前者，显然要求\(s\mid n\)

• 对于后者，假设分别有\(x\)和\(y\)个连通块大小为\(s\)和\(s+1\)，则\(s(x+y)+y=n\)

  记\(k=x+y\)，则\(sk\le n\le (s+1)k\)，即\(s=\lfloor\frac{n}{k}\rfloor\)或\(\frac{n}{k}-1\)（当\(k\mid n\)时）

不论哪种情况，均仅有\(O(\sqrt{n})\)种，可以暴力枚举

此时，在最顶端的方点上统计答案，则：

• 对于圆点，由该圆点是否选择，剩余方点数为\(0\)或\(sz\)

  前者方案唯一，后者方案数即所有儿子"剩余方点数合法的方案数"乘积

• 对于方点，儿子中\(sz>s\)的仅能取\(0\)，\(sz<s\)的仅能取\(sz\)，\(sz=s\)的至多取一个

  本质不同的方点数仅\(O(1)\)种，并分别贡献向答案和"剩余方点数合法的方案数"即可

时间复杂度为\(O(n\sqrt{n})\)，需要一定卡常

人员调度

不妨钦定有贡献的员工，结合Hall定理，即要求以\(k\)为根的子树内不超过\(sz_{k}\)个

维护当前所选的员工，加入时找到第一个不满足限制的祖先，并删去其子树内最小值即可

树剖+线段树维护差值，线段树分治实现删除，时间复杂度为\(O((m+k)\log^{2}n\log m)\)

过河卒

局面状态可以用两个\(O\)和\(X\)的位置及操作方确定，共\(O(n^{3}m^{3})\)种

在此基础上，由边界确定结束状态后，显然有以下两种情况：

• 能转移到某个"操作方必败"的状态，则"操作方必胜"且步数为上述的\(\min+1\)
• 能转移到的状态均为"操作方必胜"，则"操作方必败"且步数为上述的\(\max+1\)

同时，可以证明不能以此法确定的状态为平局

注意到步数均为\(+1\)，可以用拓扑排序+bfs的形式实现，时间复杂度为\(O(tn^{3}m^{3})\)

填数游戏

将\(T_{i}\)中的两数连边（相同看作自环），显然每个连通块独立，且有解的必要条件为点数$\ge $边数

换言之，每个连通块仅有以下几种情况：

• 基环树且基环为自环，则选择方式唯一，简单判定即可

• 基环树且基环不为自环，则基环外选择方式唯一，基环上按方向有两种方式

  对于边\((x,y)\)，若\(A\)填\(x\)则选法\(1\)答案\(+1\)，填\(y\)则选法\(2\)答案\(+1\)，需最大化最小答案

  记\(s_{x},s_{y},s\)为仅能填\(x/y\)和\(x,y\)均能填的位置数，则答案即\(\begin{cases}\lfloor\frac{s+s_{l}+s_{r}}{2}\rfloor&|s_{l}-s_{r}|\le s\\\min(s_{l},s_{r})+s&|s_{l}-s_{r}|>s\end{cases}\)

• 树，不妨任选一点为根建树，则枚举其中未被选择的数\(k\)后，选择方式唯一

  对于边\((x,y)\)（其中\(x\)为父亲），若\(A\)填\(x\)则\(k\)在\(y\)子树内时答案\(+1\)，填\(y\)则\(k\)在\(y\)子树外时答案\(+1\)

  确定仅能填\(x/y\)的位置后，考虑决策\(x,y\)均能填的位置——

  若两个节点无祖先-后代关系且均选子树内，显然不如均选子树外优

  在此基础上，选子树内的节点为从根出发的一条链，暴力枚举并简单维护即可

时间复杂度为\(O(\sum n+\sum m)\)

染色数组

咕咕咕