usaco(train)解题报告

《usaco(train)解题报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、USACO(Train)部分Chapter1Section1.1YourRideIsHere(ride)这大概是一个容易的问题，一个“adhoc”问题，不需要特殊的算法和技巧。GreedyGiftGivers(gift1)这道题的难度相当于联赛第一题。用数组incom、outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j，inc(incom[j],outcom[i]divn)，其中n是要送的人数，最后inc(incom[i],outcom[i]modn)，最后输出inc

2、om[i]-outcom[i]即可。（复杂度O(n^3)）。用Hash表可以进行优化，降复杂度为O(n^2)。FridaytheThirteenth(friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1)mod7+1的星期。因为数据小，所以不会超时。当数据比较大时，可以以年为单位计算，每年为365天，mod7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。这样，只要先求出第一年的解，错位添加到以后的年即

3、可。详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1)mod7+1=星期六。这样讲可能不太清楚。那么，我来解释一下：每过7天是一个星期。n天后是星期几怎么算呢？现在假设n是7的倍数，如果n为14，那么刚好就过了两个星期，所以14天后仍然是星期一。但如果是过了15天，那么推算就得到是星期二。这样，我们就可以推导出一个公式来计算。(n天mod7（一个星期的天数）+现在日期的代号)mod7就等于现在日期的代号。当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，

4、我们可以得出题目的算法：inta[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}intb[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。b数组保存星期一到星期日出现的天数。用date记录目前是星期几的代号，然后用两个循环，依次加上所经过的月份的天数，就出那个月是星期几，当然，要注意判断闰年！知道了这个方法，实现起来就很容易了。注意考虑闰月的情况。最后注意要换行，否则会错误。BrokenNecklace(beads)这

5、道题用标准的搜索是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[

6、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的首位移动至末位，每

7、次均能从两头开始搜索，无需考虑环的问题。思路三：无需考虑w的。进行分类讨论，只有rb和br两种情况。Section1.2MilkingCows(milk2)有三种思想。离散化（其实就是进行了优化的搜索而已）按照开始时间升序排序，然后从左到右扫一遍，复杂度是O(nlogn+n)的（排序+扫一遍，用堆、合并、快排都可以）。所谓从左到右扫一遍，就是记录一个当前区间，[tmp_begin,tmp_end]。如果下一组数据的begin比tmp_end的小（或相等），则是连接起来的，检查这组数据的end，取max{

8、end,tmp_end}。如果下一组数据的begin比tmp_end的大，则是相互断开的，整理本区间，ans1取max{tmp_end-tmp_begin,ans1}。ans2取max{begin-tmp_end,ans2}。看不懂？去看看PASCAL或C的范例程序就明白了。线段树本题的规模是1e6，简单的模拟是O(nm)(n是奶牛个数，m是最大范围)的，会超时。（但是本题数据远没有描述的那么恐怖，直接模拟也是很快的）。用线段树统计区间，复