USACO题解(NOCOW整理版)

USACO题解Chapter1Section1.1YourRideIsHere(ride)这大概是一个容易的问题，一个“adhoc”问题，不需要特殊的算法和技巧。GreedyGiftGivers(gift1)这道题的难度相当于联赛第一题。用数组incom、outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j，inc(incom[j],outcom[i]divn)，其中n是要送的人数，最后inc(incom[i],outcom[i]modn)，最后输出incom[i]-outcom[i]即可。（复杂度O(n^3)）。用Hash表可以进行优化，降复杂度为O(n^2)。FridaytheThirteenth(friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1)mod7+1的星期。因为数据小，所以不会超时。当数据比较大时，可以以年为单位计算，每年为365天，mod7的余数是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天mod7（一个星期的天数）+现在日期的代号)mod7就等于现在日期的代号。当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法：inta[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}intb[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。b数组保存星期一到星期日出现的天数。用date记录目前是星期几的代号，然后用两个循环，依次加上所经过的月份的天数，就出那个月是星期几，当然，要注意判断闰年！知道了这个方法，实现起来就很容易了。注意考虑闰月的情况。最后注意要换行，否则会错误。BrokenNecklace(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两种情况。Section1.2MilkingCows(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的。注意代码的清晰程度。NameThatNumber(namenum)一个数字对应3个字母，如果我们先枚举出数字所代表的所有字符串，就有3^12种，然后再在5000的字典里寻找，可以用二分查找，数据规模是3^12*log5000=6.5e6，空间规模是5000。其实可以做的更好！一个字母只对应一个数字，从字典中读入一个单词，把它转化成唯一对应的数字，看它是否与给出的数字匹配，时间规模是5000*12=6e4，空间规模是常数，而且编程复杂度较低。还可以先比较字符长度和数字长度，如果相等，逐位比较。把字母对应成数字我给出个公式，证明不写了，很容易想明白：temp:=ord(nam[i][j])-64;iftemp17thendec(temp)；num[i]:=num[i]*10+((temp-1)div3)+2;temp是第i个名字的第j个字符ASCII码-64后的值，num[i]是地i个名字转换成的数字。还有一个方法，利用哈希表，把字典进行哈希.然后对于新产生的字符串，在哈希表里进行查找，找到了则加入输出列表.最后则快排后输出。补充一下：可以用集合来处理s[2]=['A'，'B'，'C'];s[3]=['D'，'E'，'F'];由于以3为周期，这种集合的建立可以由div3得到但注意其中挖掉了'Q'，这可以分两段来建立集合。另一种思路：如果我们就使用普通的搜索，可以这样优化：设一个有效奶牛名数量统计s，在读字典时，首先粗略判断字典中的奶牛名是否是我们所要的（如：长度是否和input文件里一样，首字母代表的数字是否与input文件中的数字一样等等。注意input文件中的数字最好读成字符串处理。）如果不合法，s就不加1.这样最终剪枝之后，每个数据的有效名称不超过200个，算最坏情况，时间复杂度共计O(5000+200)，可以说相当优秀。PalindromicSquares(palsquare)这道题唯一的知识点就是数制的转换。思路：好像没什么难的，主要就是考进制转换，以及回文数的判断。这里要注意，最大的20进制中19表示为J，不要只CASE到15哦！穷举1~300的所有平方数，转进制，比较，OK了，除非你不会怎么转进制。短除，然后逆序输出。DualPalindromes(dualpal)因为数据很小，所以只需要从s开始枚举每个十进制数然后判断就行了。参见进制转换，但并非最优算法。Section1.3MixingMilk(milk)简单的贪心算法：将所有的牛奶按价格升序排列（用快排），然后从低到高买入，直到买够m为止。贪心的证明：假设某次买了价格稍高的牛奶，可以得到最优解。那么把这次买的牛奶换成价格更低的牛奶，其它不变，那么所得的解较优。假设不成立。利用桶排的思想可以把代码压缩到极限，参见代码三。因其价格范围为[0..1000]可以用计数排序来做，就可以得到一个傻瓜代码(参见代码四)。最佳解题方法：因为价格的范围在1..1000之内，所以，我们只要在读入数据的时候把相同价格的合并即可，进行计算时，也只需要fori:=0to1000do进行扫描如果有价格为i的牛奶就收购即可，所以不需要排序。PrimeCryptarithm(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个作为间隙，其余地方用木板盖住即可。BarnRepair(barn1)没什么好说的，硬搜，数据刚好不会超时。枚举中间数（也就是认为它是回文数最中间的字母），然后左右扩展（忽略非字母）至出界和不相等。最后更新最大值。要考虑回文是奇数和偶数两种情况。提示大家在开始扩展之前就判断（很巧妙，大家举几个例子就可以明白了）。输入中的换行符可以维持原样不变，PASCAL不会输出成乱码。来说说一种O(n)的动态规划算法。方程f[i]=f[i-1]+2如果(a[i]=a[i-f[i-1]-1])或f[i]=2如果(a[i]=a[i-1])或f[i]=1其中f[i]是以恰好第i个字符结尾的回文串最大长度。速度巨快如雷电……另一种解法：1.初始化答案为0。S=T+'#'+Reverse(T)+$，得到串S（O(n)）。2.求出后缀数组SA、名次数组Rank（倍增法：O(nlogn)Dc3算法：O(n)）3.计算height数组并进行标准RMQ方法预处理（O(n)）4.枚举i，计算以i为对称中心的极长回文串并更新答案（O(n)）。扩展kmp+分治复杂度:O(nlogn)CalfFlac(calfflac)S1S4S5×S2S3约束条件只有3个：第3、4行是3位数，第5行是4位数。按S1到S5的顺序搜索。如果S1×S210或者S1×S310，则3、4行肯定不是3位数，剪枝。即S1*S2+S4*S2/10=10||S1*S3+S4*S3/10=10剪枝。补充：从高位到低位，从小到大填数据，如果发现乘积超过999就剪枝。Section1.4PackingRectangles(packrec)只要将示例中的6种（其实是5种，图4和5是同一种情况）进行模拟，以求得最优解。TheClocks(clocks)可以用bfs，dfs，枚举，数学方法解。位运算加速说说位运算加速吧，不仅编程复杂度低，效率也高。注意到时钟只有四种状态，12点，3点，6点，9点。令它们为0，1，2，3（这样的定义好处很大）。这样，它们对应的二进制数为：000，001，010，011。即，我们用三个位来记录一个时钟的状态（为什么不用两位？请思考）。要tick一个时钟的时候，就给该位加上一，再用按