【题解】CCPC Wannafly Camp Day2

难度预期

预期
A,C < E < D,K,I,H < J < F,B < G

实际：
A,C < E < H,K < F < B,J < D,I < G

A 托米的字符串

题意：统计所有子串元音字母占比的平均值

题解：令表示前个字母中元音字母个数
令长度为的子串中元音字母出现的个数之和为，

最后答案是.

C 纳新一百的石子游戏

题意：对于每个前缀的所有石子堆，询问先手必胜方案数。

题解：设当前异或和为，则要找到的就是有多少堆石头满足，这样就能将变为来使得异或和为。考虑异或和的最高的为的二进制位，所有这一位是的显然都满足条件，这一位是的都不满足条件。

E 阔力梯的树

题意：求把树上每个节点的子树里所有节点编号拿出来，排序后两两求差后的平方和。

题解：启发式合并，用 set 维护子树的序列，逐个加入时把相邻元素拿出来对答案作贡献。

H 叁佰爱抠的序列

题意：找到最大的，使得存在一个长度为值域为的序列，满足任意一组相邻关系都存在。

题解：考虑个点的完全图，若为奇数，则存在一条欧拉回路。若为偶数，同理至少把个点补足条边，使得除点外任意一点度数都为偶数才会存在欧拉路径。

因此，通过二分/小心枚举得到最大的，之后建图跑欧拉回路。

K 破忒头的匿名信

题意：用字典里的单词凑出长串，同时要求代价和最小。

题解：注意到限制了字典里单词长度总和，则字典里不同长度单词至多有根号个。则对于一个位置 p，其前继有效转移位置至多有根号个。

通过AC自动机预处理出每一个位置的有效转移位置，题目变成在一个 DAG 上求最短路， dp 即可。

F 采蘑菇的克拉丽丝

题意：一棵树，单点修改，求从某个点出发，对于每个蘑菇，采集需要走靠近它那条边一步的代价，求代价和。

题解：一个显然的暴力是用树状数组维护子树和，询问时枚举每条出边。
树链剖分，考虑只枚举和父亲、重儿子的边，还差所有轻儿子的贡献。于是修改的时候，往根跳，在轻重链交替的时候往轻边父亲打标记即可。

B 萨博的方程式

题意：，对于每个未知数限制，求解的组数。

题解：数位DP，我们看一个直观的样例：
将转换为二进制：

从最高位开始看，我们关注第一位是的数。如果我们的解的第一位是，那么其他解的第二位到最后一位无论怎么选，总能找到一个数使得：

这样我们可以 DP 计算出这一位对答案的贡献。 表示前个的最高位为的数中我们选个的最高位为、个的最高位为的方案数，状态转移方程：

这样就计算出这一位不全选的解对答案的贡献。
这一位如果能选的都选了，那么只需要把第二位当成最高位再做 DP，知道所有位的贡献都被计算完成为止即可.

J 邦邦的2-SAT模板

题意：给出一个2-sat模板(来源于可爱的克拉丽丝，似乎和lrj模板相似)

题解：构造有很多，给出其中一个
对于从到，和。最后和。
没错，本题就是为了告诉在座各位你们的板子可能是个暴力…..

D 卡拉巴什的字符串

题意：动态维护，求任意两个后缀的 lcp 集合的 mex。

题解：考虑用后缀自动机求两个后缀的 LCP，是在 parent 树上找到 lca 之后的 maxlen 的值，所以两两后缀的 LCP 的集合就是后缀自动机节点的 maxlen 值的集合。
方法一：考虑一个个字母加入时动态构建后缀自动机，每当一个节点有儿子节点，那这个节点就能成为两个不同后缀的 lca，就在布尔数组里标记为 1。每加入一个字母都暴力维护 MEX 的值，均摊O(N)
方法二：考虑两个后缀的 LCP 值加入为 x，同时删掉第一个字母，LCP 就变 x-1，所以 1 到 x 都存在，所以答案就是 maxlen 的最大值 +1
注意特判单字母的字符串是没有为 0 的 LCP 的。在方法一中，体现为 parent 树的根结点在只有一个儿子的时候不能成为 lca，因为根结点不代表一个后缀。

I 堡堡的宝藏

转化题意：一张二分图，存在一定量的关系，要求最小。

前置知识：
Km 算法用于求完备匹配下的最大权匹配。
该算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转化为求完备匹配的问题的。
设顶点 的顶标为 ，顶点的顶标为，顶点与之间的边权为。在算法执行过程中的任一时刻，对于任一条边 ，始终成立。
KM 算法的正确性基于以下定理：若由二分图中所有满足的边构成的子图(称做相等子图)有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
题解：因此，Km算法可以用来解决一类不等式问题，在本题直接套用即可。
注意，本题隐含条件。

G 糖糖王国的道路修建

题意：对两个点集造两棵平面生成树，要求任意两条边不交。保证不存在点三点共线。

题解：牛逼结论：凸包上的组成要么全白，要么全黑，要么一黑一白。

我们下面给出一个牛逼的证明(构造)
我们定义一个方法，表示白点 A，黑点 B,C (已经直接/间接相连)。我们要把三角形 ABC 内部所有白点和 A 连起来，把黑点和 B,C 连起来。
具体实现：如果三角形内部存在白点 S，则连接 AS，然后执行
否则把内部所有黑点按与线段 BC 的距离排序，然后相邻相连，最后补个 B 即可。
如果凸包上是单纯的，直接外面连一起来，然后取任意一个黑点 p，不断地调用转一圈即可。
否则，先把凸包上的黑和白分别相连，然后需要将凸包从中间切开，找到黑白分割的 p,q，然后做一条线把两边拆成两个凸多边形。最后分别做以 p,q 为根的三角剖分，调用即可。