USACO大量月赛题题解

题号

题目和难度

提示

勘误或注意事项

第0题

★☆☆☆☆ 负二进制 (THE MORONIC COWMPOUTER, 2006 FEB)

和其他转进制一样做,要注意mod出来可能是负的

第1题

★★☆☆☆ 数的幂次 (CRUEL MATH TEACHER, 2009 FEB)

快速幂套高精度即可

第2题

★★★☆☆ 分数变小数 (FRACTIONS TO DECIMALS, 1993 QUALIFYING ROUND)

循环判断,用数组存储每次的余数,当余数出现过一次就停止

输出格式:每行只输出76个字符

第3题

★★★☆☆ 丑数 (HUMBLE NUMBERS, CHAMPIONSHIP)

假设已算出前n个,第n+1个一定是前n个中的一个和一个素数的积

第4题

★☆☆☆☆ 公司利润 (PROFITS, 2011 JAN)

最大连续和

第5题

★☆☆☆☆ 接住苹果 (APPLE CATCHING, 2004 NOV)

dp[n][k]为前n个点正好移动k次的答案

第6题

★★☆☆☆ 方形牛棚 (BIG BARN, 1997 FALL)

用平方时间算出每个点在左方和上方的限制,然后就能DP了

第7题

★★★☆☆ 滑雪课程 (SKI LESSONS, 2009 OPEN)

将课程按结束时间排序,预处理能力值x的情况下最小时间,dp(i,j)为时间为j,前i个课程的答案

第8题

★★★☆☆ 滑雪比赛 (BOBSLEDDING, 2009 DEC)

将时间排序,每个弯角考虑：前一弯的速度,自己的限速,和后面“刹不住”,递推时顺便算答案

第9题

★☆☆☆☆ 自私的奶牛 (SELFISH GRAZING, 2009 DEC)

经典的任务调度问题,按结束时间排序即可

第10题

★★☆☆☆ 重排干草 (HAYBALE RESTACKING, 2012 MAR)

代数分析然后取中位数

同Uva 11300 BZOJ 1045

第11题

★★★☆☆ 奶牛集体照 (COW PHOTOGRAPHY, 2011 DEC)

如果一头牛在另一头牛前面,则它至多在另一头前面2次,以此排序

第12题

★★★★☆ 奶牛集会 (MOOFEST, 2004 OPEN)

V和X都做排序,按V从大往小扫,用数据结构计算x比它小的和与比它大的和

第13题

★☆☆☆☆ 购买饲料 (BUYING FEED 2, 2010 JAN)

以距离+价格为关键字排序

第14题

★★☆☆☆ 保护花朵 (PROTECTING THE FLOWERS, 2007 JAN)

s/t的比值为关键字排序

第15题

★★★☆☆ 奶牛杂技 (COW ACROBATS, 2005 NOV)

w+s为关键字排序

第16题

★★★★☆ 二道工序 (THE MILK QUEUE, 2006 OPEN)

排序关键字 return a.a + b.b + max(a.a, b.b) < a.b + b.a + max(a.b, b.a);

第17题

★☆☆☆☆ 括号序列 (BEST PARENTHESIS, 2011 FEB)

根据题目定义,维护一个栈即可

旧版的翻译有问题,没有说要mod多少

第18题

★★☆☆☆ 向右看齐 (LOOK UP, 2009 MAR)

倒序维护一个单调队列再正序输出

第19题

★★★☆☆ 雄伟的山峦 (MOUNTAIN MAJESTIES, 2002 OPEN)

按起点排序并去除完全覆盖的部分，然后进行扫描，分成两个三角形相交和相离讨论。

题目描述没有提到长度单位，自己随便定一个单位好了

第20题

★☆☆☆☆ 建造道路 (BUILDING ROADS, 2007 DEC)

Kruskal 把已经建好的用并查集合并并计算出大小,有更好的办法,Prim将连通边长设为0

第21题

★★☆☆☆ 奶牛打井 (WATERING HOLE, 2008 OCT)

增加一个点,到每个节点的距离为打一口井的耗费,求mst

第22题

★★★☆☆ 奶牛施工队 (EARTHQUAKE, 2001 OPEN) 

将成本除以V-1减去收益,转化为最大比例生成树

第23题

★★☆☆☆ 翻转棋 (FLIPTILE, 2007 OPEN)

枚举第一行即可

最优解指翻转次数最小的解

第24题

★★★★☆ 电灯 (LIGHTS, 2009 NOV)</