USACO题目
T1：贪婪地送礼者
枚举每个人，把钱送出去就好了，然后统计答案即可。
T2： [USACO1.1]黑色星期五Friday the Thirteenth
13号又是一个星期五。13号在星期五比在其他日子少吗?为了回答这个问题,写一个程序，要求计算每个月的十三号落在周一到周日的次数。给出N年的一个周期，要求计算1900年1月1日至1900+N-1年12月31日中十三号落在周一到周日的次数，N为正整数且不大于400.
这里有一些你要知道的:
1、1900年1月1日是星期一.
...
此题直接模拟即可。
需要注意的是对世纪年的特判。包括对当年和以后年（比朴素计算方法少一个闰年）的处理。
T3：坏掉的项链
假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大数目的珠子
白色可以当做红色或蓝色。
注意答案永远不能大于珠子总数的边界条件。
注意从断开出就是白色的特殊情况。
T4:命名那个数字
注意深搜的边界条件。
T5:挤牛奶
差分即可。注意区间的开闭。
T6:方块转换
模拟。
T7:回文平方数
注意输出格式。
注意转换到高进制要引入字母。
知识点：进制转换，检验回文数。
T8:双重回文数
同上题。
T9:等差数列
对于一个等差数列，只要枚举前两项，后面的项直接检验即可。
注意剪枝，如果按照当前的d到第n项大小一定爆了就直接break。
T10:母亲的牛奶
注意数据范围，直接搜索即可。
为了防止死循环，加入判重即可。
T11:数字三角形
dp入门题。
T12:回文质数
枚举即可。
T13:特殊的质数肋骨
知识点:质数筛。
注意剪枝，不用枚举每个数。
T14:顺序的分数
输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。
这有一个例子，当N=5时，所有解为：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。
注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。
这里提供三个思路
使用gcd判断是否互质，直接枚举即可。
使用map记录分数值，依次判断前面是否枚举过。可以证明的是所有可以约分的分数的分数值前面必然已经枚举过了。（注意数组大小要开够）
数学方法。（法雷数列） \[ 不妨设最简真分数\frac{a}{b}<\frac{c}{d}\\ 令 m=a+c, n=b+d.可以证明的是\frac{a}{b}<\frac{m}{n}<\frac{c}{d}.\\ 且\frac{m}{n}是个最简分数.\\ 对于不等式的证明，考虑使用做差.\\ \frac{a+c}{b+d}-\frac{a}{b}=\frac{ab+bc-ab-ad}{b(b+d)}=\frac{bc-ad}{b(b+d)}\\ 由十字相乘式,由\frac{a}{b}<\frac{c}{d}可导出ad<cb.\\ 因而\frac{a+c}{b+d}>\frac{a}{b}\\ 同理可证\frac{a+b}{b+d}<\frac{c}{d}\\ 对于\frac{m}{n}是最简分数的证明我们考虑使用反证法.\\ 假设\frac{a+c}{b+d}不是最简分数，则必然可以构造.\\ \frac{x(a_0+c_0)}{y(b_0+d_0)}其中x=gcd(a,c),y=gcd(b,d)\\ 且\gcd(x,y)\neq1\\ 将式子展开\frac{x*a_0+x*b_0}{y*c_0+y*d_0}\\ 有a=x*a0,c=y*c_0\\ 易得\gcd(x*a_0,y*a_0) \neq 1\\ 但是\gcd(a,b)=1\\ 矛盾，假设不成立，得证。 \]
T15:三值的排序
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1，2和3。我们用交换的方法把他排成升序的。
写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数
1 <= N <= 1000
爆搜肯定是不行了。
考虑计算排序交换次数的通用思路，即把当前序列与排好的序列比较。
朴素想法，考虑所有情况。
- 一个数字1跑到了区间2，同时区间2中的一个数字2跑到了区间1
- 一个数字1跑到了区间3，同时区间3中的一个数字3跑到了区间1
- 一个数字2跑到了区间3，同时区间3中的一个数字3跑到了区间2
- 一个数字1跑到了区间2，同时区间2中的一个数字2跑到了区间3，区间3中的一个数字3跑到了区间1
- 一个数字1跑到了区间3，同时区间3中的一个数字3跑到了区间2，区间2中的一个数字2跑到了区间1
对于情况1,2,3明显是最优方法，只需要交换一次就可以解决两个数字。
而情况4,5复杂一些，需要用两次交换解决3个数字。
于是我们可以贪心的找前三种情况，然后计算还没有归位的数字的数量，乘以2/3即可。
考虑一下简化方案。记目标区间中都是1的部分为区间A，都是2的部分为区间B，都是3的部分为区间3。
我们只用考虑两个区间即可。因为如果这两个区间被安排好了，剩下一个区间自然就对了。我们这里考虑A,B两个区间。
对于A,B两个区间中，所有的3都是要换进区间C中的，这是一个铁逻辑，所以此时的每一次交换都是一次有效且必要的交换。
考虑区间A。如果是1则可以不管，如果是2则和区间B中的1交换。
此时应该意识到有两种情况，即区间A中的2和区间B中的1哪个多。
应该想到的是，在我们把区间C安排好时，区间AB中就只有1和2了。
之前我们在处理C区间时，策略应当是尽量把1换到A区间，2换到B区间，现在我们考虑这三种情况。
- 刚好，所有的