公告

计蒜之道2015程序设计大赛 复赛题解

淘宝卖家评价体系      出题人:杨博洋

有各种各样的解法,比如可以类似切蛋糕,每次用一个坐标轴将长方体切成两部分(或不变),最终切完的结果就是 8 个卦限分别的面积。顺序可以通过位运算求出。这道题主要注意细节的处理,尤其是某个卦限体积为 0 的情况以及卦限顺序的计算。

京东的物流路径     出题人:戴振阳

本题有多种解法。首先是点分治的思想,在点分治的时候,我们每一次选取一个中心,先统计过中心的路径最大值,然后删掉中心,递归处理其它子树。统计过中心的路径最大值,我们以中心为根深度搜索一遍,一个需要注意的地方是路径的两个端点不能在同一子树内,因为这样可能会重复统计。所以我们把路径按子树分类,然后点权排序以后更新路径按子树分类的最大值和次大值,之和与当前点权的乘积就是答案。

本题还可以用并查集来解决。将所有点按照权值从大到小排序,对于将当前点和与其相连的所有点依次合并到一个集合中。并查集需要维护当前集合中的最长路径长度和对应的两个端点。在合并两个集合后,最终集合的最长路一定只有两类情况:一类是其中一个集合的最长路,一共有 2 种;一类是由两个集合的最长路的端点互相连接而成,一共有 2×2=4 种。需要用到最近公共祖先的算法预处理求两点在树上的距离,离线处理即可。每次合并并查集之后用当前点的权值乘以最长路的总长度来更新最优结果即可。即使这个点不在当前合并后的集合的最长路上也是没有问题的,因为如果这样的话,必然已经在之前得到了对应的结果,这次合并不会对最终结果产生影响。

中间过程不会超过 long long,WA 的同学不用怀疑数据有问题啦,请再仔细检查自己的代码是否有其他错误。对于一些复杂算法,如用 LCT 直接搞可能会被卡常数。

360的产品试用体验     出题人:郭晓旭

题意即求

q1

其中

q2

q3

因为 47 是质数,如果把 ai, li, ri, xi 写作 47 进制数

q4.1

q4.2

q4.3

q4.4

因为 47 是质数,根据 Lucas定理 ,题目转换为求

q5

的值,同时满足:

q6.1 字典序不小于 q6.2 不大于 q6.3
x1 + x2 + x3n.

形象地说,题目相当于要填一个 3 行 m 列的矩阵,每一个格子是一个 [0, 47) 的整数。我们使用动态规划解决这个问题,其中涉及基本的数位型动态规划和HNOI 2007《梦幻岛宝珠》一题中的技巧。

我们用 f(i, j, mask, r) 记录一个状态,表示从高位往低位填,现在要填第 行第 列这个格子,mask 是一个 6 位二进制数,分别表示每一行是否已经大于下界(小于上界),r 表示现在总量还剩余 r × 47j。需要注意 r ≤ 3 × 47。转移比较简单,只要枚举这个格子填什么,对应转移即可。

腾讯的星钻增值服务     出题人:商静波

注:由于本题的出题人对数据设计的缺陷,做出了不够严谨的题目设计,以下是原出题人期待考察的思路。针对本题在比赛中的给定数据,使用暴力搜索加上一定的剪枝其实可以在给定时间内通过这一题目。因为这一原因,本来预期为本场比赛最难的一道题没有表现出设计分数对应的题目难度,在此向大家表示歉意。请注意,题库中的本题数据已经增强,欢迎大家在题库中继续挑战。

先让我们来思考一下,如果这个问题被简化成“七种不同的星数分别为1, 2, 3, … 7”,这个问题应该如何解?

由于背包的最大负重和代价都比较大,所以直接做 0/1 背包难度稍大。但是由于总的星钻个数比较少,因此我们可以使用折半的方法,分别枚举四种、其余三种星钻怎么选取,得到所有可能的方案,再考虑合并(这里需要排序)。

一种简单的考虑是,假设每个星钻的星数是在 1~7 种 uniformly random 的,那么每种星数的星钻大致会在15(≈ 100/7)个左右,所以枚举的量会在154 ≈ 5 × 104

更一般的来看,考虑每种星钻的个数已知的情况下,我们可以通过枚举如何按照星数的不同分 2 组(共27 − 2种不同的分组方案),使得分出的 2 组内部组合数的最大值最小。所以,无论 7 种星钻的个数怎么分布,最坏情况下我们需要枚举的量在1.3 × 105以内。证明如下:

假设在最优分组的情况下,较小的组合数为 prod???,较大的组合数为 prodmax。由此,prod??? × Nprodmax。 又因为 prod??? × prodmax 为所有数的总乘积,这些数的总和为 ?,所以总乘积最大为 (N/7)7。所以

q9

基于 random simulation 最坏为 154,应该可以找到理论证,但这里有这个很松的界就足够了。

接下来,我们来看看星数很多的情况。核心的思想是随机染色。

首先将不同的星数随机映射到 1 到 7。假设正确答案只对应一种方案,那么在一次随机染色种,这个最佳方案中的 7 种星数被映射到 7 种不同的颜色的概率为

q10

在随机染色之后,就可以用上文提到的简单版本的方法来解决。

假设我们反复执行随机染色 1000 次,那么每一次都错误的概率为(1 − 0.006)1000 ≈ 0.002,已经是一个可以接受的范围了。如果没有通过,可以修改随机的种子后再次提交。

5 comments

  1. 第二题的并查集解法,这样合并集合真的能保证最长路上不会存在比当前点点权小的吗。。。

  2. 请问B题边权10^9,那么路径的长度就可能达到10^5*10^9,再乘以点权10^9,就是10^24为什么不会爆long long?

    1. 通常比赛中很少会出现数据设计超过long long的情况啊,我们也不会在这个点上难为选手们。这题实际的数据中没有出现任何超过long long的情况。另外5+9+9=23,理论上限是10^23不是10^24哦。

评论

你的邮箱地址并不会被公开显示 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>