公告

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

百度地图的实时路况

枚举 中的 ,把 从这个图中删去,再求这时的全源最短路即可,使用 Floyd 算法来做上述过程。Floyd 算法可以是一个增量的过程,虽然第一维一般都是从 枚举到 但是这个枚举的顺序并不影响最后的结果。所以如果可以预处理出对于每个点 只剩 没有在 Floyd 的第一维枚举到的矩阵,这个矩阵的值就是不经过 点的全源最短路。

所以使用分治,每一次把点集拆成两半,先用前一半的点在 Floyd 算法中滚,再递归后一半点。然后回溯,用后一半的点在 Floyd 算法里滚,递归前一半的点。这样每个只有一个点的状态得到的就是只有这个点没有在 Floyd 算法里滚的矩阵。

时间复杂度为

联想专卖店大促销

首先,我们需要翻译一下“相邻两位领礼包的顾客拿到的礼包类型都是不同的”这个条件。其实就是要求最多的那种类型不超过总数的一半。

因为所有 的总和比较小,因此我们可以枚举其中最多的一个类型的礼包总数后,计算另外两个怎么取既满足条件又总和最大即可。

因为 ,但是 机械键盘 又只有一类礼包会用到,所以最多的类型只可能是豪华礼包或者普通礼包。

那么分两种情况。

如果我们枚举豪华礼包用了 个。注意因为。如果 ,那么我们直接纯用普通礼包。否则,因为解一个整数线性规划问题,在实数最优解附近枚举一下就可以了。

另一种情况较为简单,可以优先组合出豪华礼包,再贪心地组其他礼包。

当然,枚举过程中我们没有考虑最初提到的条件,所以我们还需要在更新答案之前加一步验证。

青云的网络方案设计

这是一个比较复杂的构造题。大致的思路如下:
1. 当原图是一个节点连向所有节点的形状(star)时,需要特判。此时得到的是一个完全图。也是我们构造的边界情况。
2. 接下来就是每一次找到一圈叶子。因为叶子在图中相邻的点之间也都是相邻的。如果不是边界情况的话,叶子的 degree 一定是它相邻的点里极小的。
3. 找这些叶子的父亲。根据该叶子的 neighbor 的个数分情况讨论。不超过 个,就是一个 star;如果是 ,那就可以确定那两个点之间是相连的。否则需要递归后返回一个点来和这个叶子相连。
4. 扒掉这圈叶子,递归构造。

具体的证明和构造细节,可以参考这篇论文:Lin, Y. L., & Skiena, S. S. (1995). Algorithms for square roots of graphs. SIAM Journal on Discrete Mathematics, 8(1), 99-118.

微软项目经理的挑选方案

考虑 dp 的做法,首先把所有线段按照右端点排序,右端点相同的按照左端点排序,然后从 重新给线段标号。

是所选的线段集合的下标,定义 是满足下面条件的 的集合: 中的最大值, 是最小的未被 中线段支配的线段下标。显然对于每个 都是唯一确定的。另外定义 表示线段 后面,最小的未被支配的线段下标,如果不存在的话令 。定义 表示线段 前面,最大的未被 支配的线段下标,如果不存在,令 。显然题目要求答案就是 .

令能被 支配的线段集合为 ,其实 ,考虑下面计算 的做法:

对于 的情况:
, , 其它

对于

上述计算方法是 的,一个简单的前缀和表示就可以优化到 ,令 ,稍作推导,可以得到以下的递推式:
对于
, 其它
对于


显然,s 可以用线段树优化到 ,只需要实现一个支持区间乘法,区间求和的线段树即可。

微信钱包付款

对于一个整数 和它每一位数字的和 来说,。因此,题目有解当且仅当输入的值是 的倍数。所以只需要输出 即可。

菜鸟物流的运输网络

这题是一个比较经典的网络流模型。把中间节点当做源,两端节点当做汇,对节点进行拆点,做一个流量为 的流即可。

评论

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