分类目录归档:编程挑战

Common Permutation

PC/UVa IDs: 110303/10252

分析:本题只要求得到一个字符串x,使得x的某两个排列分别是两个给定字符串的子串,并没有要求x的某一个排列同时是两个给定字符串的子串。理解清楚这一点非常重要——如果题目要求是后者,则问题就演变成了求两个字符串的最长(非连续的)公共子序列(LCS)的问题,难度陡升。 继续阅读

Summation of Four Primes

PC/UVa IDs: 110705/10168

分析:试验表明:任何一个不小于8的整数都可以表示为四素数之和,且答案可能不唯一;另外,如果按照“从大到小”的顺序来找四个素数会比较快地找到解。因此有如下解:先用筛选质数法列出10000000以内的素数,然后用回溯法把一个整数n分解为四素数之和——在回溯时从不超过n的最大素数开始向前尝试。 继续阅读