BJOI 2017 解题报告

P3713 机动训练

关键在于 trick：\(\sum a_i^2\) 可以视为两个人走了相同的路径的方案数，证明是容易的：对不同的机动路径求相同的方案数，每种个数为 \(a_i\) 的机动路径会产生 \(a_i^2\) 种本质相同的走法。

如果令 \(dp[x][y][a][b]\) 为两个人分别走到 \((x, y)\) 和 \((a, b)\) 的本质相同的走法，考虑这两个人分别从何处走来就可以了。因为范围极小，所以暴力的 \(dp\) 就可以了。

P3714 树的难题

想想就想吐了，\(O(n\log^2n)\) 的做法比较显然，也比较好想，就说说这个得了。

首先，相信大家都能想到点分治。这里就已经有了一只 \(\log\)。考虑每个分治中心怎么求，也就是考虑路径怎么拼接。开一棵动态开点线段树维护长度为 \(i\) 的路径的 \(\max\)，按儿子依次合并。因为是动态开点的，所以单个分治中心总复杂度 \(O(n\log n)\)。

P3715 魔法咒语

对于 \(L\le 100\) 的部分是显然的。首先必然要建立自动机，否则无法快速得到目前的串是否合法；其次若要 DP，令节点编号是 DP 数组的一维是简单的。因此令 \(dp[i][j]\) 为以节点 \(i\) 结尾的串长度为 \(j\) 的有多少个，枚举所有基本词汇并尝试转移即可。不要转移到自动机上的 end 节点。

而我们注意到 \(L\le 10^8\)，因此考虑矩阵快速幂。快速幂的时候，长度维没有了，取而代之的是另一维节点。也即，第 \(k\) 次快速幂后得到的 \(dp[i][j]\) 是长度为 \(2^k\) 的从 \(i\) 到 \(j\) 节点的转移方案数，这个显然是可以矩阵快速幂的。

但是其实有个问题：两次转移对起来不一定是一个完整的串。但是串长只有 \(2\)，所以把矩阵长宽扩大两倍就解决了这道题。

P3991 喷式水战改

首先，见单点插入思平衡树。显然连续段必然被分在一起，则在平衡树上跑 DP 即可。因为平衡树的结构易变，所以每个节点存储以它为根的子树的信息即可。

比较烦人的是这个题要求节点的分裂。

P3992 开车

看见这个题首先想的是老鼠进洞，然后是模拟费用流，再一看带修发现事情并不简单。

有固有结论：若车和加油站均升序排序，则答案为 \(\sum|a_i-b_i|\)。那么每次单修相当于平移一段，又改了前边一个点。这个东西肯定不能 \(\log n\) 的维护，因为此信息性质极差，绝对值很难拆。另一方面，数据范围是经典的根号范围。因此考虑分块。

能不能进一步转化题意？答案是肯定的。我们先不考虑 \(x\le10^9\) 这个限制，假设 \(x=O(n)\)，我们讨论每个 \(i\to i+1\) 的贡献是前面的车站数量，减去车的数量。那么我们相当于做区间 \(+1-1\) 和对位相减求和，因为 \(+1-1\) 带来的影响很小，容易想出我们在每个块内开一个桶记一下对位相减的差就好了。

接下来我们考虑 \(x\le 10^9\) 该怎么离散化比较好。观察到同一条线段的值不变，且桶只维护个数不用把所有的都找出来一个个加，那这意味着我们把一整段都塞到桶里时间复杂度不变。总复杂度 \(O(n\sqrt{n})\)，可能实现上什么地方带一只 \(\log\)，但是数据范围支持这两种办法均可以通过此题。

P3993 同构

神仙数学题。以下内容参考了其他题解的内容。

首先，因为答案的边数很多，我们不妨考虑其反图。我们考虑各个联通分量的性质，发现把补图划分为一定大小的几个连通分量，如果这些连通分量中不存在大小为 \(6\) 的，那么存在一种全都是树的更优或等优的解。

如果有几个连通分量不是树，唯一可能的考虑是如果替换成同样大小的树可能会和已经存在的同样大小的树同构，构成冲突，但是这时我把这些连通分量全部都接在目前最长的一个触手上面构成一个巨大的触手树，显然不会发生冲突，而这就是一种全都是树的更优或等优的解。

未完待续……