下载文档原格式
在USACO比赛中，数论相关题目一直是考察的热点之一。
数论作为数学的一个重要分支，涉及整数的性质和关系，常常能够运用到算法设计和问题求解中。
本文将从简单到复杂，由浅入深地探讨USACO比赛中的数论相关题目，帮助你更深入地理解这一主题。
1. 简单级别：在USACO比赛的入门级题目中，通常会涉及一些基本的数论知识，比如素数、最大公约数、最小公倍数等。
给定两个整数，要求求它们的最大公约数或最小公倍数；或者判断一个数是否为素数等。
这些题目往往需要运用到基本的数论算法，比如欧几里得算法求最大公约数、筛法求素数等。
2. 中等级别：在中等级别的USACO比赛题目中，数论相关的内容会更加复杂和深刻。
可能涉及到模运算、同余方程、欧拉函数、费马小定理等知识点。
题目可能会要求实现一些高级的数论算法，比如快速幂算法、扩展欧几里得算法等。
这些题目往往需要更深入的数论知识和算法功底，能够更好地理解和运用复杂的数论知识。
3. 高级级别：在USACO比赛的高级题目中，数论相关的内容往往会与其他算法知识结合，考察的角度也更加灵活多样。
题目可能会涉及到数论与图论、动态规划、贪心算法等内容的结合，难度较大。
此时，除了对数论知识的深刻理解外，还需要具备较强的问题建模能力和算法设计能力。
总结回顾：通过以上的分析，我们可以看到，USACO比赛中的数论相关题目，涵盖了不同难度级别的内容，从简单的基本算法到复杂的高级问题解决方案，都需要对数论知识有较为全面、深刻的理解。
在备战USACO比赛时，我们要加强对数论知识的学习和掌握，尤其要注重基础知识的打牢和算法能力的提升。
个人观点和理解：我个人认为，数论是一门非常有趣和有挑战性的数学分支，在USACO 比赛中能够有机会运用数论知识解决实际问题，对于提高自己的数学建模能力和算法设计能力都是非常有益的。
我会在备战USACO比赛的过程中，加强对数论相关知识的学习和实践，努力提高自己的数论解题能力。
通过以上分析和讨论，我们对USACO比赛中的数论相关题目有了更全面、深刻的理解。
usaco例题USACO（美国计算机奥林匹克竞赛）是美国最具影响力的计算机竞赛之一，旨在培养学生的计算机科学和编程能力。
USACO例题是该竞赛中的一部分，通过解决这些例题，学生可以提高他们的算法和编程技巧。
下面我们来看看一个USACO例题。
题目：奶牛的旅行问题描述：农夫约翰有N头奶牛，编号为1到N。
这些奶牛之间有一些道路相连，每条道路都是双向的。
约翰想知道，如果他从某个牧场出发，经过一些道路，最终能够到达所有的牧场，他至少需要经过多少条道路。
输入格式：第一行包含两个整数N和M，分别表示奶牛的数量和道路的数量。
接下来的M行，每行包含两个整数A和B，表示编号为A和B的奶牛之间有一条道路相连。
输出格式：输出一个整数，表示约翰至少需要经过的道路数量。
示例输入：5 41 22 33 44 5示例输出：4解题思路：这是一个典型的图论问题，我们可以使用深度优先搜索（DFS）来解决。
首先，我们需要构建一个图的表示，可以使用邻接矩阵或邻接表来表示。
然后，我们从任意一个牧场开始，进行深度优先搜索，记录经过的道路数量。
最后，我们统计所有牧场中经过的最大道路数量，即为约翰至少需要经过的道路数量。
代码实现：```pythondef dfs(graph, visited, start):visited[start] = Truecount = 0for neighbor in graph[start]:if not visited[neighbor]:count += 1count += dfs(graph, visited, neighbor)return countdef minimum_roads(N, M, roads):graph = [[] for _ in range(N+1)]for road in roads:a, b = roadgraph[a].append(b)graph[b].append(a)min_roads = float('inf')for i in range(1, N+1):visited = [False] * (N+1)min_roads = min(min_roads, dfs(graph, visited, i)) return min_roadsN, M = map(int, input().split())roads = []for _ in range(M):a, b = map(int, input().split())roads.append((a, b))print(minimum_roads(N, M, roads))```这个例题中，我们使用了邻接表来表示图，通过深度优先搜索来遍历图中的节点。
2022usaco题目解析2022年的USACO比赛（UnitedStatesofAmericaComputingOlympiad）即将到来，参赛者们需要充分准备，以获得更好的比赛成绩。
为此，本文将重点就USACO 2022年题目进行解析，希望能给参赛者带去帮助。
USACO 2022年题目主要分为五大类：算法设计，数据结构，编程技巧，系统编程和数学分析。
其中算法设计包括模拟，搜索，图论，动态规划，贪心算法等。
由于算法设计是USACO考试中最重要的部分，因此参赛者需要尤其重视。
数据结构则包括基础的树，路径，栈，队列，哈希表，图，字符串，堆，红黑树等。
以此为基础，参赛者可以运用诸如递归，迭代，前缀树，双指针，Trie树等数据结构来解决有关问题。
编程技巧方面，USACO考试偏好高效算法，例如处理极大的输入，极小的延迟，空间复杂度低等。
另外，考查省时高效的编程语言，例如C++，Java，Python，Go等。
系统编程方面，考察基本的编程技巧，例如多线程，锁，网络编程，内存管理等。
同时，还会从操作系统，文件，Strings，多终端，网络等方面考查参赛者的知识积累。
此外，还会考察开发工具，例如Git，Kubernetes，Docker等。
最后，USACO 2022年考试还会考察数学分析方面的知识，例如概率论，统计学，线性代数，圆曲线等。
参赛者在此领域要有扎实的基础，并了解大数定理等关键知识。
总之，USACO 2022年考试非常具有挑战性，考查涉及面广泛，参赛者需要充分准备，集中精力复习算法，数据结构，编程技巧，系统编程和数学分析，才能取得更好的比赛成绩。
以上就是有关USACO2022年题目解析的全部内容，希望能够给参赛者带去帮助，为获得更好的比赛成绩作准备。
usaco题目集usaco题目集是一系列来自美国计算机奥林匹克竞赛（USACO）的编程题目。
USACO是一项面向中学生的计算机竞赛，旨在培养学生的计算机科学和算法设计能力。
该竞赛涵盖了广泛的主题，包括数据结构、图论、动态规划和搜索等。
usaco题目集的难度分为四个级别：铜牌、银牌、金牌和白金。
每个级别的题目都有一定的难度和要求。
通过完成这些题目，学生们可以提高他们的编程技巧和解决问题的能力。
usaco题目集的题目非常有趣和有挑战性。
每个题目都描述了一个具体的问题，学生需要设计和实现一个程序来解决这个问题。
这些问题有时与现实生活中的情境相关，有时与抽象的数学和逻辑问题相关。
例如，一个题目可能要求学生计算某个数列的前n项之和，另一个题目可能要求学生确定给定图形的面积。
解决这些问题需要学生们运用他们所学的算法和数据结构知识，并且具备良好的编程技巧。
usaco题目集的特点之一是其严格的评判标准。
每个题目都有一组测试数据，用于验证学生程序的正确性和效率。
程序需要在规定的时间内给出正确的输出结果，否则将被判定为错误。
这种评判标准旨在培养学生们高效率和准确性的编程能力。
通过解决usaco题目集中的问题，学生们可以提高他们的计算机科学能力，并为将来的学习和工作做好准备。
这些问题不仅可以让学生们巩固他们所学的知识，还可以培养他们的创造力和解决问题的能力。
此外，usaco题目集还提供了一个平台，让学生们可以与全美范围内的同龄人交流和竞争。
每年，usaco组织全美性的比赛，邀请来自各州的优秀选手进行角逐。
这些比赛不仅考察学生的编程能力，还促进了学生们之间的交流和合作。
总之，usaco题目集是一个很好的学习和提高编程能力的资源。
通过解决这些问题，学生们可以提高他们的计算机科学和算法设计能力，并为将来的学习和工作做好准备。
这些问题的多样性和挑战性，使得usaco题目集成为中学生们学习编程的重要工具。
我的USACO总结Congratulations!You have finished all available material.Chapter1DONE2008.12.16Getting startedChapter2DONE2008.12.24Bigger ChallengesChapter3DONE2009.01.15Techniques more subtleChapter4DONE2009.02.03Advanced algorithms and difficult drillsChapter5DONE2009.02.17Serious challengesChapter6DONE2009.02.20Contest Practice花了差不多四个月把USACO做完了，感觉收获很大，它就像一个私人教练能督促你学习一样，对于一个oier来说，USACO绝对是一个不可不做的经典OJ，为了整理一下知识点也当是一次巩固，便写下了这篇总结，以总结一下自己的疏漏，也希望能帮助到别人。
--湖南南县一中czz一、枚举枚举是我们用的比较多的一种算法，编程简单是它的优点，而时间效率低则是它的致命缺点，不过很多题目通过合理的优化比如减小枚举量等来优化算法。
The Clocks是第一道需要优化的枚举题，首先由于这题有9个时钟，而且每个的移动次数也不清楚，似乎无从开始，不过经过研究发现对于一个时钟如果移动四次就会便相当于没有移动，因此我们只需要枚举每个钟的四种状态共9^4共6561种状态，这样就不会超时了，不过如果进一步研究这个题目发现移动方案之间是有约束的，打个比方，A时钟由三种移动方案确定，如果其中的两种方案的次数已经知道，那么第三种方案也就会确定，因此我们只要枚举前三个方案的次数其他的便可以递推出来，状态只有4^3个，效率无疑大大提高。
Arithmetic Progressions这题由于题目要求按b升序排列，所以我们习惯性得把b放在外循环而a放在内循环，这样做加上剪枝后也会超时，由于剪枝时按a 剪枝时力度无疑会更大，因此我们可以把a提到外循环，相应的加一个快排，因此我们得出一个结论：把剪枝有利的尽量放在外循环。
【usaco2023 12月银组题解】一、题目概况1.1 题目背景12月份的usaco银级比赛是每年一度的重要赛事，题目难度适中，涵盖了很多经典算法和数据结构的应用。
1.2 题目数量本次比赛共包含5道题目，涉及动态规划、贪心算法、图论等多个领域。
二、题目详解2.1 第一题 - 最小差值本题要求给定一个包含n个正整数的数组，求该数组中两个元素的最小差值。
2.1.1 解题思路我们可以先对数组进行排序，然后遍历数组中相邻的两个元素，计算它们之间的差值，并更新最小差值。
2.1.2 代码实现```c++int minDiff(vector<int> nums) {sort(nums.begin(), nums.end());int minDiff = INT_MAX;for (int i = 1; i < nums.size(); i++) {minDiff = min(minDiff, nums[i] - nums[i-1]);}return minDiff;}```2.2 第二题 - 运动员配对本题要求给定一个包含n个正整数的数组，表示n个运动员的实力值，要求找出一种最优的配对方案，使得每对运动员的实力差值最小。
2.2.1 解题思路我们可以先对数组进行排序，然后使用双指针法找出实力差值最小的配对方案。
2.2.2 代码实现```c++int minP本人ring(vector<int> strength) {sort(strength.begin(), strength.end());int minDiff = INT_MAX;int l = 0, r = strength.size()-1;while (l < r) {minDiff = min(minDiff, strength[r] - strength[l]);l++;r--;}return minDiff;}```2.3 第三题 - 最小生成树本题给定一个无向连通图，要求求出该图的最小生成树的权值之和。
更多真题解析2023年USACO第二场月赛考试结束，这次的铜组比赛考察的内容粗中有细，在合理的范围内需要扎实的基本功。
今天给大家带来USACO 三月月赛考题解析，祝各位同学都在竞赛中取得好成绩。
USACO2月月赛考题Problem1.Hungry CowBessie is a hungry cow.Each day,for dinner,if there is a haybale in the barn,she will eat one haybale.Farmer John does not want Bessie to starve,so some days he sends a delivery of haybales,which arrive in the morning(before dinner).In particular,on day di,Farmer John sends a delivery of bi haybales(1≤di≤1014,1≤bi ≤109).Compute the total number of haybales Bessie will eat during the first T days.一头牛在谷仓内要吃草，每天吃一堆，没草料的话就要饿肚子吃不到。
约翰会在某一天d送来若干草料b，我们要计算在某天t之前一共消耗了多少草料？题解：这是一道典型的模拟题目，我们需要对数组d和b填充完毕后做以下处理：分别判断草料足够使用以及不够使用的情况，足够使用要记录下吃草的天数，并把剩余草料结转到下一次；如果草料不够就记录草料数，剩余草料记为零；到了第t天，输出结果。
以下是部分关键代码：for(int i=1;i<=n;i++){if(cur<d[i]-d[i-1]-1) {ans+=cur;cur=0;}else{ans+=d[i]-d[i-1]-1;cur-=d[i]-d[i-1]-1; }if(cur<0){cur=0;}ans++;cur+=b[i]-1;if(i==n){ans+=min(cur,t-d[i]); }}Problem2.Stamp GridA stamp painting is a black and white painting on an N×N canvas,where certain cells are inked while others are blank.It can be described by an N×N array of characters(1≤N≤20).The ith entry of the jth column of the array is equal to*if the canvas contains ink at that square and.otherwise.Bessie has a stamp painting that she would like to create,so Farmer John has lent her a single K×K(1≤K≤N)stamp to do this and an empty N×N canvas.Bessie can repeatedly rotate the stamp clockwise by90∘and stamp anywhere on the grid as long as the stamp is entirely inside the grid.Formally,to stamp,Bessie chooses integers i,j such that i∈[1,N−K+1]and j∈[1,N−K+1];for each(i′,j′)such that1≤i′,j′≤K,canvas cell(i+i′−1,j+j′−1) is painted black if the stamp has ink at(i′,j′).Bessie can rotate the stamp at any time between stampings.Once a canvas cell is painted black,it remains black.Farmer John is wondering whether it's possible for Bessie to create her desired stamp painting with his stamp.For each of T(1≤T≤100)test cases,help Farmer John answer this question.奶牛拿了一个印章，k x k大小，能旋转使用。
USACO 2009年11月月赛金、银试题与解析重庆八中吴新第一题开灯(金组)贝希和她的朋友们在牛棚中玩游戏。
突然，牛棚的电源跳闸了，所有的灯都熄灭了。
贝希希望你帮帮她，把所有的灯都给重新开起来，她才能继续快乐地跟朋友们玩游戏！牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。
这些灯被置于一个非常复杂的网络之中。
有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。
每盏灯上面都带有一个开关。
当按下某一盏灯的开关的时候，这盏灯本身，还有所有与这盏灯有边相连的灯的状态都会被改变。
状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。
问最少要按下多少个开关，才能把所有的灯都给重新打开。
数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。
输入文件：第1行：两个空格隔开的整数：N和M。
第2..M+1行：每一行有两个由空格隔开的整数，表示两盏灯被一条无向边连接在一起。
没有一条边会出现两次。
输出文件：第1行：一个单独的整数，表示要把所有的灯都打开时，最少需要按下的开关的数目。
输入样例：5 61 21 34 23 42 55 3输入细节：一共有五盏灯。
灯1、灯4和灯5都连接着灯2和灯3。
输出样例：3输出细节：按下在灯1、灯4和灯5上面的开关。
第二题谁请客？(金组)农夫约翰的N（1 <= N <= 1000）头奶牛（编号为1到N）决定成立M个学习小组（1 <= M <= 100）。
在学习小组G_i中有S_i只牛，分别为牛G_i1、G_i2……一头牛可能会参加多个小组。
对于每个学习小组，有一头牛必须在每次聚会的时候带零食请大家吃。
因为买这些零食会消耗奶牛们那为数不多的零花钱，还会花费宝贵的时间，所以奶牛们希望尽可能公平地分摊带零食的责任。
她们决定：如果一头牛参加了K个学习小组，K个学习小组的大小分别为c_1、c_2、…、c_K，那么她最多负责为ceil(1/c_1 + 1/c_2 +… + 1/c_K)个学习小组的聚会带零食。
USACO Fall03题目总结在Noi2005之前，我和Fu Dong集体训练USACO竞赛的题目，分别写了一些题目的解题分析。
发表在这里供大家参考。
Fall03 Orange -- Cow Laundry题意：n条线段，有些线段可能会相交，一次可以交换上端点或下端点相邻的两条线段，求至少要经过多少次交换才能使所有的线段都互不相交。
就是求n个数的一个排列的逆序对数，方法很多，用归并排序，线段树，虚二叉树都可以做，我用的是虚二叉树，因为它的空间复杂度和时间复杂度都是最优的。
注：这个题的输入中每行的两个数不是表示一条线的上下两个端点的编号，而是表示上边第i个端点和下边第i个端点连的线的编号。
）Fall03 Orange -- Romeo Meets Juliet题意：P个点连成一条线段，有N只奶牛占有这条线段上一个单位的线段，求这条线段上最长的一条子线段，使得这条子线段上的奶牛不超过C只。
把每个单位线段上有多少头牛计算出来后，从头到尾扫描一下每个单位线段，并记录最长的长度就可以了。
Fall03 Orange -- ISBN题意：ISBN码是一个10位的能被11整除的数，给出一个ISBN码，其中有一位上的数字不知道是多少，求那个数字。
一个数被11除的余数与这个数奇数位上的数字和与偶数位上的数字和的差的绝对值被11除的余数相等，所以如果有解，那么一定是唯一的。
求缺的那个数字直接计算就可以了。
Fall03 Green -- Cow Exhibition题意：N头奶牛，每头牛有两个属性值S和F，现在要从中选出若干头牛，要求这些牛的S属性值的和非负，F属性值的和也非负，并且要求S属性值和加上F属性值和的结果最大。
这道题可以用动态规划来做，状态f[i,j]表示前i头牛中选出一些牛，它们的S属性值的和为j时，F属性值的和最大为多少。
用搜索来解决这道题的效率要比动态规划高很多。
首先把s≥0和f≥0的牛保存下来，因为这样的牛是一定要选的；把s＜0和f＜0的牛去掉，因为这样的牛是一定不能选的。
USACO 题解Chapter1Section 1.1Your Ride Is Here (ride)这大概是一个容易的问题，一个“ad hoc”问题，不需要特殊的算法和技巧。
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)。
Friday the Thirteenth (friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1) mod 7+1的星期。
因为数据小，所以不会超时。
当数据比较大时，可以以年为单位计算，每年为365天，mod 7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。
这样，只要先求出第一年的解，错位添加到以后的年即可。
详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1) mod7+1=星期六。
这样讲可能不太清楚。
那么，我来解释一下：每过7天是一个星期。
n天后是星期几怎么算呢？现在假设n是7的倍数，如果n 为14，那么刚好就过了两个星期，所以14天后仍然是星期一。
但如果是过了15天，那么推算就得到是星期二。
这样，我们就可以推导出一个公式来计算。
(n天 mod 7（一个星期的天数）+ 现在日期的代号) mod 7 就等于现在日期的代号。
当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法：int a[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}int b[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。
USACO 题解Chapter1Section 1.1Your Ride Is Here (ride)这大概是一个容易的问题，一个“ad hoc”问题，不需要特殊的算法和技巧。
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)。
Friday the Thirteenth (friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1) mod 7+1的星期。
因为数据小，所以不会超时。
当数据比较大时，可以以年为单位计算，每年为365天，mod 7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。
这样，只要先求出第一年的解，错位添加到以后的年即可。
详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1) mod7+1=星期六。
这样讲可能不太清楚。
那么，我来解释一下：每过7天是一个星期。
n天后是星期几怎么算呢？现在假设n是7的倍数，如果n为14，那么刚好就过了两个星期，所以14天后仍然是星期一。
但如果是过了15天，那么推算就得到是星期二。
这样，我们就可以推导出一个公式来计算。
(n天mod 7（一个星期的天数）+ 现在日期的代号) mod 7 就等于现在日期的代号。
当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法：int a[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}int b[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。
b数组保存星期一到星期日出现的天数。
用date记录目前是星期几的代号，然后用两个循环，依次加上所经过的月份的天数，就出那个月是星期几，当然，要注意判断闰年！知道了这个方法，实现起来就很容易了。
注意考虑闰月的情况。
最后注意要换行，否则会错误。
Broken Necklace (beads)这道题用标准的搜索是O(n^2)的，可以用类似动态规划的方法优化到O(n)。
用数组bl，br，rl，rr分别记录在项链i处向左向右收集的蓝色红色珠子数。
项链是环形的，但我们只要把两个同样的项链放在一块，就把它转换成线性的了。
我们只要求出bl，br，rl，rr，那么结果就是max(max(bl[i]，rl[i])+max(br[i+1]，rr[i+1])) (0<=i<=2*n-1)。
我们以求bl，rl为例：初始时bl[0]=rl[0]=0我们从左往右计算如果necklace[i]='r'，rl[i]=rl[i-1]+1，bl[i]=0；如果necklace[i]='b'，bl[i]=bl[i-1]+1，rl[i]=0；如果necklace[i]='w'，bl[i]=bl[i-1]+1，rl[i]=rl[i-1]+1。
同理可以求出br，rr。
事实上不必使用动态规划，直接搜索亦可达到O(n)。
把两个同样的项链放在一块，从头开始用两个变量(变量)a，b记录自左方某点至目前为止可搜集到之两种颜色珠子数，取途中所出现a+b之最大值，遇颜色变换时再将b指定给a 即可，代码十分简洁。
思路二：每次将串s的首位移动至末位，每次均能从两头开始搜索，无需考虑环的问题。
思路三：无需考虑w的。
进行分类讨论，只有rb和br两种情况。
Section 1.2Milking Cows (milk2)有三种思想。
离散化（其实就是进行了优化的搜索而已）按照开始时间升序排序，然后从左到右扫一遍，复杂度是O(nlogn+n)的（排序+扫一遍，用堆、合并、快排都可以）。
所谓从左到右扫一遍，就是记录一个当前区间，[tmp_begin,tmp_end]。
如果下一组数据的begin比tmp_end的小（或相等），则是连接起来的，检查这组数据的end，取max{end,tmp_end}。
如果下一组数据的begin比tmp_end的大，则是相互断开的，整理本区间，ans1取max{tmp_end - tmp_begin,ans1}。
ans2取max{begin - tmp_end,ans2}。
看不懂？去看看PASCAL或C的范例程序就明白了。
线段树本题的规模是1e6，简单的模拟是O(nm)(n是奶牛个数，m是最大范围)的，会超时。
（但是本题数据远没有描述的那么恐怖，直接模拟也是很快的）。
用线段树统计区间，复杂度降为O(nlogm+m)，可以接受。
标记数组（哈希）1e6的范围，开一个布尔数组完全可以，有人为TRUE，无人为FALSE，注意边界即可。
最后线性扫描即可。
时间复杂度，应该是O(n)，n为最后结束的时间。
缺点就是……比较慢。
叫什么好呢？并查集加速直接模拟。
记录一个fa[i]表示i之后第一个没覆盖的点。
下次遇到这里的时候就可以直接跳过了。
复杂度大概算o（n）吧。
Transformations (transform)设a是原始状态，b是改变后的状态。
水平翻转：b[i，n-j+1]:=a[i，j]右旋90度：b[j，n-i+1]:=a[i，j]枚举方案就行了，或直接枚举变换。
需要注意的是，USACO是不给用GOTO的。
注意代码的清晰程度。
Name That Number (namenum)一个数字对应3个字母，如果我们先枚举出数字所代表的所有字符串，就有3^12种，然后再在5000的字典里寻找，可以用二分查找，数据规模是3^12*log5000=6.5e6，空间规模是5000。
其实可以做的更好！一个字母只对应一个数字，从字典中读入一个单词，把它转化成唯一对应的数字，看它是否与给出的数字匹配，时间规模是5000*12=6e4，空间规模是常数，而且编程复杂度较低。
还可以先比较字符长度和数字长度，如果相等，逐位比较。
把字母对应成数字我给出个公式，证明不写了，很容易想明白：temp:=ord(nam[i][j])-64;if temp>17 then dec(temp)；num[i]:=num[i]*10+((temp-1) div 3)+2;temp是第i个名字的第j个字符ASCII码-64后的值，num[i]是地i个名字转换成的数字。
还有一个方法，利用哈希表，把字典进行哈希. 然后对于新产生的字符串，在哈希表里进行查找，找到了则加入输出列表. 最后则快排后输出。
补充一下：可以用集合来处理s[2]=['A'，'B'，'C']; s[3]=['D'，'E'，'F']; 由于以3为周期，这种集合的建立可以由div 3得到但注意其中挖掉了'Q'，这可以分两段来建立集合。
另一种思路：如果我们就使用普通的搜索，可以这样优化：设一个有效奶牛名数量统计s，在读字典时，首先粗略判断字典中的奶牛名是否是我们所要的（如：长度是否和input文件里一样，首字母代表的数字是否与input文件中的数字一样等等。
注意input文件中的数字最好读成字符串处理。
）如果不合法，s就不加1. 这样最终剪枝之后，每个数据的有效名称不超过200个，算最坏情况，时间复杂度共计O(5000+200)，可以说相当优秀。
Palindromic Squares (palsquare)这道题唯一的知识点就是数制的转换。
思路：好像没什么难的，主要就是考进制转换，以及回文数的判断。
这里要注意，最大的20进制中19表示为J，不要只CASE到15哦！穷举1~300的所有平方数，转进制，比较，OK了，除非你不会怎么转进制。
短除，然后逆序输出。
Dual Palindromes (dualpal)因为数据很小，所以只需要从s开始枚举每个十进制数然后判断就行了。
参见进制转换，但并非最优算法。
Section 1.3Mixing Milk (milk)简单的贪心算法：将所有的牛奶按价格升序排列（用快排），然后从低到高买入，直到买够m为止。
贪心的证明：假设某次买了价格稍高的牛奶，可以得到最优解。
那么把这次买的牛奶换成价格更低的牛奶，其它不变，那么所得的解较优。
假设不成立。
利用桶排的思想可以把代码压缩到极限，参见代码三。
因其价格范围为[0..1000]可以用计数排序来做，就可以得到一个傻瓜代码(参见代码四)。
最佳解题方法：因为价格的范围在1..1000之内，所以，我们只要在读入数据的时候把相同价格的合并即可，进行计算时，也只需要for i:=0 to 1000 do进行扫描如果有价格为i的牛奶就收购即可，所以不需要排序。
Prime Cryptarithm (crypt1)思路一要使木板总长度最少，就要使未盖木板的长度最大。
我们先用一块木板盖住牛棚，然后，每次从盖住的范围内选一个最大的空隙，以空隙为界将木板分成两块，重复直到分成m块或没有空隙。
可以用二叉堆来优化算法。
贪心的证明略。
思路二显然，当所有木板均用上时，长度最短（证明....）。
正向思维，初始状态有c块木板，每块木板只盖住一个牛棚。
由c块倒推至m块木板，每次寻找这样的两个牛棚：其间距在所有未连接的木板中最小。
当这两个牛棚的木板连接时，总木板数减1，总长度增加1。
思路三还可以用动态规划求解，将有牛的牛棚排序后，设置一个函数d[i，j]表示第i个牛修到第j个牛需要使用的木版长度，设f[i，j]表示用前i个木版修到第j头牛所用的最短长度。
f[i，j]=f[i-1，k-1]+d[k，j] (i<=k<=j)思路四显然，当所有木板均用上时，长度最短。
用上m块木板时有m-1各间隙。
现在的目标是让总间隙最大。
将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的m-1个作为间隙，其余地方用木板盖住即可。
Barn Repair (barn1)没什么好说的，硬搜，数据刚好不会超时。
枚举中间数（也就是认为它是回文数最中间的字母），然后左右扩展（忽略非字母）至出界和不相等。
最后更新最大值。
要考虑回文是奇数和偶数两种情况。
提示大家在开始扩展之前就判断（很巧妙，大家举几个例子就可以明白了）。
输入中的换行符可以维持原样不变，PASCAL不会输出成乱码。
