1.2 beads Broken Necklace
每次都把遇到的第一颗珠子作为标准珠，处理珠子直到遇到异色珠(白色为同色)；处理一颗珠子就把珠子删掉，防止重复计算；注意在某一点断开后，可能遇到白色珠，那么就不停地读，直到遇到蓝色或红色珠，把标准珠修改为遇到的珠子，继续操作。
1.2 pprime Prime Palindromes
从开始数的位数，到结束数的位数，通过对位数奇偶性的判断，来决定最后生成回文数的方式；通过对回文数左边一半的枚举，就能够生成整个回文数(注意奇偶)；用简单的判质即可解决。
1.3 barn1 Barn Repair
可以用贪心，将连在一起的牛看作整体，把空白的地方看作一个整体，将整个牛-空串的两端的空去掉后，把空排序，把最小的空用栅栏把两边的牛群联在一起，如此重复操作，直到满足规定；我是用DP解的，把f[ i ][j][k]定义用i块木板从第j个牛群覆盖到第k个牛群的最少长度。
1.4 checker Checker Challenge
对每行穷举方案并对该点所在列标记，以防重复的常规算法上改进。把最长的那条对角线标记为0号对角线，在其右边与其平行的对角线号码递增，反之递减。如此即可完成对角线的标记，完成第一步优化；利用对称性，可以将第一行只枚举左边一半的情况，因为其实枚举右边也是一样的，完成第二步优化；搜两次，第一次搜到三个解即退出，第二次不记录方案再搜一次，可以大幅提高效率，完成最后一步优化。[剪枝]
1.4 sprime Superprime Rib
对第一位穷举判质，加入第二位穷举判质…… 注意除了第一位可以放个2外，不允许有偶数，因此实际搜索量很小.....
2.1 castle The Castle
把地图存下来，然后用flood fill将每个格子染色，记下最后颜色总数，和每个颜色的格子数。再把每个房间看作点，相邻的两个面积相加最大的颜色纪录下来，然后按照一定顺序找隔离这两个房间的墙即可。
2.1 contact Contact
读入的时候只要读入最长子串长的字符串，然后对这个字符串里最后的长度为i的符合条件的子串登记。在对01串描述时，要在串前加上一个1再转化为十进制，那么串就能唯一了。
2.1 frac1 Ordered Fractions
P1/Q1 < (P1+P2)/(Q1+Q2) < P2/Q2 这个非常有用，中间的分数必然是最简的。对每个分数记录前驱的编号和后继的编号，输出是用这种类似指针的玩意到处乱跑。
2.1 rect1 Shaping Regions
把矩形的各条边延长，那么大白纸就被分成好多小块。以垂直的直线建立线段树，对相邻的两条水平的直线之间的区域进行操作，每次都选用一个矩形，如果该节点已覆盖的值小于col[ b ]-col[a]，那么这个节点区域还没有被完全覆盖，如果左子树和矩形有重合，那么访问左子树，右子树也一样，如果该节点的区域完全被矩形覆盖，那么该节点的以覆盖值就修改，记得其祖先也要修改，同时将该颜色的面积加上这一块面积。
2.2 milk2 Milking Cows
我们可以将每个农民开始的时刻和结束的时刻都看作点，这两点之间有线段，然后可以找出一条条的相互重叠的线段，总的就是一条长线段，最后就是线段-空白串，找出其中最长的线段和空白即可。
2.2 preface Preface Numbering
把IVX, XLC, CDM, M 如此分成四组，这四组的操作大同小异。
2.2 runround Runaround Numbers
把每位的数看作一个点，枚举这个点的值，如果该值并未使用过，并且该点在等于该值时的下一个点并未访问过，那么就可以继续搜。
从和开始数同样位数的数开始搜索，找到满足条件的就更改，如果在该位数未找到符合条件的数，那么就可以输出，否则位数加一，继续。
2.3 clocks The Clocks
因为每个操作最多执行3次，所以可以用9重循环解决所有操作的情况，对于钟的情况的存储，不要用状态表示了，直接用字符串或者数组存储，可以省掉转化的环节。把九种操作预置常数，可以使程序简洁。
2.3 comehome Bessie Come Home
最短路。注意’A’和’a’是两个不同的农场.................
2.3 maze1 Overfencing
出口毗邻的格子步数为1，向外扩展，倒推出所有格子的最短用时。找出最大
2.4 humble Humble Numbers
用三个数组，一个数组存已求得的顺序丑数，一个数组存可用的素数，一个数组存对应的素数乘以哪一个已求得的丑数能得到最小的，且未求得的丑数的编号。因为一个丑数一定是一个丑数乘以一个丑数得到的，所以这种方法是可行的。
2.4 inflate Score Inflation
无限背包。用一个数组纪录就可以了。在读入数据的时候，要把一些数据给排除：
时间用得比前面的数据大于等于，得分却小于等于的，不做修改；时间用得比前面的数据小于等于，得分大于等于的，把前面数据改称刚读入的。
2.5 kimbits Stringsobits
设所求的串是n位有m个1的01串。利用组合数可以算出长度为i的01串中1的数目为j的情况，从而进一步算出，从i个0的01串，到最大的长度为i，j个1的01串（即11……10……0）的个数，如果要求的k大于这个值，那么所求串在第i位上必然是1，那么01串就有至多(m-1)个1未确定。
看一下样例，10011的编号计算：第五位(从右往左看)为1，因此加上0000~1111中满足条件的串的个数15，为15，确定10000为第16个数；只要知道00~11里有多少个符合条件的串就可以了；第二位为1，因此加上0~1中满足条件的串的个数2，为17；第一位为1，因此加上0~1种满足条件的个数2，为19，得解。
如此的逆过程就是问题的求解。
2.5 sort3 Sorting a Three-Valued Sequence
考虑两种情况，一种是A在B的位置上，B也在A的位置上，将这两者调换无疑是最优的，另一种就是A在B的位置上，B在C的位置上，C在A的位置上，这需要每组作两次调换。用一个二维数组记录数字A在数字B的位置上的个数。第一种情况的调换次数可以求min{g[a, b], g[b, a]}。如果第二种情况存在，根据循环时，错位数组的差值的传递性，任意找一个g[a, b]，用 | g[a,b] - g[b,a] | *2 即可求得.
3.1 lamps Party Lamps
其实枚举量是很小的，总共只需要考虑6盏灯，因为由于操作的情态，第i盏灯的情况和第(i + 6)盏是一样的。另外，次数再多的操作，无外乎不操作、1号操作、2号操作、3号操作、4号操作、(1 + 4)号操作、(2 + 4)号操作、(3 + 4)号操作八种。可以通过两次操作还原状态，亦可以通过三次操作还原状态。所以只需要判断操作数是为0、1、2、3 或更高即可。
3.2 calfflac Calf Flac
在读入的时候储存两张表，一张是原文，一张是被upcase的字母，并记录该字母是原文的第几个字符。只需要从字母表中的第一个开始，枚举该字母为中心展开的最长的回文长度，以及以该字母及后面一个字母为中心展开的最长的回文长度。找出最大的回文长度及其中心，然后还原输出。
3.2 game1 A Game
Opt[ i ][ j ] = max{a[ i ] - Opt[i + 1][ j ], a[ j ] - Opt[ i ][j - 1]}
其中Opt[j]指当操作[i..j]个数字的时候，能获得的最优差。
3.2 range Home on the Range
在判断过程中可以用true\false 代替 0\1，在求边长为k的正方形数时，可以简单的判断g[ i ][ j ], g[i + 1][ j ], g[ i ][j + 1], g[i + 1][j + 1]是否都为true，如果都是true，不仅要计数器加1，而且g[ i ][ j ]也要赋为true。因为边长为k + 1的正方形可以看作是四个相重叠的边长为k的正方形。如果其中一个边长为k的正方形不存在，那么这个边长为k + 1的正方形也是不存在的。这样整个问题就又回归到边长为2的情况下，时间复杂度比单纯判断低多了。
3.3 camelot Camelot
枚举所有骑士相遇的可能点、枚举所有骑士和国王相遇的可能点。所谓可能点，就是骑士能够到达的点。对可能点枚举的范围可以缩小。所有骑士相遇的可能点应该是在骑士纵横坐标的平均值附近，骑士和国王相遇的可能点应该是在国王附近。在计算路程的过程中，如果值不比以求得的小，那就趁早结束计算。
在计算最短路的过程中，可以从每个骑士的出发点开始，向外扩展，就是宽搜咯。
国王的最短路，是目的地的纵坐标与出发地的纵坐标之差 和 目的地的横坐标与出发地的横坐标之差 的 最大值。
3.3 concom Controlling Companies
我用了三个二围数组，g[ i ][ j ]表示i公司拥有j公司的股权，t[ i ][ j ]表示对于i公司已经统计了其子公司j公司的直接子公司的拥有股权，h[ i ][ j ]表示j公司是i公司的子公司。
3.3 packrec Packing Rectangles
矩形的旋转其实只是两种情况，不旋转或旋转90度。由于每个矩形都可以旋转，所以对于每个排放顺序和方式来说，都会派生出16种情况。对于每个排放方式都会派生出24种情况。枚举一下就行了。至于第六种，又会有N多情况，看oibh吧...
3.4 cowtour Cow Tours
先用一下floyd，底下枚举所有尚未相通的点。那么当前的直径为这两点辐射出的最长路径和两点距离和。但事实上不完全正确，如果其中一个牧场直径非常大，甚至大于这个求得的值，那么当前的直径应该就是这个大牧场的直径。
3.4 fence4 Closed Fences
第一个任务很好完成，只需要判断两个不相邻的边有无公共点即可。第二个任务可以把观察点与每个点连线，如果连线与某条边相交或重合，那么与观察点连线的线段是不能看见的，于是就会简化很多。
USACO的简析：用类似蒙特卡罗的方法找射线，第一个与之相交的线段是可见的。射线的生成是通过观察点和各端点、各边中点的连线。虽然觉得不怎么对，但没找到反例。
我爸的想法：如果观察点在多边形外，可以将多边形最上方的点与之连线，最下方的点与之连线，两点再连线，这个三角形区域后的都是看不见的，可以不考虑，问题规模就很小了。
