1、走進(jìn)“回文”的神秘世界中在平時生活中，有一種現(xiàn)象經(jīng)常會引起的注意和好奇，那就是“回文”。有一副據(jù)說是至今無解的對聯(lián)“自來水來自海上”就是一個經(jīng)典的回文的例子。同樣的，在信息學(xué)競賽中也有各種各樣與回文有關(guān)的題目。下面（熱身題）回文質(zhì)數(shù)（From USACO）一起來走進(jìn)這個神秘的世界吧因為151 即是一個質(zhì)數(shù)又是一個回文數(shù)(從左到右和從右到左是看一樣的)，所以是回文質(zhì)數(shù)。寫一個程序來找出范圍a,b(5 = a b = 100,000,000)間的所有回文質(zhì)數(shù)。、151號輸入格式第 1 行: 二個整數(shù) a 和 b樣例輸入5 500輸出格式輸出一個回文質(zhì)數(shù)的列表，一行一個。樣例輸出5711101131

2、151181191313353373383從此題數(shù)據(jù)范圍來看,若用樸素的循環(huán)數(shù)字表進(jìn)行判斷在時間限制內(nèi)無法得解,那么就需要利用回文數(shù)的性質(zhì)來進(jìn)行優(yōu)化,這里可以采用構(gòu)造法進(jìn)行解答。如果要構(gòu)造出 n位數(shù)中的所有回文數(shù)，可以通過回文數(shù)左右相同的性質(zhì)只構(gòu)造出 n 位數(shù)中的左半部分，右半部分鏡象處理，當(dāng) n 是奇數(shù)時,將前 1n/2 +1 鏡象后添加到右半部分，到 n 是偶數(shù)時將前1n/2鏡象后添加到右半部分，這樣即可將復(fù)雜度降為sqrt(10k)（當(dāng)n 為奇數(shù)時,k=n+1/2,當(dāng) n 為偶數(shù)時,k=n/2); 如此一來時間復(fù)雜度即可滿足題目要求，再加以素數(shù)判斷，問題得解。（標(biāo)準(zhǔn)程序：hw_1.cpp

3、）熱身完畢了嗎？那么真正的就開始了DP 類型的回文類型題：（例題 1）調(diào)整隊形學(xué)校藝術(shù)節(jié)上，規(guī)定合唱隊要參加比賽，各個隊員的衣服顏色不能很排成一橫排，且衣服顏色必須是左右對稱的。：合唱隊員應(yīng)例如：“紅藍(lán)綠就不符合要求?！被颉凹t藍(lán)”都是符合的，而“紅藍(lán)綠紅”或“藍(lán)綠”合唱隊人數(shù)自然很多，僅現(xiàn)有的同學(xué)就可能會有 3000 個。老師希望將合唱隊調(diào)整得符合要求，但想要調(diào)整盡量少，減少麻煩。以下任一動作認(rèn)為是一次調(diào)整：1、在隊伍左或右邊加一個人（衣服顏色依要求而定）；2、在隊伍中任兩個人中間3、剔掉一個人；4、讓一個人換衣服顏色；一個人（衣服顏色依要求而定）；老師想知道就目前的隊形最少的調(diào)整次數(shù)是多少，

