usaco中文译题 下载本文

Prime Palindromes

回文质数

译 by tim green

因为151即是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 号是回文质数。

写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)间的所有回文质数;

PROGRAM NAME: pprime INPUT FORMAT

第 1 行: 二个整数 a 和 b .

SAMPLE INPUT (file pprime.in)

5 500

OUTPUT FORMAT

输出一个回文质数的列表,一行一个。

SAMPLE OUTPUT (file pprime.out)

5 7 11 101 131 151 181 191 313 353 373

3Greedy Algorithm

贪心算法

译 by Lucky Crazy & Felicia Crazy 样例:牛棚修理 [1999 USACO 春季公开赛]

Farmer John 有一列牛棚,在一次暴风中,牛棚的一整面墙都被吹倒了,但还好不是每一间牛棚都有牛。Farmer John 决定卖木料来修理牛棚,然而,刻薄的木材提供商却只能提供有限块的木料(木料的长度不限),现在告诉你关着牛的牛棚号,和提供的木材个数N,你的任务是编程求出最小的木块长度和。(1 <= N <= 50) 贪心思想:

贪心思想的本质是每次都形成局部最优解,换一种方法说,就是每次都处理出一个最好的方案。例如:在样例中,若已经发现 N = 5 时的最优解,那么我们可以直接利用 N = 5 的最优解构成 N = 4 的最优解,而不用去考虑那些 N = 4 时的其他非最优解。

贪心算法的最大特点就是快。通常,二次方级的存储要浪费额外的空间,而且很不幸,那些空间经常得不出正解。但是,当使用贪心算法时,这些空间可以帮助算法更容易实现且更快执行。 贪心的难点:

贪心算法有两大难点: 如何贪心:

怎样才能从众多可行解中找到最优解呢?其实,大部分都是有规律的。在样例中,贪心就有很明显的规律。但你得到了 N = 5 时的最优解后,你只需要在已用上的5块木板中寻找最靠近的两块,然后贴上中间的几个牛棚,使两块木板变成一块。这样生成的 N = 4 的解必定最优。因为这样木板的浪费最少。同样,其他的贪心题也会有这样的性质。正因为贪心有如此性质,它才能比其他算法要快。 贪心的正确性:

要证明贪心性质的正确性,才是贪心算法的真正挑战,因为并不是每次局部最优解都会与整体最优解之间有联系,往往靠贪心生成的解不是最优解。这样,贪心性质的证明就成了贪心算法正确的关键。一个你想出的贪心性质也许是错的,即使它在大部分数据中都是可行的,你必须考虑到所有可能出现的特殊情况,并证明你的贪心性质在这些特殊情况中仍然正确。这样经过千锤百炼的性质才能构成一个正确的贪心。

在样例中,我们的贪心性质是正确的。如下:

假设我们的答案盖住了较大的空牛棚连续列,而不是较小的。那么我们把那部分盖空牛棚的木板锯下来,用来把较小的空牛棚连续列盖住,还会有剩余。那么锯掉它们!还给木材商!同时我们的解也变小了。也就是说,我们获得更优的解。所以,靠盖住较大空牛棚连续列的方法无法获得最优解,我们也应该尽量贪心那些距离小的木板合并。

如果仍有一个空牛棚连续列与我们的答案盖住的那个相同,我们同样使用上述的方法。会发现获得的新解与原解相同,那么不论我们选哪个,结果都将一样。 由此可见,如果我们合并的两块木板间距离最短,那么总能获得最优解。所以,在解题的每一步中,我们都只需要寻找两块距离最小的木板并合并它们。这样,我们获得的解必定最优。 结论:

如果有贪心性质存在,那么一定要采用!因为它容易编写,容易调试,速度极快,并且节约空间。几乎可以说,它是所有算法中最好的。但是应该注意,别陷入证明不正确贪心性质的泥塘中无法自拔,因为贪心算法的适用范围并不大,而且有一部分极难证明,若是没有把握,最好还是不要冒险,因为还有其他算法会比它要保险。 类似问题:

三值排序问题 [IOI 1996]

有一个由N个数值均为1、2或3的数构成的序列(N<= 1000),其值无序,现要求你用最少的交换次数将序列按升序顺序排列。

算法:排序后的序列分为三个部分:排序后应存储1的部分,排序后应存储2的部分和排序后应存储3的部分,贪心排序法应交换尽量多的交换后位置正确的(2,1)、(3,1)和(3,2)数对。当这些数对交换完毕后,再交换进行两次交换后位置正确的(1,2,3)三个数。

分析:很明显,每一次交换都可以改变两个数的位置,若经过一次交换以后,两个数的位置都由错误变为了正确,那么它必定最优。同时我们还可发现,经过两次交换后,我们可以随意改变3个数的位置。那么如果存在三个数恰好为1,2和3,且位置都是错误的,那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质,我们的贪心算法成立。 货币系统 -- 一个反例 [已删节]

奶牛王国刚刚独立,王国中的奶牛们要求设立一个货币系统,使得这个货币系统最好。现在告诉你一个货币系统所包含的货币面额种类(假设全为硬币)以及所需要找的钱的大小,请给出用该货币系统找出该钱数,并且要求硬币数尽量少。 算法:每次都选择面额不超过剩余钱数但却最大的一枚硬币。例如:有货币系统为{1,2,5,10},要求找出16,那么第一次找出10,第二次找出5,第三次找出1,恰好为最优解。

错误分析: 其实可以发现,这种算法并不是每一次都能构成最优解。反例如:货币系统{1,5,8,10},同样找16,贪心的结果是10,5,1三枚,但用两枚8的硬币才是最优解。因为这样,贪心的性质不成立,如此解题也是错的。 拓扑排序

给你一些物品的集合,然后给你一些这些物品的摆放顺序的约束,如\物品A应摆放在物品B前\,请给出一个这些物品的摆放方案,使得所有约束都可以得到满足。

算法:对于给定的物品创建一个有向图,A到B的弧表示\物品A应摆放在物品B前”。以任意顺序对每个物品进行遍历。每当你找到一个物品,他的入度为0,那么贪心地将它放到当前序列的末尾,删除它所有的出弧,然后对它的出弧指向的所有结点进行递归,用同样的算法。如果这个算法遍历了所有的物品,但却没有把所有的物品排序,那就意味着没有满足条件的解。 83