JSOI2018 部分题解

• 潜入行动
• 防御网络
• 列队

潜入行动

一眼直接 DP。

设 \(f_{i,j,0/1,0/1}\) 表示 \(i\) 子树内放了 \(j\) 个监听设备，\(i\) 是否被子结点覆盖，\(i\) 是否放了监听设备，\(i\) 子树内除了 \(i\) 都被覆盖的方案数。

转移是一个树形背包，时间复杂度 \(\mathcal{O}(nk)\)，只是常数有点大。

https://loj.ac/s/1788791。

防御网络

先考虑图是一棵树怎么做。

对于每条边计算贡献，那么答案就是所有边的贡献之和。容易发现，不妨设这条边两端的点数分别为 \(x\) 和 \(n-x\)，那么该边贡献就是 \((2^x-1)(2^{n-x}-1)\)。

再考虑仙人掌的情况。建出圆方树，为了方便可以直接 DFS 建树。

对于每条割边，其贡献也可以按照上面这种方式计算。而对于环边，我们考虑把环拿出来，把子树内有被选的点的点打上标记，那么这种分配方案的贡献就是环长减去相邻打标记的点之间的最长距离。

那么我们可以把所有子树的 \(size\) 排成一排，枚举第一个子树内有被选的点的点以及这个最长距离（注意这里不考虑最后一个到第一个的距离），然后进行一个 DP：设 \(f_{i,0/1}\) 表示选了 \(i\)，之前是否已经有相邻的点达到了最长距离。转移是一个显然可以用前缀和优化的式子。计算总贡献时枚举最后一个选了的点，方案数 \(\times\) 环长减最长距离 就是贡献。

https://loj.ac/s/1789208。

列队

肯定的是，在集合后学生的相对位置不会改变。

于是维护一棵主席树，每次将第 \(i\) 个学生的位置插入，维护区间学生个数和学生位置的编号和。

对于询问到的区间 \([l,r]\)，有以下几种情况：

• 区间内没有学生；
• 区间内的学生全都往左跑；
• 区间内的学生全都往右跑；
• 区间内的学生有往左跑的，也有往右跑的；

第 \(1\) 种可以直接返回 \(0\)，第 \(2\) 种和第 \(3\) 种可以用等差数列求和公式计算，第 \(4\) 种直接递归两个子树。

https://loj.ac/s/1409101。