MX Day2

· · 生活·游记

T1：

做法：

1、统计自由数，也就是 a_i == b_i 的那些数，这些数可以随便交换；

2、找出第一个不在自由数中的数字，这个就是答案，之于为什么只能从自由数之前找，因为我们要保证这些数一定不能被交换出来，而自由数无论怎么交换永远存在数组里面；

3、找出那些位子不能交换，也就是包含答案数的位子；

4、之后排列组合

T2：

1、我们可以确定当前节点选还是不选；

2、定义dp[u][0/1][0/1]表示当前点u选还是不选，它的父亲选还是不选，如果当前点不选，则我们可以直接将他的儿子节点的答案相乘，毕竟没有限制，这几个儿子不相连。

你问我为啥不考虑他的爹，因为u不选他的爹也不会影响答案，应该乘进去，因为dp状态表示的是当前子树中的答案

3、否则，我们就要考虑选择u的情况，先考虑要选这个叶子的父亲，也就是u自己，第三维度一定是1。之后我们可以考虑是否选择v，如果我们此时还有空间，就选dp[v][1][1]。

code：

T3：