2025 省选模拟 6
A.圣诞树
DP，计数题
考虑题目题目的两个限制
-
相邻两层彩球颜色集合不同
-
同层相邻两个彩球颜色不同
发现求出每一行恰好 \(j\) 个颜色后第二个限制很简单就解决了。
设 \(f_{i,j}\) 表示长度为 \(i\) 时恰好有 \(j\) 个颜色的方案数（对于一行考虑）
设 \(g_{i,j}\) 表示考虑前 \(i\) 行时第 \(i\) 恰有 \(j\) 个颜色的方案数（对于全局统计答案考虑）
设 \(s_i=\sum_jg_{i,j}\)
则 \(g\) 数组的转移为
\[g_{i,j}=f_{l_i,j}\left (\left (s_{i-1}-g_{i-1,j}\right )\binom{m}{j}+g_{i-1,j}\left (\binom{m}{j}-1\right )\right ) \]对于 \(f\) 数组考虑一个从无到有的的过程去转移。
\[f_{i,j}=f_{i-1,j}(j-1)+f_{i-1,j-1} \]转移第一部分是增加一位，第二部分是增加一个数（第一次出现的位置），对于增加一个数我们考虑钦定从 \(1-j\) 依次去添加，最后有再乘上一个全排即可。
时间复杂度 \(O(l^2+\sum l+n+m)\).
B.过河
构造，二分图，dfs树
显然第一步得选取一个和 \(m\) 个三元关系都有关的猪，称其为关键点。
若样的关键点大于 \(2\) 显然有解，因为可以一边放一个，然后把其他的依次挪过去。
考虑关键点个数等于 \(1\) 时。
逆向思维去想，最后一步一定是移动关键点，所以一定有一个关键点再次过河的过程。
考虑这个过程，分为两步。
-
第一步，此时关键点过河，未过河的点形成一些二元关系，但这些二元关系可能有交，发现当二元关系不存在奇环时，可以将所有二元关系拆开，即移动一个属于二元限制的点过河，此时两边显然不会有冲突，可以将关键点重新运回来，依旧不会冲突，然后将所有除关键点外的点移动过河即，即是一组合法解。但是若未过河的点形成了奇环，此时肯定不能将所有二元关系拆开，因为拆开后河对岸必定发生冲突，考虑破坏奇环。
-
第二步，发现最多有两次机会去破坏未过河的二元关系组成的奇环，即在河两边都没有冲突时（人在河中央也不会有冲突），将两个属于奇环且相邻的点运过河，再运输第二次时，会发生冲突，但是由于人在所以不会有冲突，此时再将特殊点运过河。运过河后如果还有奇环，此时还会有冲突，但由于人在所以不会有冲突，此时能再破坏一次。总共两次。
此时得到一个暴力的做法，即枚举两个点，然后跑黑白染色判断二分图，单次时间复杂度 \(O(n^2(n+m))\)，可以使用线段树分治优化，虽然我优化后和 GGrun 暴力一个分（
考虑正解，依旧考虑枚举一个点，然后判断是否存在另一个点。
这个点一定是所有奇环的交集，但是由于环与环之间的 "异或" 操作导致无法统计全部数量。
注意到一些性质，两个奇环相交不会得到奇环，而一个奇环和一个偶环相交会得到奇环。
证明
考虑通过 总大小 - 交集 去判断奇偶性，由于交集部分贡献会乘 \(2\) 所以根据总大小即可判断奇偶。
考虑奇环和偶环相交后那些点是合法的
对于图中的红点是非法的，因为去掉后依旧会存在奇环，黄点是合法的，因为去掉后就能将两个奇环破坏掉。
考虑通过 dfs树 去找环
由于 dfs树 只能找到不能找到与偶环相交后的奇环，所以得额外去判断上面情况。
考虑对每个点维护子树内通过 奇环/偶环 返祖边所能达到最小的 \(dep\)，可以通过前缀和优化 ，然后通过每个儿子的信息去判断上述情况（因为得在同一颗子树内，否则就成上图中下部黄点了），此时不用关心偶环与偶环相交生成的偶环，因为此时统计信息是最小能达到的 \(dep\)，不用 "异或" 产生的环的信息也能完成。
合法点还得是所有能找到奇环的交，和上面一样前缀和差分优化即可。
时间复杂度 \(O(Tn(n+m))\)。
C.点对游戏
概率期望，树上问题
不难发现每个最终局面的概率相等。
记 \(a,b,c\) 为每个人最终选点的个数。
考虑计算贡献，考虑枚举一组点对，然后判断其距离是否合法，其对 A 的贡献为 \(\dfrac{\dbinom{n-2}{a-2,b,c}}{\dbinom{n}{a,b,c}}=\dfrac{a(a-1)}{n(n-1)}\)，发现只用计算有多少组点对合法即可。
使用点分治或者 dsu 即可在 \(O(nm\log n)\) 复杂度解决。
标签：过河,省选,二元关系,偶环,2025,奇环,考虑,模拟,关键点 From： https://www.cnblogs.com/07Qyun/p/18675522