竞赛讨论区 > 【题解】CCPC Wannafly Camp Day2
头像
王清楚
发布于 2020-01-21 18:06
+ 关注

【题解】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 为根的三角剖分,调用即可。

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