USACO题解-Chapter 1

I’m on my way. I know I’m gonna get there someday. It doesn’t help when you say It won’t be easy. PROB Your Ride Is Here 模拟。 可利用ASCII码将字母转换成数字。 Program ride; PROB Greedy Gift Givers 模拟。 如果一个人钱数为x，想送给y个人礼物，有以下三种情况： 1、 x=0，连续读入y行人名即可； 2、 y=0，将钱数加到此人名下即可； 3、 x<>0，y<>0，此人所有的钱数要加上分给别人后剩余的钱，即x mod y，再减去x；读入y行人名，每人名下加上x div y。 Program gift1; PROB Friday the Thirteenth 模拟。 判断闰年，1900年1月13日是星期六，即数字6，加上这个月的天数，再一直-7直到<=7，就是对应的星期几了。 Program Friday; PROB Broken Necklace 模拟。 枚举断点，指针l和r分别表示从断点向左和向右的长度，向左若到0则赋为n，向右若到n+1则赋为1；特殊情况： 1、 全为r或b或w，则如果l>n或r>n或l+r>n就输出n并退出，否则会死循环； 2、 出现如rrwwwwbb的情况，在第一个r左侧断的话，向右会记rrwwww长度为6，向左会记bbwwww长度为6，相加输出ans=12>n=8，可以在更新ans值时判断是否大于n，若大于，跳出循环并输出n退出。 Program beads;

