USACO 5.4&5.5

今天终于把第5章搞定了.USACO还剩下3题,早日结束了这3题,任务还很艰巨啊.

简单写下这两节的题解.这两节搞了好久啊.有些题还是看了题解之后,然后差不多是照着标称打的(- -|).

ALL Latin:比较变态的一道搜索题,7的时候过不去,然后看的题解,那个循环群什么的不是很懂,用的是另外一种方法,就是首先第一行第一列都放好(最后结果再乘以(n-1)!就行),然后第2行第2列放2,3,4,5的方案是一样多的.貌似比较慢,最慢的0.9+s

Canada Tour:费用流的方法没弄,用的是DP,类似方格取数的那种多线程DP,只需要看最后是不是有两条独立的路径从起点到终点就OK了,中间不能有重复的点

Character Recognition:很烦的一道题,借鉴标称的,方法:DP,有一点就是多余的那一行的变化数不算在里面的.然后如果知道了前i行的可以推知i+19,i+20,i+21的情况.

Betsy’s Tour:正解是连通性DP?czw和我说了下这是最简单的连通性DP,但是那论文看不懂,刚好这题可以搜过,只需要考虑下,如果进入了死胡同就不要搜了,还有如果当前的路径把格子分成了两边就不用搜了.死胡同那个可以考虑做过这个点之后,它的上下左右点是否被走过,一个点必须有进有出才行(不然进死胡同了),除了起点和终点

TeleCowmunication:拆点,最大流,然后枚举删点.拆点时,每个点拆成2i,2i+1,然后流量是1,原边中有边的则加两条无穷大的边,跑最大流,然后枚举删点.看删掉点之后是不是最大流减少了.是的话就输出这个点,最大流减少,继续枚举

Picture:很早以前就听说这题是线段树的好题,但是我还是用了朴素的方法(小汗一下),直接把横向边和纵向边分别排序,然后遇到起始边(坐标小的)就+1.否则-1.这样如果由0->1,那么一定是最终矩形的边,这样枚举完了之后,在USACO还挺快.线段树就是在更新+1,-1的时候用线段树,可以做到区间处理.降低时间复杂度

Hidden Passwords:刚好czw和我说过最小表示法,然后就直接做了.或许这是这两节我觉得最简单的了- -|.貌似还有很多其他方法,可以看看nocow的分析

Two Five:就是一个一个算就行了.主要是要好写,而且速度还过得去.对于数变字符串.可以枚举25个位置,如果某个位置放字符ch的数目加上前面算的结果已经超过了给的n,那么就把这个位置放置ch,因为放置ch-1的时候不够,然后接着放下一个位置,直到25个位置全放好为止,字符串变数字的差不多,只不过把上面的操作反过来而已,就是看这个字符之前有多少个.比如求ACD的,那么我们就求ABC,ABD,ACB,的方案数,然后再求ACD后面有多少个,就像求10进制数的大小一样,求521是第几个,可以首先求1,2,3,4的个数,然后求5_(<2)和52(<1)的个数,最后结果+1就是521的结果了

接下来还有三题,搞定也算是圆满了USACO,加油吧