【正文】 W WBBBWWBW BBWWBWB BWWB BWBW BWBWB WBWBWBBW WBWBBWBW WBBWBWBW BWBWB WBWB BWWB BWBWWBB WBWWBBBW WWBBB WWW請編一個程序解大小為N的棋盤游戲(1 = N = 12)。要求用最少的移動步數實現。輸入 輸入僅一個整數N。輸出 用空格在棋盤的位置(位置從左到右依次為1, 2, ..., 2N+1)表示棋盤的狀態(tài)。輸出棋盤的狀態(tài)變換序列，每行20個數(除了最后一行)。 輸出的解還應當有最小的字典順序(即如果有多組移動步數最小的解，輸出第一個數最小的解；如果還有多組，輸出第二個數最小的解；...)。六、 數據結構Problem1火車棧題目描述 有一個車站，每天都會有N輛車進站，進站按從1到N的順序進站?，F在車站的站長想讓這些火車按照特定的順序出站，問可以做
到嗎？ 當N為5時，出站順序若為1 2 3 4 5，可以做到，但是順序若為5 4 1 2 3，則不行。 我們可以把火車進站就是壓棧，出站則是彈棧。輸入 一個N，在1000之內，下接一些出站序列，當讀到一個0時，則這個測試數據結束。輸出對每個序列輸出一行“Yes”或“No”。Problem2括號表達式題目描述 一個由左右括號39。(39。,39。)39。,39。[39。,39。]39。,39。{39。,39。}39。組成的表達式，判斷表達式是否合法，其中規(guī)則如下： (1)空串合法 (2)如果A合法，那么[A],(A),{A}都合法 (3)如果A，B都合法，那么AB合法輸入 輸入有若干行，每行一個表達式輸出輸出對于每一個表達式給出判斷，行數與輸入一樣，每行對應每一個表達式，如果為合法則輸出‘Yes’，否則輸出‘No’Problem3銀河英雄傳說題目描述 公元五八○一年，地球居民遷移至金牛座α第二行星，在那里發(fā)表銀河聯邦創(chuàng)立宣言，同年改元為宇宙歷元年，并開始向銀河系深處拓展。 宇宙歷七九九年，銀河系的兩大軍事集團在巴米利恩星域爆發(fā)戰(zhàn)爭。泰山壓頂集團派宇宙艦隊司令萊因哈特率領十萬余艘戰(zhàn)艦出征，氣吞山河集團點名將楊威利組織麾下三萬艘戰(zhàn)艦迎敵。 楊威利擅長排兵布陣，巧妙運用各種戰(zhàn)術屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場劃分成30000列，每列依次編號為1, 2, …, 30000。之后，他把自己的戰(zhàn)艦也依次編號為1, 2, …, 30000，讓第i號戰(zhàn)艦處于第i列(i = 1, 2, …, 30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當進犯之敵到達時，楊威利會多次發(fā)布合并指令，將大部分戰(zhàn)艦集中在某幾列上，實施密集攻擊。合并指令為M i j，含義為讓第i號戰(zhàn)艦所在的整個戰(zhàn)艦隊列，作為一個整體（頭在前尾在后）接至第j號戰(zhàn)艦所在的戰(zhàn)艦隊列的尾部。顯然戰(zhàn)艦隊列是由處于同一列的一個或多個戰(zhàn)艦組成的。合并指令的執(zhí)行結果會使隊列增大。 然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動。在交戰(zhàn)中，他可以通過龐大的情報網絡隨時監(jiān)聽楊威利的艦隊調動指令。 在楊威利發(fā)布指令調動艦隊的同時，萊因哈特為了及時了解當前楊威利的戰(zhàn)艦分布情況，也會發(fā)出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利的第i號戰(zhàn)艦與第j號戰(zhàn)艦當前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。 作為一個資深的高級程序設計員，你被要求編寫程序分析楊威利的指令，以及回答萊因哈特的詢問。 最終的決戰(zhàn)已經展開，銀河的歷史又翻過了一頁……輸入 輸入的第一行有一個整數T（1=T=500,000），表示總共有T條指令。 以下有T行，每行有一條指令。指令有兩種格式： i j ：i和j是兩個整數（1=i , j=30000），表示指令涉及的戰(zhàn)艦編號。該指令是萊因哈特竊聽到的楊威利發(fā)布的艦 隊調動指令，并且保證第i號戰(zhàn)艦與第j號戰(zhàn)艦不在同一列。 i j ：i和j是兩個整數（1=i , j=30000），表示指令涉及的戰(zhàn)艦編號。該指令是萊因哈特發(fā)布的詢問指令。輸出 。你的程序應當依次對輸入的每一條指令進行分析和處理： 如果是楊威利發(fā)布的艦隊調動指令，則表示艦隊排列發(fā)生了變化，你的程序要注意到這一點，但是不要輸出任何信息； 　如果是萊因哈特發(fā)布的詢問指令，你的程序要輸出一行，僅包含一個整數，表示在同一列上，第i號戰(zhàn)艦與第j號戰(zhàn)艦之間布置 的戰(zhàn)艦數目。如果第i號戰(zhàn)艦與第j號戰(zhàn)艦當前不在同一列上，則輸出1。Problem4矩形覆蓋題目描述 給出平面上n個矩形，求它們所形成的圖形的周長和面積輸入 輸入第一行為n(n=5000) 后面n行米行描述一個矩形，分別為4個整數(每兩個描述一個點，兩個點即為矩形的對點)，坐標值均在[10000，10000]之內輸出輸出有兩行，第一行為圖形的周長，第二行為面積Problem5最短路徑問題題目描述 求一個有向圖的起點到終點的最短路徑輸入 第一行有四個數n,e,s,t分別表示點數，邊數，起點，終點(n=5000) 后面e行，每行3個數分別表示邊的起點，終點，與權(有可能出現兩條起點終點相同的邊)輸出輸出s到t的最短路徑長度Problem6果子合并題目描述 在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經過n1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。 例如有3種果子，數目依次為1，2，9?？梢韵葘?堆合并，新堆數目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數目為12，耗費體力為12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的體力耗費值。 輸入 輸入第一行為N(N=100000)，第二行有N個整數，分別描述每個果子輸出 輸出一個數即最小代價七、 字符串處理Problem1相對分子質量題目描述 給出分子化學式（其中元素序號不大于50，可能為單原子），請計算相對分子質量。 形如“”的分子將以“CuSO4(H2O)5”的形式給出，即不會出現“.”和分子前的系數。輸入 輸入僅一行，給出化學分子式（不保證此物質存在）長度小于200個字符。輸出 輸出此分子的相對分子質量(結果保留兩位小數)Problem2表達式求值題目描述 給出一個算術表達式，包含39。+39。,39。39。,39。*39。,39。/39。,39。^39。，求這個表達式的值，字串長度小于100，結果小于實數范圍輸入 輸入僅一行，即表達式輸出 輸出表達式的值Problem3偵探推理題目描述明明同學最近迷上了偵探漫畫《柯南》并沉醉于推理游戲之中，于是他召集了一群同學玩推理游戲。游戲的內容是這樣的，明明的同學們先商量好由其中的一個人充當罪犯（在明明不知情的情況下），明明的任務就是找出這個罪犯。接著，明明逐個詢問每一個同學，被詢問者可能會說：證詞中出現的其他話，都不列入邏輯推理的內容。明明所知道的是，他的同學中有N個人始終說假話，其余的人始終說真?，F在，明明需要你幫助他從他同學的話中推斷出誰是真正的兇手，請記住，兇手只有一個！輸入 輸入由若干行組成，第一行有二個整數，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是參加游戲的明明的同學數，N是其中始終說謊的人數，P是證言的總數。接下來M行，每行是明明的一個同學的名字（英文字母組成，沒有主格，全部大寫）。往后有P行，每行開始是某個同學的名宇，緊跟著一個冒號和一個空格，后面是一句證詞，符合前表中所列格式。證詞每行不會超過250個字符。 輸入中不會出現連續(xù)的兩個空格，而且每行開頭和結尾也沒有空格。輸出 如果你的程序能確定誰是罪犯，則輸出他的名字；如果程序判斷出不止一個人可能是罪犯，則輸出 Cannot Determine；如果程序判斷出沒有人可能成為罪犯，則輸出 Impossible。Problem4最長公共子串題目描述 求N個字符串的最長公共子串，N＜＝20，字符串長度不超過255。輸入 輸入第一行為n，后面n行每行一個字符串輸出輸出其最長公共子串長度Problem5一元一次方程的解題目描述 給出一個一元一次方程，只含加減與未知數(3x、4x等形式是合法的)的一元一次方程，求方程的解(未知數為x)輸入 輸入一行，即方程長度小于100輸出輸出一個數，即方程的解，方程保證有解，結果保留2位小數Problem6多項式乘法題目描述 給出兩個多項式，包含+,,^與x、數字(x前面可能有系數，后面可能有次數)，求它們的乘積輸入 輸入有兩行，分別表示兩個多次項(長度小于100，次數小于100)輸出以標準的方式輸出他們的乘積，次數遞增 29 / 29