公告

计蒜之道 2016 程序设计大赛 初赛前三场题解

第一场

青云的服务器密钥 

如果只有一种字符,很好得出答案。超过 种字符,选取最少的一种字符 的一个放到第一个位置,剩下种类的字符依次排列,剩下的 k 放到末尾。比如 kxxxxxyyykk。这样最小答案就是 k 的个数减

青云的机房组网方案

子问题 1 

由于 只有 ,先处理出任意两点间的距离,然后枚举所有点对,判断下权值 是否为 ,如果为 那么给答案加上点对距离,复杂度为

子问题 2 

表示节点 子树中为 的个数。枚举每条边,左边 的个数记录为 , 右边 的个数记为 。预处理 每个数的质因子。对于右边的数 ,枚举数 的质因子选取状态 。对于左边的数 ,枚举 的质因子选取状态 , 根据选出的质因子个数容斥,奇数 , 偶数 。树上一遍扫描就可以求出答案。复杂度

子问题 3 

枚举 ,把所有 的倍数的权值的点找出来,预处理下可以做到找出来的点的权值从小到大。然后对这些点 建树,相邻两个点加进去 lca,用一个栈维护下父亲链即可。构建好树后在树上 dfs 两次可以求出所有 的倍数的权值的点对之间的距离和,最后容斥下就可以求出答案。复杂度为

第二场

联想公司的 logo 设计 

连接两条线段的中点,向两边延长直到和两个圆相交,两个交点连线即为最小的外接圆直径。其中,两条线段中点的距离可以用余弦定理求得。需要注意精度问题,比如 最好使用 而非

联想的显示屏校准

子问题1 

枚举两个点,得到这两个点构成的直线方程,然后去重即可。

子问题2 

比较显然的是平行于坐标轴的直线只有 条,然后任意一条不垂直于坐标轴的直线把斜率取反都能一一对应另一条直线,所以可以只计算斜率为正且不平行于坐标轴的直线。

考虑枚举直线的方向向量 ,显然有 ,然后来看这个方向下能有多少条直线。如果我们定义一个点 的前驱为 ,后继为 ,则直线的数量为满足“它本身以及它的前驱在点阵内而它的后继不在点阵内”的点的数量。这个数量经过一些计算可以算出是

所以这个问题就变成了算一个

由于 ,可以直接 处理出一个二维前缀和,每次询问为 。也可以进行如 子问题 3 的反演,然后暴力计算,每次询问

子问题3 

算出那个式子以后就没什么难度了, 的贡献可以和 分开计算。然后由 进行反演,然后使劲推一下就可以发现可以使用一个老技巧使得单组询问可以做到 ,然后发现只需要预处理 的前缀和,可以 预处理。

第三场

百度的科学计算器 

这是一道考察细节的题目,没有用到任何数据结构或算法。对于前导零、前置加号、小数点后的多余零、次幂的前导零和前置加号显然都应该被去除。

百度帐号的选取方案

子问题1 

由于串 的长度 只有 ,所以可以暴力枚举所有子串,再枚举重复次数,求出所有子串的最大重复次数,然后枚举所有子串对判断最大重复次数是否相同就可以了。复杂度为

子问题2 

枚举所有子串,再枚举子串长度的约数表示重复次数,哈希判断这种重复次数是否可行,于是 求出了所有子串的最大重复次数。然后求出 表示前 个字符的所有子串中最大重复次数为 的有多少个,再枚举所有子串 ,利用 数组就可以求出与该子串最大重复次数相同的子串个数。总体复杂度为

子问题3 

先只考虑重复次数 的子串,枚举长度 ,那么重复次数 的子串必定包括了 …中某相邻的两个,所以只需要看看 往前和往后最多能匹配到多远,假设往左能匹配到 ,往右能匹配到 ,那么可以处理出一些子串区间 表示区间 的某一个重复次数为 。所有这些区间个数最多有 个,基数排序后去重后有 级别个区间。区间搞出来后,对于 相同的区间,将所有区间插入线段树,在线段树里维护 表示右端点为 的区间个数。然后枚举所有区间,利用线段树维护好的信息即可求出在该区间左边的区间个数。于是对于重复次数 的相同重复次数的子串对的个数已经求出来了,然后根据已知的所有重复次数 的区间可以求出 分别表示重复次数等于 的左端点为 的子串个数和右端点为 的子串个数,那么重复次数为 的子串对就很容易可以求出了。总体复杂度为

2 comments

评论

你的邮箱地址并不会被公开显示 Required fields are marked *

你可以使用 HTML 标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>