走进“回文”的神秘世界中

《走进“回文”的神秘世界中》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、走进“回文”的神秘世界中在平时生活中，有一种现象经常会引起我们的注意和好奇，那就是“回文”。有一副据说是至今无解的对联“上海自来水来自海上”就是一个经典的回文的例子。同样的，在信息学竞赛中也有各种各样与回文有关的题目。下面我们一起来走进这个神秘的世界吧——（热身题）回文质数（FromUSACO）因为151即是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以151号是回文质数。写一个程序来找出范围[a,b](5<=a

2、，一行一个。样例输出57111011311511811913133533733839999从此题数据范围来看,若用朴素的循环数字表进行判断在时间限制内无法得解,那么就需要我们利用回文数的性质来进行优化,这里我们可以采用构造法进行解答。如果要构造出n位数中的所有回文数，我们可以通过回文数左右相同的性质只构造出n位数中的左半部分，右半部分镜象处理，当n是奇数时,将前1~[n/2]+1镜象后添加到右半部分，到n是偶数时将前1~[n/2]镜象后添加到右半部分，这样即可将复杂度降为sqrt(10^k)（当n为奇数时,k=n+1/2,当n为偶数时,k=n/2);如

3、此一来时间复杂度即可满足题目要求，再加以素数判断，问题得解。（标准程序：hw_1.cpp）热身完毕了吗？那么真正的挑战就开始了——DP类型的回文类型题：（例题1）调整队形学校艺术节上，规定合唱队要参加比赛，各个队员的衣服颜色不能很混乱：合唱队员应排成一横排，且衣服颜色必须是左右对称的。例如：“红蓝绿蓝红”或“红蓝绿绿蓝红”都是符合的，而“红蓝绿红”或“蓝绿蓝红”就不符合要求。合唱队人数自然很多，仅现有的同学就可能会有3000个。老师希望将合唱队调整得符合要求，但想要调整尽量少，减少麻烦。以下任一动作认为是一次调整：1、在队伍左或右边加一个人（衣服颜色依

4、要求而定）；2、在队伍中任两个人中间插入一个人（衣服颜色依要求而定）；3、剔掉一个人；4、让一个人换衣服颜色；老师想知道就目前的队形最少的调整次数是多少，请你编一个程序来回答他。因为加入合唱队很热门，你可以认为人数是无限的，即随时想加一个人都能找到人。同时衣服颜色也是任意的。输入格式第一行是一个整数n(1<=n<=3000)。第二行是n个整数，从左到右分别表示现有的每个队员衣服的颜色号，都是1到3000的整数。输出格式一个数，即对于输入队列，要调整得符合要求，最少的调整次数。样例输入512243样例输出2设a[i]为第i个人衣服的颜色，F[i,j]为第

5、i到第j个人需要的调整的最少次数，那么F[i,j]=min{1.F[i+1][j-1]+1(且满足a[i]!=a[j]，意思是将i或j其一变色来达成匹配）2.F[i+1][j]+1(且满足a[i]!=a[j],意思将第i人删除或者为匹配第i个人多加一人到j后面）3.F[i][j-1]+1(且满足a[i]!=a[j],同上意思将第j人删除或为匹配第j人多加一人到i后面）4.F[i+1][j-1]（且满足a[i]=a[j],意为第i人与第j人衣着相同不需调整）}边界是F[i][i]=0;则F[1][n]即为最终答案。（标准程序：hw_2.cpp）（例题2）

6、回文字如果一个单词从前和从后读都是一样的，则称为回文字。如果一个单词不是回文字，则可以把它拆分成若干个回文字。编程求一个给定的字母序列，最少要分割成几部分，使每一部分都为回文字。输入格式：输入文件有且只有一行，包含一个字符串。字符串由小写英文字母组成（a-z），长度不超过100。输出格式：输出文件只一行，为最少的回文字个数。样例1样例2样例3输入anabanabaccbcbanavolimilana输出235样例1说明：(不用输出)#1a_naban#2aba_cc_bcb#3ana_v_o_limil_ana设f[i,j]为第i个字母到第j个字母中的

7、最少的回文字个数，s[i][j]为母串中第i到第j子串，当s[i][j]为回文字时,f[i][j]=1；否则f[i][j]=min(f[i][k]+f[k+1][j]);最后f[1][n]即为答案。（标准程序：hw_3.cpp）（例题3）回文词（FromIOI2000）回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“d

8、Ab3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。输入格式