北方大学多校联合训练第十一场（长安大学）简要题解

A.Palindrome

先把相邻的同字母段合并，跑一遍马拉车，注意只有长度和字母均相等才继续扩展。统计答案的时候再考虑两侧可能还有一段字母相同但是长度不同，取两边长度较小者。

B.Triangles

小于三个点的情况答案为零。考虑三个点的情况，由于三点不共线，必然构成一个三角形。现加入第四个点，若其在原三角形外部，则称其为外点，可以新构造$1$个三角形；若其在原三角形内部，则称其为内点，可以新构造$3$个三角形。故要尽可能让更多的点成为内点。假设这$n$个点的凸包上有$m$个点，这$m$个点必然只能是外点，将凸包剖分成$m - 2$个三角形后，剩余$n - m$个点均为内点，答案即为$3n - 2m - 2$。

C.XOR Queries

若询问固定$[L, R]$，那么可以用字典树维护$[L, R]$之间所有数的二进制表示，每次询问$(A, B)$只要在树上统计一遍即可。那么对于不同的$[L, R]$，可以用线段树或者类似的离线分治将询问区间分成$log$个然后在每个字典树上分别统计再求和。莫队维护字典树转移应该也可以通过本题。

D.Annual Party

  • 若题目为树上单组询问，只要维护子树中关键点个数以及关键点到根的距离之和$dp$两遍即可。
  • 若题目为树上多组询问，由于$\sum k \leq 100000$，每次建虚树$dp$即可。
  • 若题目为环套树上单组询问，先把环抠出来，环上每个点作为根按照树上版本做，第二次$dp$之前对于每个根需要统计其他树上所有关键点到它的距离，注意到环上存在一个分界点，分界点一侧的根从环左侧到当前根比较近，另一侧则从环右侧到当前根比较近，而遍历根的时候这个分界点也是单调的，故滑窗在环上扫一遍即可。
  • 那么对于本题环套树上多组询问，可以类似的用虚树方法，环上每个根下的子树按树上版本做，环上只保留子树中有关键点的根，环上其余的边压缩掉，环上的处理同上，由于这样最多仅增加了$\sum k$个点，故复杂度和上面是一样的。

E.Modules

显然安置完所有模块形成以主板为根的树，即为一个非常耿直的最大树形图问题。建图先考虑每个模块若无加成则可以直接连在主板上，再考虑加成给$m$对模块连边。

F.Expectation

定义$f[x]$为满足$L \leq a, b \leq R$且$a \bigoplus b = x$的有序对$(a, b)$数目，那么第$i$个位置填数$j$带来的贡献为：

单个$f[x]$可以用数位$dp$在$O(log(x))$时间求出，直接求每个$f[x]$再统计一遍答案就可以通过本题了，但是稍微整理一下就发现答案是：

前面可以$O(1)$求，最后一项关于$f$的和式一次数位$dp$就可以$O(log(R))$求出。