A Yet Another LCP Problem
考虑反过来看串，如果建立前缀树，会发现这个 LCP 长度的问题就可以看成对于所有一类集合的点都到根全部 +1 ，对所有二类集合点求和。但是由于一般来说前缀树显然是建不出来的只能建出 parent 树，而如果建出 parent 树后，相当于这个点父亲到根的所有串全部 +1 ，然后需要特殊处理当前点。因此树剖显得挺难受，于是考虑建立虚树后 dfs 两遍做即可。细节可以参考代码。
复杂度 $O(n\log n)$ 对每个点上串的长度需要排序，以及建虚树时需要排序。
1 |
|
B Qanat
我们考虑当我们对 $x_1,x_2,\dots ,x_n$ 打洞，最后花费是啥。为了方便，设 $x_0 = 0,x_{n+1} = w$ 。显然对于 $x_i,x_{i+1}$ 之间的土，设洞的高度为 $h_i$ ，那么 $\frac{h_i+h_{i+1} + x_{i+1} - x_i}{2} - h_i$ 之前的部分会从左边运出去，剩下的会从右边运出去。我们设 $f(a) = \int_{0}^a x\ \text{d}x $ ，那么显然，总花费可以通过对于每两个相邻的洞，我们算出运出这两个洞以及中间的土需要的花费，再减去每个洞本身的花费再加上最后一个洞的花费得到的就是总花费。这三部分可以分开算，最后一部分是常量也就是 $f(h)$ 对最大值时的取值不重要就不管了，于是式子就是：
我们设 $k = \frac{h}{w}$ ，那么 $h_i = kx_i$ ，于是我们可以写出一个 $n$ 元函数。然后就可以对这个东西求偏导，考虑对 $x_i$ 求偏导，式子大概是：
剩下的都和 $x_i$ 无关。设 $a = \frac{k+1}{2} , b = \frac{k-1}{2}$ ，最后可以得到一个关于 $a,b,k$ 的式子，大概是：
然后我们设 $x_1 = x,x_0 = 0$ ，可以得到 $x_n$ 关于 $x$ 的式子，解出即可。
1 |
|
C 精准预测
我们考虑给每个时刻建出每个人的活点和死点，这样就可以类似 2-sat 来建边。但是这样复杂度不可接受。于是考虑只对每个人的关键时刻（也就是与它相连的边的时刻）来建点，这样点的个数就是 $O(n+m)$ 了。
然后建点完成后考虑怎么算答案。我们可以对于每个人建立出 $T+1$ 时刻的活点然后从这个点跑一次 dfs ，看看可以到达哪些人的死点。如果它可以到达自己的死点，显然计算所有人的答案的时候它都不在贡献里，把它放入必死点。否则，答案显然就是所有点减去这个点能到的死点并上必死点的集合大小。可以发现这些集合操作都是可以 bitset 优化的。这样时间复杂度仅仅是 $O(\frac{n(n+m)}{\omega})$ 可以接受，但是一算空间就炸了。所以可以考虑我们分块来做，类似 Ynoi 掉进兔子洞，每块分别做做完再合并即可，空间复杂度就可以接受了。
1 |
|
D AUOJ117 随机变量
不难发现，设 $A(z) = \sum_{i=0}^k p_kz^k$ ，然后只要求出 $A^n(z) \pmod {z^x}$ ，就可以算出答案（分别算最后得值小于和大于等于 $x$ 得情况）。
这个形式的式子是可以类似暴力多项式 $\exp$ 来做的，设 $G(z) = A^n(z)$ ，那么我们对两边分别求导，得到
最后得到的这个式子就可以 $O(k)$ 递推了，因为 $t-i$ 的范围是 $\le k$ ，然后复杂度就是 $O(xk)$ 大概 $5\times 10^7$ 。
1 |
|