首页| 论坛| 消息
主题:USACO Chapter 1~3 简析
archimedes发表于 2006-02-20 10:01
1.2 beads Broken Necklace
每次都把遇到的第一颗珠子作为标准珠,处理珠子直到遇到异色珠(白色为同色);处理一颗珠子就把珠子删掉,防止重复计算;注意在某一点断开后,可能遇到白色珠,那么就不停地读,直到遇到蓝色或红色珠,把标准珠修改为遇到的珠子,继续操作。

1.2 pprime Prime Palindromes
从开始数的位数,到结束数的位数,通过对位数奇偶性的判断,来决定最后生成回文数的方式;通过对回文数左边一半的枚举,就能够生成整个回文数(注意奇偶);用简单的判质即可解决。
1.3 barn1 Barn Repair
可以用贪心,将连在一起的牛看作整体,把空白的地方看作一个整体,将整个牛-空串的两端的空去掉后,把空排序,把最小的空用栅栏把两边的牛群联在一起,如此重复操作,直到满足规定;我是用DP解的,把f[ i ]定义用i块木板从第j个牛群覆盖到第k个牛群的最少长度。
1.4 checker Checker Challenge
对每行穷举方案并对该点所在列标记,以防重复的常规算法上改进。把最长的那条对角线标记为0号对角线,在其右边与其平行的对角线号码递增,反之递减。如此即可完成对角线的标记,完成第一步优化;利用对称性,可以将第一行只枚举左边一半的情况,因为其实枚举右边也是一样的,完成第二步优化;搜两次,第一次搜到三个解即退出,第二次不记录方案再搜一次,可以大幅提高效率,完成最后一步优化。[剪枝]
1.4 sprime Superprime Rib
对第一位穷举判质,加入第二位穷举判质…… 注意除了第一位可以放个2外,不允许有偶数,因此实际搜索量很小.....
2.1 castle The Castle
把地图存下来,然后用flood fill将每个格子染色,记下最后颜色总数,和每个颜色的格子数。再把每个
下一页 (1/5)
回帖(1):
1楼:不是有Chapter4 了么.......

--> 全部回帖(1)»
最新回帖
收藏本帖
发新帖