USACO题解(NOCOW整理版).doc

USACO 题解 USACO 题解是美国计算机奥林匹克（USACO）竞赛的题解集合，本文档提供了多个题目的解释和解决方案，涵盖了 Greedy Algorithm、Hash 表、动态规划、搜索等多种算法和技术。 Chapter 1 Section 1.1 Your Ride Is Here (ride) 这道题是一个容易的问题，使用 Greedy Algorithm 可以解决。该题可以使用数组 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)。 Chapter 1 Section 1.1 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)。 Chapter 1 Section 1.1 Friday the Thirteenth (friday) 这道题的解决方案是使用模拟运算，按照月为单位计算，记录每个月的 13 日是星期几，然后输出结果。该算法的复杂度较低，适合小规模数据。当数据比较大时，可以以年为单位计算，每年为 365 天，mod 7 的余数是 1，就是说每过一年所有的日和星期错一天，闰年第 1、2 月错 1 天，3 月以后错 2 天。这样，只要先求出第一年的解，错位添加到以后的年即可。 Chapter 1 Section 1.2 Broken Necklace (beads) 这道题可以使用搜索来解决，使用数组 bl、br、rl、rr 分别记录在项链 i 处向左向右收集的蓝色红色珠子数。项链是环形的，但我们只要把两个同样的项链放在一块，就把它转换成线性的了。我们只要求出 bl、rl、br、rr，然后计算 max(max(bl[i],rl[i])+max(br[i+1],rr[i+1])) (0<=i<=2*n-1)。事实上不必使用动态规划，直接搜索亦可达到 O(n)。 Chapter 1 Section 1.2 Milking Cows (milk2) 这道题有三种思想。第一种思想是离散化（其实就是进行了优化的搜索而已），按照开始时间升序排序，然后从左到右扫一遍，复杂度是 O(nlogn+n) 的（排序+扫一遍，用堆、合并、快排都可以）。第二种思想是使用动态规划，记录一个当前区间，[tmp_begin,tmp_end]。如果下一组数据的 begin 比 tmp_end 的小（或相等），则是连接起来的，检查这组数据的 end，取 max{end,tmp_end}。如果下一组数据的 begin 比 tmp_end 的大，则是相互断开的，整理本区间，ans1 取 max{tmp_end}。