走进回文的神秘世界中

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

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

3、）热身完毕了吗？那么真正的就开始了DP 类型的回文类型题：（例题 1）调整队形学校艺术节上，规定合唱队要参加比赛，各个队员的衣服颜色不能很排成一横排，且衣服颜色必须是左右对称的。：合唱队员应例如：“红蓝绿就不符合要求。”或“红蓝”都是符合的，而“红蓝绿红”或“蓝绿”合唱队人数自然很多，仅现有的同学就可能会有 3000 个。老师希望将合唱队调整得符合要求，但想要调整尽量少，减少麻烦。以下任一动作认为是一次调整：1、在队伍左或右边加一个人（衣服颜色依要求而定）；2、在队伍中任两个人中间3、剔掉一个人；4、让一个人换衣服颜色；一个人（衣服颜色依要求而定）；老师想知道就目前的队形最少的调整次数是多少，

4、请你编一个程序来回答他。因为加入合唱队很热门，你可以认为人数是无限的，即随时想加一个人都能找到人。同时衣服颜色也是任意的。输入格式第一行是一个整数 n(1=n=3000)。第二行是 n 个整数，从左到右分别表示现有的每个队员衣服的颜色号，都是 1 到 3000的整数。输出格式一个数，即对于输入队列，要调整得符合要求，最少的调整次数。样例输入51 2 2 4 3样例输出2设 ai为第 i 个人衣服的颜色，Fi,j为第 i 到第 j 个人需要的调整的最少次数，那么Fi,j = min 1.Fi + 1j - 1 + 1 (且满足 ai != aj，意思是将 i 或 j 其一变色来达成匹配）2.Fi

5、 + 1j + 1 (且满足 ai != aj, 意思将第 i 人删除或者为匹配第 i 个人多加一人到 j 后面）3.Fij - 1 + 1 (且满足ai != aj, 同上意思将第j 人删除或为匹配第j 人多加一人到 i 后面）4.Fi + 1j - 1 （且满足 ai = aj, 意为第 i 人与第 j 人衣着相同不需调整）边界是 Fii = 0;则 F1n即为最终。（标准程序：hw_2.cpp）（例题 2）回文字如果一个单词从前和从后读都是一样的，则称为回文字。如果一个单词不是回文字，则可以把它拆分成若干个回文字。编程求一个给定的字母序列，最少要分割成几部分，使每一部分都为回文字。输入格

6、式：输入文件有且只有一行，包含一个字符串。字符串由小写英文字母组成（a-z），长度不超过 100。输出格式：输出文件只一行，为最少的回文字个数。样例 1 说明：(不用输出)设 fi,j为第 i 个字母到第 j 个字母中的最少的回文字个数，sij为母串中第 i 到第 j 子串，当 sij为回文字时,fij = 1；否则 fij = min(fik + fk + 1j);最后 f1n即为。（标准程序：hw_3.cpp）（例题 3）回文词（From IOI 2000）回文词是一种对称的字符串也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过若干字符，都可以变成一

7、个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需的最少字符数。比如字符串“ Ab3bd ”， 在两个字符后可以变成一个回文词（“ dAb3bAd”或“Adb3bdA”）。然而，两个以下的字符无法使它变成一个回文词。输入格式第一行包含一个整数N，表示给定字符串的长度，3=N=5000第二行是一个长度为N 的字符串，字符串由大小写字母和数字。输出格式一个整数，表示需要的最少字符数。样例输入5Ab3bd#1a_naban#2aba_cc_bcb#3ana_v_o_limil_ana样例 1样例 2样例 3输入anabanabaccbcbanavolimilana输出235样例输出2要想

8、知道最少需要添加多少个字母，只需求得串中的最长的回长度 L(这个回后其他所有的字不一定是连续的),设串总长为S,那么即是说S 串中除去了L 这个回母都需要添加一个字母与之匹配。那么现在问题变成求母串中的最长回文子串（非连续），由于回左右相同，只需将母串翻转与母串进行一次最长公共子串长度的计算，即可得解。这样就将问题转化为了熟悉的 LCS（最长公共子序列）。方程为 Fij = maxfi - 1j - 1 + 1(ai = aj), fi - 1j, fij - 1;数学构造的回文类型题：（例题 4）回文数一个自然数如果把所有数字倒过来以后和原来的一样，那么称它为回文数。例如151 和 7533

9、57可以把所有回文数从小到大排成一排：1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, .注意 10 不是回文数，虽然可以把它写成 010，但是在本题中前导 0 是不允许的。你的任务是求出第 i 小的回文数。例如第 1,12,24 小的回文数分别是 1,33,151。输入格式输入只有一行，即 i(1=i=2*109)。输出格式输出只有一行，即第 i 小的回文数。样例输入24样例输出151这道题目看完后第法应该是枚举后 const，但看看数据范围就会放弃这个想法了。const 肯定要上 GB 所以说肯定不可取。枚举也是不可能的，要超时，而且要高精度。那么剩下的想法就是

10、要利用数学方法进行构造了。首先来枚举一下小的数101111121202 1001212 1111222 122112311223344141242 1441这样对齐后就很容易看出来规律了。首先定义一下 L 代表的是回文数的长度。当 L=1 or 2 时都有 9 个回文数当 L=3 or 4 时都有 910 个回文数当 L=4 or 5 时都有 9102 个回文数让这样看当 L=3 or 4 时回文数的同式可以表示为：XYX or XYYX根据乘法原理X 的可能个数为 9Y 的可能个数为 10以此类推，可以发现最外层的数都有 9 种而中间的数字都有 10 种。这样的规律就可以用于实现程序了。首先

11、 const 两个表（对应外部和），表示长度为 L 的回文数有多少个逐步把每一个位置上的数都用一个很小的表查出来。就构造完成了。复杂度十分小，仅为O(L div 2)。好了，你对回文是不是已经有了一些感觉了呢？试试看做下面的练习题来测试一下自己吧！（练习题 1）Calf Flac （From USACO）据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去这些牛制造的奇观(最棒的回文)。在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为要考虑 A-Z和a-z。要你寻找的最长的回文的文章是一个不超过 20,000 个字符的字

12、符串。输出),只需保证最长的回文不会超过 2,000 个字符(在除去标点符号、空格之前)。输入格式一个不超过 20000 个字符的文件。输出格式输出的第一行应该包括找到的最长的回文的长度。下一个行或几行应该包括这个回文的原文(没有除去标点符号、空格)，把这个回文输出到一行或多行(如果回文中包括换行符)。如果有多个回文长度都等于最大值,输出在较前位置出现的。样例输入Confucius say: Madam, Im Adam.样例输出：11Madam, Im Adam（练习题 2）送给 MM 的生日（From Matrix67）*注：本题可能有一定的难度，请根据自己的实际情况选做。10 月 11

13、日是 MM 的生日，Matrix67 打算自己 DIY 一些抱枕送给 MM。Matrix67 手中有一块矩形花布，花布分成了M x N 个小格子，有些格子的花色相同，有些格子的花色不同。为了使最终成品更美观，Matrix67 希望用于 DIY 的布匹都是正方形的，并且满足布匹花色上下对称且左右对称。为此，他希望能计算出这块花左右对称的小正方形。一共包含有多少个上下对称且举例来说，Matrix67 手中的花布大小为 6 x 4，上面共有 5 种花色：ABACDA DCDEAA ABABAA DDCBBA则这块一共有 26 个上下对称且左右对称的正方形，其中包括最左上角的 3x3 正方形、右边 4 个 A 组成的 2x2 正方形，当然还有 24 个 1x1 的小正方形。输入格式第一行输入两个用空格隔开的正整数 M,N，表示 Matrix67 手中的格子布分为M 行N 列。以下 M 行每行 N 个字符，描述布匹的花色。用 26 个大写字母来区别不同的花色，相同的字母代表相同的花色，不同的字母代表不同的花色。输出格式输出在 Matrix67