4、請你編一個程序來回答他。因為加入合唱隊很熱門，你可以認(rèn)為人數(shù)是無限的，即隨時想加一個人都能找到人。同時衣服顏色也是任意的。輸入格式第一行是一個整數(shù) n(1=n=3000)。第二行是 n 個整數(shù)，從左到右分別表示現(xiàn)有的每個隊員衣服的顏色號，都是 1 到 3000的整數(shù)。輸出格式一個數(shù)，即對于輸入隊列，要調(diào)整得符合要求，最少的調(diào)整次數(shù)。樣例輸入51 2 2 4 3樣例輸出2設(shè) ai為第 i 個人衣服的顏色，F(xiàn)i,j為第 i 到第 j 個人需要的調(diào)整的最少次數(shù)，那么Fi,j = min 1.Fi + 1j - 1 + 1 (且滿足 ai != aj，意思是將 i 或 j 其一變色來達(dá)成匹配）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 人衣著相同不需調(diào)整）邊界是 Fii = 0;則 F1n即為最終。（標(biāo)準(zhǔn)程序：hw_2.cpp）（例題 2）回文字如果一個單詞從前和從后讀都是一樣的，則稱為回文字。如果一個單詞不是回文字，則可以把它拆分成若干個回文字。編程求一個給定的字母序列，最少要分割成幾部分，使每一部分都為回文字。輸入格

6、式：輸入文件有且只有一行，包含一個字符串。字符串由小寫英文字母組成（a-z），長度不超過 100。輸出格式：輸出文件只一行，為最少的回文字個數(shù)。樣例 1 說明：(不用輸出)設(shè) fi,j為第 i 個字母到第 j 個字母中的最少的回文字個數(shù)，sij為母串中第 i 到第 j 子串，當(dāng) sij為回文字時,fij = 1；否則 fij = min(fik + fk + 1j);最后 f1n即為。（標(biāo)準(zhǔn)程序：hw_3.cpp）（例題 3）回文詞（From IOI 2000）回文詞是一種對稱的字符串也就是說，一個回文詞，從左到右讀和從右到左讀得到的結(jié)果是一樣的。任意給定一個字符串，通過若干字符，都可以變成一

7、個回文詞。你的任務(wù)是寫一個程序，求出將給定字符串變成回文詞所需的最少字符數(shù)。比如字符串“ Ab3bd ”， 在兩個字符后可以變成一個回文詞（“ dAb3bAd”或“Adb3bdA”）。然而，兩個以下的字符無法使它變成一個回文詞。輸入格式第一行包含一個整數(shù)N，表示給定字符串的長度，3=N=5000第二行是一個長度為N 的字符串，字符串由大小寫字母和數(shù)字。輸出格式一個整數(shù)，表示需要的最少字符數(shù)。樣例輸入5Ab3bd#1a_naban#2aba_cc_bcb#3ana_v_o_limil_ana樣例 1樣例 2樣例 3輸入anabanabaccbcbanavolimilana輸出235樣例輸出2要想

8、知道最少需要添加多少個字母，只需求得串中的最長的回長度 L(這個回后其他所有的字不一定是連續(xù)的),設(shè)串總長為S,那么即是說S 串中除去了L 這個回母都需要添加一個字母與之匹配。那么現(xiàn)在問題變成求母串中的最長回文子串（非連續(xù)），由于回左右相同，只需將母串翻轉(zhuǎn)與母串進(jìn)行一次最長公共子串長度的計算，即可得解。這樣就將問題轉(zhuǎn)化為了熟悉的 LCS（最長公共子序列）。方程為 Fij = maxfi - 1j - 1 + 1(ai = aj), fi - 1j, fij - 1;數(shù)學(xué)構(gòu)造的回文類型題：（例題 4）回文數(shù)一個自然數(shù)如果把所有數(shù)字倒過來以后和原來的一樣，那么稱它為回文數(shù)。例如151 和 7533

9、57可以把所有回文數(shù)從小到大排成一排：1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, .注意 10 不是回文數(shù)，雖然可以把它寫成 010，但是在本題中前導(dǎo) 0 是不允許的。你的任務(wù)是求出第 i 小的回文數(shù)。例如第 1,12,24 小的回文數(shù)分別是 1,33,151。輸入格式輸入只有一行，即 i(1=i=2*109)。輸出格式輸出只有一行，即第 i 小的回文數(shù)。樣例輸入24樣例輸出151這道題目看完后第法應(yīng)該是枚舉后 const，但看看數(shù)據(jù)范圍就會放棄這個想法了。const 肯定要上 GB 所以說肯定不可取。枚舉也是不可能的，要超時，而且要高精度。那么剩下的想法就是

10、要利用數(shù)學(xué)方法進(jìn)行構(gòu)造了。首先來枚舉一下小的數(shù)101111121202 1001212 1111222 122112311223344141242 1441這樣對齊后就很容易看出來規(guī)律了。首先定義一下 L 代表的是回文數(shù)的長度。當(dāng) L=1 or 2 時都有 9 個回文數(shù)當(dāng) L=3 or 4 時都有 910 個回文數(shù)當(dāng) L=4 or 5 時都有 9102 個回文數(shù)讓這樣看當(dāng) L=3 or 4 時回文數(shù)的同式可以表示為：XYX or XYYX根據(jù)乘法原理X 的可能個數(shù)為 9Y 的可能個數(shù)為 10以此類推，可以發(fā)現(xiàn)最外層的數(shù)都有 9 種而中間的數(shù)字都有 10 種。這樣的規(guī)律就可以用于實現(xiàn)程序了。首先

11、 const 兩個表（對應(yīng)外部和），表示長度為 L 的回文數(shù)有多少個逐步把每一個位置上的數(shù)都用一個很小的表查出來。就構(gòu)造完成了。復(fù)雜度十分小，僅為O(L div 2)。好了，你對回文是不是已經(jīng)有了一些感覺了呢？試試看做下面的練習(xí)題來測試一下自己吧?。ň毩?xí)題 1）Calf Flac （From USACO）據(jù)說如果你給無限只母牛和無限臺巨型便攜式電腦(有非常大的鍵盤),那么母牛們會制造出世上最棒的回文。你的工作就是去這些牛制造的奇觀(最棒的回文)。在尋找回文時不用理睬那些標(biāo)點(diǎn)符號、空格(但應(yīng)該保留下來以便做為要考慮 A-Z和a-z。要你尋找的最長的回文的文章是一個不超過 20,000 個字符的字

12、符串。輸出),只需保證最長的回文不會超過 2,000 個字符(在除去標(biāo)點(diǎn)符號、空格之前)。輸入格式一個不超過 20000 個字符的文件。輸出格式輸出的第一行應(yīng)該包括找到的最長的回文的長度。下一個行或幾行應(yīng)該包括這個回文的原文(沒有除去標(biāo)點(diǎn)符號、空格)，把這個回文輸出到一行或多行(如果回文中包括換行符)。如果有多個回文長度都等于最大值,輸出在較前位置出現(xiàn)的。樣例輸入Confucius say: Madam, Im Adam.樣例輸出：11Madam, Im Adam（練習(xí)題 2）送給 MM 的生日（From Matrix67）*注：本題可能有一定的難度，請根據(jù)自己的實際情況選做。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 正方形，當(dāng)然還有 24 個 1x1 的小正方形。輸入格式第一行輸入兩個用空格隔開的正整數(shù) M,N，表示 Matrix67 手中的格子布分為M 行N 列。以下 M 行每行 N 個字符，描述布匹的花色。用 26 個大寫字母來區(qū)別不同的花色，相同的字母代表相同的花色，不同的字母代表不同的花色。輸出格式輸出在 Matrix67