评讲
T1
签到题。
简单观察，发现最后的数为 \(\sum_{i=1}^{n}a_i\times\tbinom{n-1}{i-1} \pmod m\)
题目需要求出无关量，本质上是求系数为 \(0\) 的项，即求 \(\tbinom{n-i}{i-1} \equiv 0\pmod m\) 的 \(i\)。
因为 \(m\) 不为质数，所以没法直接处理阶乘，但很容易给出一个递推的 \(O(n^2)\) 做法。
注意到我们只关心 \(\tbinom{n-i}{i-1}\) 是否为 \(m\) 的倍数，\(m\) 的质因子也比较少 \(\leq 10\)，所以我们可以直接记录每一个质因子的质数即可，这样就可以直接阶乘。
T2
简单题。
有个很重要的限制，一条边只能经过两次，说白了就是进入一棵子树之后，必须先确定叶节点有没有他的女朋友之后才能出去。
所以就能设计出树形 DP，\(dp[u][0/1]\)，表示 \(u\) 的子树是否有渡边女朋友，走完子树 \(u\) 的期望。
最终答案为 \(dp[u][1]\)。
考虑转移，首先，有小弟把守的节点，\(dp[u][0]=0\)，因为渡边家兴只需要询问小弟就可以走完这棵子树。
计算 \(dp[u][0]\)，就是 \(\sum\limits_{v\in E(u)}dp[v][0]+2\)，就是搜索完所有的儿子节点加上进入每个儿子节点的消耗。
计算 \(dp[u][1]\)，本质上我们是要确定一个搜索子树的顺序，让期望搜索时间最小，考虑对于一个顺序 \(p\)，期望时间是多少，记 \(v\) 子树中叶子个数为 \(sz_v\)，显然是 \[ \Large\sum\limits_{i=1}^{k} dp[p_i][1]\times \frac{sz_{p_i}}{sz_u} + (dp[p_i][0]+2)\times\frac{\sum\limits_{j=i+1}^{k}sz_{p_j}}{sz_v} \] 即枚举所在子树，加上额外的搜索空子树的时间。
我们可以证明，按照 \(\frac{dp[v][0]+2}{sz_v}\) 升序排序后的顺序是最优的，具体证明参考国王游戏。
T3
有些毒瘤的题。
简单观察发现每个字符都和其上下的位置高度相关，将 NOI
划分为 9 个部分，三个字母均分为中间和两边三个部分，再加上两个空白部分共
11 部分，考虑 DP，设 \(dp[i][s][l][r]\) 表示第 \(i\) 列，状态为 \(s\) ，上下为 \(l,r\) 的最大值。
其它的转移是简单的，我们着重强调 N
中间部分的转移。它转枚举了上一个上下端点 \(l',r'\)，向 \(l,r\) 转移，条件为 \(l\le r'+1\)，枚举当前的上端点 \(l\)，我们可以动态维护一个数组 \(dp\_max[i]\) 表示考虑所有 \(r=i,l'\le l\)。转移使用当前的
\(l\) 对应的 \(dp\_max\) 数组的 \([1,r]\) 的 \(\max\) 即可。
这道题的思维难度甚至没有 T2 大。
T4
思维题。
找规律和暴力各有 10pts。
Solution1
先把 BFS 序转化为 \(1,2,\dots n\)，然后再来考虑。
因为要求平均高度，所以我们需要求出总高度和总个数，转化后一棵树的高度等于 \(n\) 号节点的深度。
现在考虑划分 \(1-n\) 这个 BFS 序列。可以发现一个划分最多只能对应一棵树。
一个显然的必要条件是相同高度的元素在 DFS 序列中递增，另一个显然的必要条件是 DFS 序列中 \(dep_{a_i}+1\ge dep_{a_{i+1}}\)。
事实上，这两个条件也是充分的。
设 \(dp[i][0/1]\) 表示考虑到 \(i\)，总数和总高度。转移检查哪些左端点可以转移即可，事实上，可以转移的左端点一定是一个区间，可以处理 \(dp\) 数组的前缀和完成快速转移。
判断转移区间和结论证明，留作思考，后文有 Details。
如果可能，尽量不要看 Details，自行思考。
Solution2
考虑一个划分合法的必要条件，Solution1 中已经提到。
考虑哪些位置可以划分，把一个间隔看成一个 01 变量，选择划分为 \(1\)，发现可以转化为一个这样的问题：
你需要确定长度为 \(n-1\) 的二进制串，有若干个限制。每个限制形如
- \([l,r]\) 至多有一个 \(1\)。即：\(dep_{a_i}+1\ge dep_{a_{i+1}}\) 转化而来的 \([a_i,a_{i+1})\)
- \(x\) 位置必须为 \(1\) 。即：如果 \(pos_i>pos_{i+1}\)，那么由于同高度在 \(a\) 中的位置递增，则 \(i\) 位置必须为 \(1\)。
很容易设计出一个 \(O(n^2)\) 的动态规划做法。
观察第一个条件，如果 \(a_{i+1}>a_i\) 才会有第一个限制，如果 \(a_i+1=a_{i+1}\)，那么相当于这个限制不存在。
否则，因为保证一定存在一棵合法的树，所以 \([a_i,a_{i+1}]\) 区间的 \(pos\) 数组必须能够被划分为两个连续上升子序列。\(a_i\) 又和 \(a_{i+1}\) 紧紧挨在一起，那么得知必定会被划分，因为中间的某个数一定会冲突。我们很容易模拟得到被划分的位置，之后这个区间的所有数都不能再被划分。
对于没有限制的位置，我们划分与不划分的方案数是相同的，因此对期望的贡献是 \(0.5\)。
将所有位置的期望加起来就是答案。
Solution1 Details
Transform
看看样例，发现从 \(1-n\) 排列比较好想，所以考虑先把点做个变换，弄成 \(1-n\)，所以 \(b\) 变成了 \(1,2,3,\dots,n\)。
然后记 \(u\) 的深度为 \(dep_u\)，发现 \(\forall i\in[1,n),dep_i\le dep_{i+1}\le dep_i+1\)。
然后又发现，对于 BFS 序列为 \(1,2,3,\dots n\) 的树，一个点遍历子节点的顺序一定是按编号从小到大遍历。
所以，确定了每个点的深度和 DFS 序列。可以唯一确定一颗树。
感性证明的话，确定深度之后把点画出来，画在一个二维平面上，深度相同的点在一层按编号从小到大排列，然后在 DFS 序列上走，如果下一个点深度更大，那肯定是往下连，如果深度不变或者更小，那一定是回去了一部分再往下走了一个，这样的逻辑可以唯一确定一棵树。
自上到下，自左到右遍历二维平面所有点的过程，就是 BFS 的过程
请认真理解二维平面的含义。
本质上，确定深度的过程就是划分 \(b\) 序列的过程
Native DP Algorithm
所以考虑对 BFS 序列的划分过程 DP，设 \(dp[i][k]\) 表示考虑到第 \(i\) 个点，深度为 \(k\) 的合法划分方案总数。
然后我们需要枚举一个左端点 \(j\)，考虑如何判断这个划分是否合法。
首先有个必要条件：同一深度的点，在 DFS 序列上的位置必须递增，因为我们遍历一个点的儿子的顺序是从小到大。称该条件为条件一
其次，我们模拟一下在 DFS 序列上走的过程，发现一个点 \(u\) 的下一个点 \(x\) 一定有 \(dep_u+1\ge dep_x\)，原因是显然的。称该条件为条件二
满足了以上条件，我们可以说明一定可以构造出一棵唯一对应的树。具体的，对于一个点 \(u\)，下一个点是 \(v\)，找到它或者它的祖先 \(u'\)， 满足 \(dep_v=dep_{u'}+1\)，那么 \(v\) 的父亲就是 \(u'\)。由于第一个条件，限制了处理的 \(v\) 一定是该层第一个还没有安排父亲的点。所以每个点只会恰好被安排一次父亲，得到一个合法的树。
这样的话，我们再记录一维划分起点，变成 \(dp[i][j][k]\)。
转移枚举当前起点和上一个划分的起点，判断两个条件可以简单的 \(O(n)\) 做。
复杂度为 \(O(n^4)\)，因为对于 \(n\) 个深度 \(k\) ，一共只需要判断一次。
Observaion1&&Optimization1
- 发现其实不用记录具体每个深度有几个元素，只需要记录深度之和与树的个数就可以计算答案。
- 假设划分的区间为 \([l,r]\) ，深度为 \(d\)。条件二等价于，\(a\) 中 \([1,l)\) 的后一个元素 \(x\)，一定满足 \(x\le r\)。因为每次加入一段区间的点之后，上一次的深度为 \(d-1\) 的点的右端点，如果还没有确定深度，就会被确定为 \(d\)。所以加入后，存在右端点还没确定深度的点，其本身深度只能为 \(d\) 了。所以可以直接判断交界处的深度关系，判断方式是 \(\forall i\in[1,n),a_i>j \or a_{i+1}\ge i\)。
40Pts 的代码运用了第二个观察，请阅读。
运用第一个观察，DP 状态简化为 \(dp[i][j][0/1]\)
再次运用第二个观察，其实已经无需记录 \(j\)，DP 状态进一步简化为 \(dp[i][0/1]\)。
上述做法的复杂度是 \(O(n^3)\) 的，考虑优化。
参看 Codes 部分的 40Pts 做法。\(sum\) 数组的含义是，\(sum[i][j]\) 表示以 \(i\) 结尾，深度为 \(j\) 的方案总数。
40Pts 的部分没有对层数做简化
Observaion2&&Optimization2
其实 \(dp\) 数组没有用，只需要记录一个 \(sum\) 数组就可以了。
条件一，显然可行的 \(j\) 是一个右端点为 \(i\) 的区间，对于每个 \(i\)，可以处理出满足 \(p\) 数组(参考题解开头的定义)区间递增的最小左端点，作为 \(j\) 左端点的限制。
条件二，显然可行的 \(j\) 是一个前缀，并且右端点随 \(i\) 增大，这限制了 \(j\) 的右端点。
由于条件一，二的限为区间转移限制，所以记录一下 \(sum\) 的前缀和即可做到转移 \(O(n)\)
利用尺取法的思想可以 \(O(n^2)\) 的计算条件二的右端点。
但进一步观察，发现对条件二进行了一些无用的 check，每次移动端点时，有用的 check 只有一个，就是值为右端点本身的位置。
所以 check 变成了 \(O(1)\)，总复杂度 \(O(n)\)
参考 100Pts 代码，注意，其中的 \(dp\) 代表 40pts 写法中的 \(sum\)，\(sum\) 代表其前缀和。
Notes
- DP 过程中最大值达到了 \(2^{n}\)，需要手写科学计数法，可以忽略指数差距过大的加减运算。
Codes
40pts \(O(n^3)\)
1 |
|
100 pts \(O(n)\)
1 |
|
