竞赛讨论区 > 【题解】CCPC Wannafly Camp Day1
头像
王清楚
编辑于 2020-01-20 20:00
+ 关注

【题解】CCPC Wannafly Camp Day1

A、期望逆序对

medium
假设最终序列是 ,它作为最优解的一个必要条件是交换两个相邻的位置 不能让答案变得更优。交换两个相邻的数的时候,只有它们之间的相对顺序发生了改变,所有这个条件也可以被写成所有 是逆序对的概率不超过图片说明
对于两个随机变量,考虑(x,y)是逆序对的概率不超过。的条件:
1.,这时 的区间整体在 的左侧,因此形成逆序对的概率不超过号。
2.,即 的区间包含 的区间时,如果 的区间在 的区间的正中央时,根据对称性,形成逆序对的概率是恰好。因此当 中间偏右的时候,逆序对的概率就小于了;中间偏左的时候,逆序对的概率大于
综上,条件可以被总结为。因此最开始把所有区间按照中点从小到大排序,我们就可以得到最优的序列。问题变成了给定序列怎么求逆序对个数的期望。根据期望的可加性,我们可以枚举每一对位置,答案就是它们形成逆序对的概率加起来。对于两个随机变量,左边比右边大的概率为:
右侧是一个分段的线性函数,讨论一下即可。总的时间复杂度为

B、密码学

easy
题面中给出了已知原文和秘钥,加密得到密文的方法。其实已知密文和秘钥,就可以轻松的解密出原文:只要用密文对应的数字减去秘钥对应的数字就可以了。
因此,我们可以从后往前“撤销”所有加密操作带来的影响。假设最后一次加密操作是用 去加密
,那么在结果中,。是没有发生变化的,即秘钥已知;,存储的是结果,即密文已知。从而用上面的方法可以直接从两者之中推出 ,原来的值。
所以从后往前考虑每一次加密操作,依次进行撤销,最后得到的就是最开始的 个字符串。

C、染色图

medium-easy
对于一张图,如果染色方案已知:染第 种颜色的点的个数是 ,为了最大化图的边数,我们会在每一对不同颜色点之间连上一条边,因此此时的最大边数为:
为了让上面这个十字尽可能大,最优方案是把 均匀地分配给所有的 ,即有 个颜色有 个点,有 个颜色有个点,此时边数为:
使用两个恒等式化简:。这样可以得到是一个只和。后两者的取值只有 种,枚举它们然后每一段直接求和即可。
时间复杂度为

D、生成树

medium-hard
这题要用到带权版本的基尔霍夫矩阵:对于一张带边权图G,定义生成树的权值为所有使用的边权的乘积,求所有生成树的权值和。方法和不带权的版本类似,定义矩阵A:
1.,等于 所有相邻边的权值和。
2.等于 的权值。令 删去第 行第 列后得到的矩阵,那么答案就是
在这题中,我们定义所有只在 的边的边权为 ,同时在 中的边的边权为 ,那么B的每一个元素都是一个多项式,记作 是一个 次多项式,其中 表示使用了 条公共边的生成树个数,所以答案就是
根据矩阵求导法则,可以得到:
用高斯消元 的行列式和逆矩阵即可,时间复杂度为

E、树与路径

为第 个点为根时的答案,那么 可以在 时间内求出来。现在对于每一个点 ,设它的父亲为 ,考虑
1.对于任何一条不同时经过 ,的路径,它对;的贡献相同,即
2.对于一条同时经过 的路径,设其长度为 往下的长度是 ,那么对 的贡献为,对 ;的贡献为 ,即对 ;的贡献是 。所以,我们需要对每一个,求出所有同时经过 :的所有路径的 的和(记作)。对于路径(u,v),设它们的最近公共祖先为 ,我们只考虑这一半边路径(另半边对称),这条路径对 产生了的贡献,对危产生了产生了 的贡献,以此类推可得,对 上的每一个点 产生了的贡献,其中 表示 的深度。
我们可以用树上前缀和来推出所有 :如果要对加上一个等差数列,就在 上加上,在 中减去,然后DFS一遍,对每一个点 算出子树内的所有标记和 ,那么
求出 后,DFS一遍就可以根据A1的值推出所有的值。时间复杂度

F、乘法

medium-easy
二分答案 ,算小于等于 的乘积有多少个。这只要对 排序后,lower_bound 或者用指针单调地扫一遍就行了。难点在于数可以是负数或者 ,因此要对这些情况分类讨论。
时间复杂度

G、圆凸包

medium
在合并两个凸包的时候,我们会选择先求出两个凸包的外切线:外切线会取代原来凸包的一部分边界,出现在合并后的凸包边界上。因为圆也是凸包,所以这个过程对圆同样适用。
因此,答案的边界一定是若干段圆弧+外切线。考虑什么样的点会成为答案的顶点:
1.首先这个点必须要是某两个圆之间的外切点。
2.这个点不被任何圆覆盖。
因此我们可以先 求出所有满足这个条件的顶点,然后对这些顶点求凸包。计算答案的时候,如果相邻两个凸包点在同一个圆上,说明这一段应该是圆弧,就把对应长度的圆弧计入答案,否则说明这一段是外切线,直接把这一段的长度计入答案。
时间复杂度

H、最大公约数

easy
考虑 的取值:
1. 必须是 的倍数,否则无法区分
2.对于的每一个质数 必须是 的倍数,否则无法区分
因此设中的所有质数,那么答案就是。用高精度计算后就能得到答案。

I、K小数查询

medium-hard
考虑区间线段树套权值线段树求区间 小值的算法:对建线段树,每一个线段树节点,用一棵动态开点的权值线段树记录 中每种权值出现了多少次。
如果能够维护这样的数据结构,询问就可以转化为在 棵权值线段树上二分,能在的时间里得到答案。
修改时,首先和普通的区间线段树一样,定位到某些节点:这次修改相当于把内层线段树中所有大于等于 的数并到 的位置,这可以被转化成 次线段树单点修改操作,其中 为被并入的节点个数。把这 次修改应用到内层线段树以及所有祖先节点的内层线段树上。这一步的时间复杂度为
接着,在 上打上对 的标记。在标记下传的时候,同样当前节点的内层线段树中,更大的节点的值并到 处,但是因为次数祖先节点的内层线段树的信息都是正确的,所以不需要把修改应用到祖先节点的内层线段树上。
时间复杂度和所有操作的 的和有关,不难发现,每一次操作结束后,内层线段树的叶子节点个数都减少了 ,而最开始一共有个叶子节点,所以 的总和不会超过。因此总的时间复杂度为

J、德州扑克

medium-hard
直接枚举公共的 张牌的方案数是,再加上判断的复杂度乘上长度,是容易超时的。在此基础上各凭本事的剪枝就行了。
标算的做法是不枚举所有花色组合:出现同花的时候,必然有一种花色出现了超过 次,此时只有这一种花色的花色信息是有用的(其他花色不可能出现同花了)。因此只需要枚举大小组合、出现超过 次的花色以及对应的牌即可,枚举量就大大降低了。

全部评论

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

等你来战

查看全部

热门推荐