某岛

… : "…アッカリ~ン . .. . " .. .
October 17, 2012

CodeChef October Challenge 2012

。。CC 题目真是越来越鬼畜了。。。实在是做不动啊。。。

Level 1:

Fierce Battles
签到题。。(略。。

Little Elephant and Order
。贪心。。(先考虑最多能放多少 7,再考虑最多能放多少 4 。。。

The New Scheme
。。递推数列。这个题神爆了。还是老段教我的啦 =w=。。。
http://user.qzone.qq.com/251815992/blog/1231945319#!app=2&via=QZ.HashRefresh&pos=1231945319
连数据都一样。。。果断扔个 Ruby 秒了。。

Event Organizer
。。区间调度问题。。
。。刚好是 ZOJ 月赛那枚 的简化版。。。暴力 DP 也没什么好说的。。

Need More Diamonds
。。对于一次询问,显然我们可以暴力 DP。。
dp[l][r] 表示取区间 (l, r) 位置的期望得分。。
然后询问比较多要预处理,大概就是。。
C[i][j表示长度为 i 时,第 j 项的系数。。
有了这张表就可以 O(n) 回答每个询问了。。
。。预处理的过程和开始的 DP 逻辑上也是等价的。。

Level 2:

Blade Master
。。题目比较不好总结。。大致做法大概就是暴力 Hash 记录循环节。(。。 yy 一下大概可以知道一定会出现循环节。。
。。。然后用小学数学把位移算出来就行了。。(注意中间的模拟过程要使用位运算优化。。

Team Formation
给定一个数列 ai、之后。。一个区间是合法区间、如果其中最大值和最小值之差 <= C 记 cand[i] 为长度为 i 的合法区间的数目。。每个询问 M,回答使得 cand[i] <= M、且 cand[i] 尽可能大的 i。。 (。若有多个解满足条件,则取 i 最小的。。。。 易知 cand[i] 单调递减。。然后用单调队列把这个数组搞出来二分查找就行了。(求出极大合法区间最后累和。。 。。方法类似上个月的单调队列题。。。

Level 3:

Ciel and password cracking
。。题目太长了。抓不住重点。。GG。。。。

Max Circumference
。。不会做。求人教。。

Bonus:

Maximum Sub-rectangle in Matrix
。。让你选定一些行和一些列,然后最大化所有这些属于交叉位置的得分。。
。。。我就写了个简单的贪心骗了点分就给扔一边了。
。(唉。。太没追求了。。

External link:

http://www.codechef.com/OCT12