1月6日省选组总结

T1：mate

题目大意：

有n个点，m1条黑边，m2条白边，每个点最多有2条边，问将在n的排列中，有多少个排列满足每个点的黑边和白边的另一端点与原来一样

解法:

不难发现，对于每个连通块，可以构成简单环，链
对于长度为 $x$ 的环，它自己的置换有 $x$ 种，若有 $y$ 个这种环，则总数为 $x^yy!$
对于偶链,每条有 $2$ 种置换,所以就有 $2^yy!$
对于奇链,每条只有 $1$ 种置换,所以只有 $y!$ 最后累乘一下即可

总结:

分类讨论要讨论清楚!

T2: teleport

题目大意:

有一颗 $n$ 个点的树,其中点 $i$ 到点 $j$ 的距离为 $d_{i,j}$ ,记每个的点的点权为 $a_i$ ,要求满足条件 $\forall l_i \le a_i \le r_i$ 和 $\forall |a_i-a_j|\le d_{i,j}$

解法:

化简条件2,得到 $\forall a_i-a_j\le d_{i,j} ~~or~~a_i-a_j\ge -d_{i,j}$ ,即 $\forall a_i\le d_{i,j}+a_j ~~or~~a_j\le d_{i,j}+a_i$ ,发现这就是一个松弛操作,对于条件1,可以构建点0,令其为起点,那么有 $\forall a_0 \le a_i-l_i~~and~~a_i\le a_0+r_i$ ,也就是说,从 $a_i$ 向 $a_0$ 连 $-l_i$ 的边,从 $a_0$ 向 $a_i$ 连 $r_i$ 的边,判负环即可,题解说 $Dijkstra$ 可以用,但其常数巨大,会超时,所以我们要用 $dfs$ 求出 $a_0$ 从子树外和子树内到点 $i$ 的最小距离 $v_i$ ,然后就可以求解最小环了