Chapter1
Secon 1.1
Your Ride Is Here (ride)
这大概是一个容易的问题,一个“ad hoc”问题,不需要特殊的算法和技巧。
Greedy Gi Givers (gi1)
这道题的难度相当于联赛第一题。用数组 incom、outcom 记录每个人的收入和支出,
记录每个人的名字,对于送礼人 i,找到他要送给的人 j,inc(incom[j],outcom[i] div n),其中
n 是要送的人数,最后 inc(incom[i],outcom[i] mod n),最后输出 incom[i]-outcom[i]即可。
(复杂度 O(n^3))。
用 Hash 表可以进行优化,降复杂度为 O(n^2)。
Friday the Thirteenth (friday)
按月为单位计算,模拟运算,1900 年 1 月 13 日是星期六(代号 1),下个月的 13 日
就是代号(1+31-1) mod 7+1 的星期。
因为数据小,所以不会超时。
当数据比较大时,可以以年为单位计算,每年为 365 天,mod 7 的余数是 1,就是说每
过一年所有的日和星期错一天,闰年第 1、2 月错 1 天,3 月以后错 2 天。这样,只要先求
出第一年的解,错位添加到以后的年即可。
详细分析:因为 1900.1.1 是星期一,所以 1900.1.13 就等于(13-1) mod7+1=星期六。这
样讲可能不太清楚。那么,我来解释一下:每过 7 天是一个星期。n 天后是星期几怎么算
呢?现在假设 n 是 7 的倍数,如果 n 为 14,那么刚好就过了两个星期,所以 14 天后仍然是
星期一。但如果是过了 15 天,那么推算就得到是星期二。这样,我们就可以推导出一个公
式来计算。(n 天 mod 7(一个星期的天数)+ 现在日期的代号) mod 7 就等于现在日期的代
号。当括号内的值为 7 的倍数时,其代号就为 0,那么,此时就应该是星期日这样,我们
可以得出题目的算法:
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}
int b[8]={0}
a 数组保存一年 12 个月的天数(因为 C 语言中数组起始下标为 0,所以这里定义为
13)。
b 数组保存星期一到星期日出现的天数。用 date 记录目前是星期几的代号,然后用两
个循环,依次加上所经过的月份的天数,就出那个月是星期几,当然,要注意判断闰年!
知道了这个方法,实现起来就很容易了。
注意考虑闰月的情况。
最后注意要换行,否则会错误。
Broken Necklace (beads)
这道题用标准的搜索是 O(n^2)的,可以用类似动态规划的方法优化到 O(n)。
用数组 bl,br,rl,rr 分别记录在项链 i 处向左向右收集的蓝色红色珠子数。
项链是环形的,但我们只要把两个同样的项链放在一块,就把它转换成线性的了。
我们只要求出 bl,br,rl,rr,那么结果就是 max(max(bl[i],rl[i])+max(br[i+1],rr[i+1]))
(0<=i<=2*n-1)。
我们以求 bl,rl 为例:
初始时 bl[0]=rl[0]=0
我们从左往右计算