USACO题解(NOCOW整理版).pdf

USACO 题解 Chapter1 Section 1.1 Your Ride Is Here (ride) 这大概是一个容易的问题，一个 “ad hoc”问题，不需要特殊的算法和技巧。 Greedy Gift Givers (gift1) 这道题的难度相当于联赛第一题。用数组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 我们从左往右计算 如果necklace[i]=r ，rl[i]=rl[i-1]+1，bl[i]=0 ； 如果necklace[i]=b ， bl[i]=bl[i-1]+1，rl[i]=0 ； 如果necklace[i]=w ，bl[i]=bl[i-1]+1，rl[i]=rl[i-1]+1。 同理可以求出br ，rr 。 事实上不必使用动态规划，直接有哪些信誉好的足球投注网站亦可达到O(n) 。 把两个同样的项链放在一块，从头开始用两个变量(变量)a，b 记录自左方某点至目前为 止可搜集到之两种颜色珠子数，取途中所出现a+b 之最大值，遇颜色变换时再将b 指定给a 即可，代码十分简洁。 思路二：每次将串s 的首位移动至末位，每次均能从两头开始有哪些信誉好的足球投注网站，无需考虑环的问题。 思路三：无需考虑w 的。进行分类讨论，只有rb 和br 两种情况。 Section