公告

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

第四场

淘宝流量分配 

枚举最后一个任务是否选择,之后根据最后一个任务是否选择来分别求解前面序列能选取的最大值即可。

遗失的支付宝密码

子问题 1 

暴力枚举所有答案,然后删掉不合法的字符串,统计个数即可。

子问题 2 

只要知道了每个位置的等价关系,我们事实上就确定了这个字符串。一种想法是直接枚举每个位置的相等关系,然后计数,但是这样复杂度是 的,显然会 TLE。另一个想法是容斥,注意到只有长度是偶数的前缀才会成为 square,大概有 个。就可以 枚举哪些前缀一定是 ,做容斥。答案就是 至少有 个前缀是 square 至少有 个前缀是 square …。

题外话:其实答案最后答案的结构显然是 这样的,系数 只和 有关,于是可以本地打表出来。这样就可以很快解决这个 case。

子问题 3 

考虑 表示当前处理完前 个偶数长度的前缀,并且第 个一定是一个 square, 后面那些位置都不是 square,当前所有位置的等价关系是 的方案数。

那么如果不考虑 后面那些位置都不是 square,方案数是 ,其中 是当前状态中联通分量的数目,考虑定义只需要减去 即可。这样直接算 的状态应该会爆炸。注意到可以将 做最小表示,通过简单的计算发现 时最多只有 种不同的状态,在这个时限下用 map 搞搞就好了。

第五场

腾讯的一笔画游戏 

这张图实际上提示了正确解法,对于最优解,答案为内圈周长的 加上除了内圈的所有圈周长的

腾讯的新游戏

子问题1 

模拟每次交换操作,然后枚举挑战护卫队的顺序(一共 种顺序)计算需要的初始防御力值。时间复杂度

子问题2 

模拟每次交换操作。然后计算出单独挑战每只护卫队分别需要多少初始防御力值,按照这个从小到大挑战护卫队即可。时间复杂度

子问题3 

同样按照中等版本的贪心方法。使用 splay 来维护每只护卫队的队内顺序以及护卫队们的排列次序即可。时间复杂度

第六场

微软编辑器的代码高亮 

考察细节的题目,注意空串(只包含引号)、多串、引号不匹配、非法转义字符等情况。

微软的员工福利

子问题1 

枚举每个节点选的显示器,计算一下代价即可。时间复杂度
子问题2 

考虑在树上进行动态规划。:节点 选了颜色 的子树 的最大净价值和。枚举最大值和最小值来进行转移。时间复杂度

子问题3 

表示节点 选了显示器 的子树 的最大净价值和。注意到极差的取值只有 种,那么转移时枚举极差,然后枚举最大值的同时顺便维护在这个取值区间内的最优决策(较大提升的显示器不在区间内的话,就一定要把较小显示器选上;如果来自同一子树的两个显示器都在区间内,贪心选 值较大的那个)。决策点至多 个,可以 two pointers 维护。时间复杂度

2 comments

  1. 能不能解释一下微软的员工福利子问题2枚举最小值最大值怎么做到时间复杂度 O(n^3)解决问题呢?

评论

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