Postal Vans
一看就是一道状态压缩的题目, 牛X一点, 基于连通性的状态压缩. 可以按照cdq大牛今年冬令营的论文中所讲的括号表示法来做.
f[ i ][ j ][ S ]表示到( i, j )格时, 轮廓线状态为S时的总方案数, 分三种情况讨论, 1>新建一对匹配括号, 2>合并两个括号, 3>延续一个括号. 最后答案是f[ N ][ 4 ][ 0 ]. 当然还有很多别的状态表示方式可以做. 看第二维那么小( <=4 ), 按行搜索其实也不错啊.
A Rectangular Barn
很经典的有关数据结构应用的题目, 做的时候碰巧读到朱晨光大牛2006年冬令营论文, 用了其中说的堆栈作法, 不做赘述, 附这篇论文的下载.
朱晨光《基本数据结构在信息学竞赛中的应用》链接失效
Cow XOR
这道题也很经典 ( 6.1道道经典, 或者就是我太水了 ), 为了做这题又把那道 Hidden Password 想了一遍, 两道题的思路很相似, 就是每次循环都去淘汰若干个不符合要求的答案, 直到最后剩下一个( 或若干个 )正确答案为止 ( 很有我做化学选择的题风格, 拼人品法+排除法 ).
官方解法就是这样:
用xr[ i ]表示从第1个数到第i个数做xor运算后的结果, 则从第i+1个数到第j个数做xor运算的结果等于xr[ j ] xor xr[ i ] ( 因为 a xor b xor b = a. 不熟悉位运算? 去Matrix67’s Blog补课 ).
我们要从最高位到最低位去判断xor结果的最大值, 因此, 设当前判断到从左数起第e位, 定义pop[ i ][ 0 ]表示1~i-1这些数字中, 编号最大的, 二进制表示从左数起第1, 2, 3, 直到第e位都与i相等的数的编号, 再定义pop[ i ][ 1 ]表示1~i-1这些数字中, 编号最大的, 二进制表示从左数起第1,2,3,直到第e-1位都与i相等, 但第e位不同的数的编号. 设当前最大xor结果为X, 设best[ i ]为在1~i-1中, 编号最大的数的编号, 满足xr[ best[ i ] ] xor xr[ i ] = X.
无论是pop[ i ][ 0 ], pop[ i ][ 1 ], 或best[ i ], 若满足条件的数不存在, 则其值为-1.
这样, 我们就可以逐位求出那个X, 并利用pop[ i ][ 0 ]和pop[ i ][ 1 ]调整best[ i ]的值, 不断淘汰错误的解( 即将best[ i ]设成-1 ), 最后找到编号最小的i满足best[ i ] != -1, 将best[ i ] + 1与i输出来就可以了. 由于我们每次都要求的pop[ i ][ 0 ], pop[ i ][ 1 ]及best[ i ]都满足编号尽可能大, 因此i - best[ i ]也必然会尽可能小.
自认为这样的思想很值得仔细的品味.
完整的写完了USACO 4.1~6.1的全部解题报告, 第四章之前的当时没写, 现在也懒的补上, 等有空再找几道当时做的很困难的题重温一下. 感觉USACO用来做入门的题库是再合适不过了, 提供数据不会使自己感到为难, 同时又涉及到了种种基础的数据结构和算法.
赞
话说我还在2.1.1呢
sqybi