▲PROB Milking Cows 模拟。 读入开始点l和结束点r时分别将模拟数组a中的a[l+1]+1、a[r+1]-1，并记录l的最小值， r的最大值作为区间范围[因为是从有人挤奶开始算起，且题目中未规定上限]。用i循环min+1到max+1，令a[i]=a[i]+a[i-1]，到此时a数组与每次读入都将a[l..r]+1的效果相同，而且复杂度降低。 处理时先判断是否更新最优值，再累计值+1。否则因为a[min]<>a[min+1]，先加会导致出现用1更新最优值、答案-1等情况。每次更新最优值后将累计值清零。 Program milk2; PROB Transformations 模拟。 很明显的模拟，很明显的麻烦。得算出旋转和镜面对称后坐标变化的规律，利用新数组存储，再逐位比较。 1、 c[j,1+n-i]:=a[i,j]，顺时针旋转90°； 2、 c[1+n-i,1+n-j]:=a[i,j]，顺时针旋转180°； 3、 c[1+n-j,i]:=a[i,j]，顺时针旋转270°； 4、 c[i,1+n-j]:=a[i,j]，水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。 Program transform; PROB Name That Number 模拟。 由于一个数字对应三个字母，如果直接计算，会有3^12个名字，即使在4617个给定名字中使用二分查找也很慢。反过来，计算字母对应的数字，与读入的一个编号进行比较，则会快很多。 2: A,B,C 3: D,E,F 4: G,H,I 5: J,K,L 6: M,N,O 7: P,R,S 8: T,U,V 9: W,X,Y 【把字母对应成数字我给出个公式，证明不写了，很容易想明白：temp:=ord(name[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个名字转换成的数字。----by Tony Shaw. 】 证明：大写字母的ASCII码值从65到90，第17个是Q，因为数字对应的字母里没有Q和Z，-1是去掉Q；-1再除以3是分组，三个一组，这样ABC就可以分到一组，+2是因为ABC分别对应012，div3均是0，而分组是从2组开始的。 因为之前的temp-1，Z被分到10组，而Q则到了7组。这样似乎还有些问题，如果出现了SUE、QUE，输入783的话，就会出错。 Program namenum; PROB Palindromic Squares 模拟。 十进制数字x转换为n进制的方法为： While x<>0 do {len:=len+1; a[len]:=x mod n; x:=x div n;} 根据情况不同可以有多种变式，比如不用数组存储，用字符串： While x<>0 do {len:=len+1; s:=num[x mod n]+s; x:=x div n;} 在使用字符串时，需要注意向字符串中添加字符时，+前后顺序不能颠倒，必须后加s，否则会造成数字倒序添加，比如26，仍为十进制时利用此循环{s:=s+num[x mod n]}处理完后，输出的s是62。这种错误对于输出平方回文数没有影响，但是鉴于题目还要求输出n进制下的原数，就必须注意顺序了。 同样转换为n进制，原数y一定不会比平方数长度大，可以在while循环中嵌套if y<>0then语句以同样的方法转换原数。 Num为字符型数组，存储0~9，A~K{分别表示10~20}的字符。 Program palsquare; PROB Dual Palindromes 模拟。 将上一题的程序改改就成了。读入n和s之后，用while true do循环对大于s的数进行处理，不断+1，直到已输出的数sum=n为止。处理时用for循环2~10进制，处理方法同上，字符串检查，如果符合回文数tot+1，当tot>=2时，说明此数在两种或两种以上进制（2~10进制）上是回文数，输出该数，且sum+1。 Program dualpal; You program worked first time! PROB Mixing Milk 贪心。 将牛奶的价钱和数量按照价钱由小到大排序，从小到大取n份牛奶计算价钱即可。 Program milk; You program worked first time! PROB Barn Repair 贪心。 有几点需要注意：第一，读入的c个牛棚编号不一定是按顺序的，可能完全无序，所以读入后必须存储；第三，虽然选m-1个最大的空隙去掉就可以，但m有可能大于等于c。此时，只要输出c即可。二……是留给栽在以上两个坑里的蒟蒻[包括我]的。 读入牛棚编号，从大到小排序，令a[0]:=a[1]-a[c]+1，是求得从第一个有牛的牛棚到最后一个有牛的牛棚的长度，这就是当只用一块木板时的长度了；for循环令a[i]:=a[i]-a[i+1]-1，求两牛棚之间的空隙，空隙为0的情况可能很多，所以要顺便把空隙为0的去掉：If a[i]=0 then {inc(tot); a[tot]:=a[i];}因为不管有没有0的情况出现，tot一定小于等于i，不必担心把a[i]处的空隙覆盖掉。重新从大到小给a[1..tot]排序，这次排的就是空隙了，选择1到m-1个空隙，在a[0]中减去空隙的长度，输出a[0]即可。从需要注意的第三可以看出，一旦m大于等于c，可以不用处理直接输出c即可。 Program barn1; ▲PROB Calf Flac 搜到一个字母就检查是否有和它对应成回文串的字符串，注意字符串长度可能是偶数也可能是奇数。 Program calfflac; PROB Prime Cryptarithm 穷举。 读入n个数，存入集合s。穷举111到999和11到99之间的每一个数分别作为数i和数j，x和y分别是j的个位和十位。

第一，检查i*j是不是四位数，i*x、i*y是不是三位数，不是则continue； 第二，检查i、j、i*j、i*(j mod 10)、i*(j div 10)中的数是否都在集合s中，是的话ans+1。 Program crypt1; ▲PROB Packing Rectangles 枚举+模拟。 出了几个小纰漏。一个是读入时rewrite了input，一读全空了；还有一个是当i循环0~15，j循环1~4时，改动a[j]和b[j]写成了a[i]和b[i]，超了a和b数组的范围。当用了Math

库后这些错误都显示成217了，没头没脑的，差点儿就打算重写了。

横宽x竖长y ① 宽x1+x2+x3+x4，长max(y1,y2,y3,y4)； ② 宽max(x4,x1+x2+x3)，长max(y1,y2,y3)+y4； ③ 宽max(x3,x1+x2)+x4，长max(max(y1,y2)+y3,y4)； ④ 宽max(x2,x3) +x1+x4，长max(y1,y4,y2+y3)； ⑤ 同④； ⑥ Ⅰ. 宽max(x1+x2,x3,x4))，长max(y1+y3,y2+y4)； Ⅱ. 如y1Ⅲ. 如y1>y2，宽max(Ⅱ,x1+x4)，长同Ⅰ； Ⅳ. 如(y1+y3>y2)and(y2+y4>y1)，宽max(Ⅲ,x3+x4)，长同Ⅰ； 每一个矩形有两种状态，共16种，调用16次deal(1)，每一次可以扩展出一种状态，正好遍历2^4种组合： procedure deal(n:longint); begin inc(pos[n]); alt[n]:=true; if (pos[n]=2)and(n<4) then deal(n+1); pos[n]:=pos[n] mod 2; end; 分别为：{◆表示长宽交换后矩形，◇表示原矩形} 编号\状态\次数 1 2 3 4 5 6 7 8 1 ◆ ◇ ◆ ◇ ◆ ◇ ◆ ◇ 2 ◇ ◆ ◆ ◇ ◇ ◆ ◆ ◇