USACO Chapter 1 解题总结

USACO Chapter 1 解题总结

1.1.1 Your Ride Is Here

基本字符串操作，无压力。

1.1.2 Greedy Gift Givers

基础模拟题，弄明白题意，不怕麻烦，就OK了。

1.1.3 Friday the Thirteenth

自己的做法：三维数组代表年月日，400的数据范围不大，模拟走一下时间的流逝过程即可。时间复杂度O(N*12*31)，多好玩。

官方标程好像用到了一个神奇的公式，好像是什么蔡勒公式。

1.1.4 Broken Necklace

2*N的拆环，枚举断点找即可。在找的过程中先要解决那个万能的颜色珠子，如果起点是那个珠子，先累加答案，之后到头之后，再按规则找。

1.2.1 Milking Cows

问题模型：找被覆盖的最长区间，和没有覆盖的最小区间长度。自己用了一个基于扫描线的思想，遇到起点入栈，终点出栈，每遇到一个点就计算一下当前长度。注意细节即可。

1.2.2 Transformations

非常恶心的模拟题，让人想吐。不多说。

1.2.3 Name That Number

双文件读入注意一下，解决了这个问题然后正常模拟就可以。

1.2.4 Palindromic Squares

进制转换基础 + 判断回文数。

1.2.5 Dual Palindromes

进制转换。可以开一个这样的数组 base[]={“0123456789ABCDEFG”};

1.3.1 Mixing Milk

刚学不到2个月奥赛时候做的题，按照生活思路去贪心，注意贪心的题，一般开始都要先排个序。

1.3.2 Barn Repair

区间动态规划，同 “乘积最大”。注意细节即可。

1.3.3 Prime Cryptarithm

牛式，暴力枚举。注意数位就可以。

1.3.4 Combination Lock

正常循环加判断就行，话说自己一开始错是因为没有注意到这东西是个环，是位置差2，不是数值差2。

1.3.5 Wormholes

第一章的Boss，话说出来的有点早。搜索 + 剪枝 + 模拟，解题报告已经写了。

1.3.6 Ski Course Design

暴力枚举每个答案做就行。一开始想复杂了。

1.4.1 Arithmetic Progressions

话说这题倒是让自己语文觉得不好了，读了N多遍题才明白。

类比于搜索，要学习的还是剪枝的技巧，当我写完解题报告之后才发现自己有多么愚蠢。记住一个：你要找的等差数列的第一个数一定是这个双平方数集合中的某个BABY。然后枚举公差就可以。注意剪枝。

1.4.2 Mother’s Milk

BFS 搜索每一步的每种倒法，一定要注意不合法的倒法是不能够入队的，至于为什么，嘿嘿，自己试过就知道了。

1.5.1 Number Triangles

动态规划第一题，谁都是从这题开始DP的，放这里主要是让你学习一下滚动数组。

1.5.2 Prime Palindromes

回文质数，它给的两个性质很好，只有奇数可能是质数（2除外），先找回文数再找质数。如果是暴力的做法，你打个表，如果是正解，你就写个生成不同位数回文数的东西，然后判断素数就可以。话说我是打的表。

1.5.3 SuperPrime Rib

DFS，自己还傻傻的想枚举每个素数呢。不过这个题和上个题倒是让我复习了一下筛法。记住一个性质，如果是肋骨数，那么第一位一定是 2、3、5、7，最后一位一定是1、3、7、9。信不信由你。反正我信了。