信息學聯賽知識：基本程序題集(3)

(2)任意一段連續的子串沒有連續出現3次(如：010101、001001001就不符合要求)

　　輸入

　　輸入僅一個數，即序列長度

　　輸出

　　輸出僅一個數，即滿足要求的序列總數

　　Problem9生日蛋糕

　　題目描述

　　要制作一個體積為N*pi的M層生日蛋糕，每層都是一個圓柱體。 設從下往上數第i(1 <= i <= M)層蛋糕是半徑為Ri, 高度為Hi的圓柱。當i < M時，要求Ri > Ri+1且Hi > Hi+1。 由于要在蛋糕上抹奶油，為盡可能節約經費，我們希望蛋糕外表面（最下一層的下底面除外）的面積Q最小。 令Q = S*pi 請編程對給出的N和M，找出蛋糕的制作方案（適當的Ri和Hi的值），使S最小。（除Q外，以上所有數據皆為正整數）

　　輸入

　　輸入兩行，第一行為N（N <= 10000），表示待制作的蛋糕的體積為N*pi；第二行為M(M <= 20)，表示蛋糕的層數為M。

　　輸出

　　輸出僅一行，是一個正整數S（若無解則S=0）。

　　四、 圖論算法

　　Problem1一筆畫問題

　　題目描述

　　給出一個圖，求其歐拉回路（若沒有回路，則求其歐拉路徑），若不存在則輸出'No solution'

　　輸入

　　輸入的第一行為邊數F(<=1024)，后面F行每行表示一條邊（定點標號范圍為1-500）

　　輸出

　　輸出一條合法的歐拉回路（路徑），若有多條滿足要求，輸出其字典序最小的那一個。

　　Problem2 Car的旅行路線

　　題目描述

　　住在城市A的Car想和朋友一起去城市B旅游。她知道每個城市都有四個飛機場，分別位于一個矩形的四個頂點上，同一個城市中兩個機場之間有一條筆直的高速鐵路，第I個城市中高速鐵路了的單位里程價格為Ti，任意兩個不同城市的機場之間均有航線，所有航線單位里程的價格均為t。

　　那么Car應如何安排到城市B的路線才能盡可能的節省花費，求其最少花費

　　輸入

　　第一行有四個正整數s，t，A，B。

　　S(0<S<=100)表示城市的個數，t表示飛機單位里程的價格，A，B分別為城市A，B的序號，(1<=A，B<=S)。

　　接下來有S行，其中第I行均有7個正整數xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第I個城市中任意三個機場的坐標，T I為第I個城市高速鐵路單位里程的價格。

　　輸出

　　輸出最小花費，保留一位小數

　　Problem3求割點與橋

　　題目描述

　　給定一個圖，求其割點與橋

　　輸入

　　第一行有兩個整數，n、e，即點數與邊數

　　后面e行，每行兩個整數v1、v2，表示點v1與v2相連

　　輸出

　　首先輸出所有割點，每行輸出一個

　　然后輸出所有橋，每行一條

　　(不用考慮順序)

　　Problem4十字繡

　　題目描述

　　布是一個n*m的網格，線只能在網格的頂點處才能從布的一面穿到另一面。每一段線都覆蓋一個單位網格的兩條對角線之一，而在繡的過程中，一針中連續的兩段線必須分處布的兩面。給出布兩面的圖案(實線代表該處有線,虛線代表背面有線)，問最少需要幾針才能繡出來？一針是指針不離開布的一次繡花過程。

　　輸入

　　輸入第1行兩個數N和M(1<=N,M<=200)。

　　接下來N行每行M個數描述正面。

　　再接下來N行每行M個數描述反面。

　　每個格子用.（表示空）,/（表示從右上角連到左下角）,\（表示從左上角連到右下角）和X（表示連兩條對角線）表示。

　　輸出

　　輸出一個數，最少要用的針數

　　Problem5舞會

　　題目描述

　　一個舞會邀請n個人，這n個人每一個人都有一個小花名冊，名冊里面寫著他所愿意交流的人的名字。比如說在A的人名單里寫了B，那么表示A愿意與B交流；但是B的名單里不見的有A，也就是說B不見的想與A交流。但是如果A愿意與B交流，B愿意與C交流，那么A一定愿意與C交流。也就是說交流有傳遞性。現在覺得需要將這n個人分為m組，要求每一組的任何一人都愿意與組內其他人交流。并求出一種方案以確定m的最小值是多少。

　　注意：自己的名單里面不會有自己的名字。

　　輸入

　　輸入第一行一個數n。接下來n行，每i+1行表示編號為i的人的小花名冊名單，名單以0結束。1<=n<=200。

　　輸出

　　輸出即m的最小值

　　Problem6休息中的小呆

　　題目描述

　　NOIP備戰之際，小呆正在悠閑（欠扁）地玩一個叫"最初夢想"的游戲。游戲描述的是一個叫pass的有志少年在不同的時空穿越對抗傳說中的大魔王chinesesonic的故事。小呆發現這個游戲的故事流程設計得很復雜，它有著很多的分支劇情，但不同的分支劇情是可以同時進行的，因此游戲可以由劇情和劇情的結束點組成，某些劇情必須要在一些特定的劇情結束后才能繼續發展。為了體驗游戲的完整性，小呆決定要看到所有的分支劇情--完成所有的任務。但這樣做會不會耽誤小呆寶貴的睡覺時間呢？所以就請你來解決這個問題了。

　　輸入

　　輸入會給你一個劇情流程和完成條件的列表，其中第一行有一個數n（0<n<100），表示總共有n個劇情結束點，第二行一個數m(0<m<=120)，表示由m個不同的劇情，下面的m行中每行有三個數i0<i<=100),j0<j<=100),k0<k<=1000)，表示從劇情結束點i必須完成一個耗費時間為k的劇情才能到達劇情結束點j。注意，這m行中出現的1不是劇情結束點而是游戲的開始，而n+1表示游戲結束。

　　輸出

　　輸出第一行為一個數，即你要告訴小呆完成整個游戲至少需要多少時間，第二韓有若干個數，即要經過的所有可能的劇情結束點（按升序輸出）。

　　Problem7最優布線問題

　　題目描述

　　校園里有n臺計算機，要將它們用數據線連接起來。由于計算機所處的位置不同，連接2臺計算機的費用往往是不同的。如果將每2 臺計算機都用數據線連接，勢必造成浪費。為了節省費用，可以采用數據的間接傳輸手段，即一臺計算機可以間接通過若干臺計算機(作為中轉)來實現與另一臺計算機的連接。如何用最少費用連接n臺計算機。

　　輸入

　　輸入數據。第一行有1個正整數n，表示計算機數。此后n行，每行有n個正整數。第x+1行，第y列的正整數表示直接連接第x臺計算機和第y臺計算機的費用。

　　輸出

　　輸出最小費用

　　Problem8磁盤碎片整理

　　題目描述

　　出于最高安全性考慮，司令部采用了特殊的安全操作系統。該系統采用一個特殊的文件系統。在這個文件系統中所有磁盤空間都被分配了相同尺寸的N塊，用整數1到N表識，每個文件占用磁盤上任意區域的一塊或多塊存儲區，未被文件占用的存儲塊被認為是可以使用的。如果文件存儲在磁盤上自然連續的存儲塊中，則能被以最快的速度讀出。

　　因為磁盤是均勻轉動的，所以存取上面的不同的存儲快需要的時間也不同。讀取磁盤開頭處的存儲比讀取磁盤結尾處的存儲塊快。根據以上現象，我們事先將文件按其存取頻率的大小用整數1到K標識。按文件在磁盤上最佳的存儲方法，1號文件將占用1，2……，S1的存儲塊，2號文件占用S1+1,S1+2……S1+S2的存儲塊，依次類推。為了將文件以最佳形式存儲在磁盤上，需要執行存儲酷塊移動操作。操作后，原空間將被釋放，新空間將被占用。

　　問對于一個文件序列，最少需要多少次移動操作才能以最佳方式存儲到磁盤上

　　輸入

　　輸入第一行包含兩個整數N，K，接下來K行每行描述一個文件，第一個數為Si，表示其存儲塊數量，后面有Si個整數，每個整數之間用空格隔開，表示該文件按自然順序在磁盤上占用的存儲塊標識，所有這些數都介于1和N之間，包括1和N。

　　所有磁盤空間的表識都不相同

　　輸出

　　輸出一個數，即最小移動次數

　　Problem9說謊島

　　題目描述

　　哥侖布在到達美州后，發現了一個奇特的島嶼。這個島嶼上的人狡猾且喜歡說謊，由于完全的謊言較易為人所識破，所以為了更加能夠迷惑別人，他們的言語往往是半真半假的。

　　由于對于環境的不熟悉，哥侖布有許多問題要請教島上的居民。當然他已經知道了島上居民的這一說謊習俗。

　　幸好，哥侖布的所有問題都只需回答"是"或者"否"，這樣便免去了許多繁復。假設哥侖布詢問了N個居民，對于每個居民只問兩個問題，每個居民只需對于每個問題回答"是"或"否"。根據居民的習俗，可以斷定兩個回答中必有一個是正確的，而另一個是錯誤的。同一個問題可以反復問多人。

　　哥侖布根據這N個人的回答，需要整理推斷出他所有問題的答案。但這一過程實在太復雜與困難了，因此希望你能夠編程求出所有可能答案的種數。

　　輸入

　　輸入第一行是兩個整數N（1≤N≤10000）、M（1≤M≤200），以空格分隔。分別表示詢問了N人，共有M個問題。整個輸入文件共N+1行。

　　第i+1行共有四個整數a,b,c,d，以空格分隔。表示第i個人對于第a個問題的答案是b, 對于第c個問題的答案是d。其中1≤a,c≤M。b和d為0時表示答案為"否；"為1時表示答案為"是"。

　　輸出

　　若不可能推出任何結果，即無解，輸出"NO ANSWER"；否則輸出可能答案組的個數。

　　Problem10 01串問題

　　題目描述

　　給定7個整數N,A0,B0,L0,A1,B1,L1，要求設計一個01串S=s1s2…si…sN，滿足：

　　1.si=0或si=1，1<=i<=N；

　　2.對于S的任何連續的長度為L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1)，0的個數大于等于A0且小于等于B0;

　　3.對于S的任何連續的長度為L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1)，1的個數大于等于A1且小于等于B1;

　　例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，則存在一個滿足上述所有條件的01串S=010101。

　　輸入

　　輸入僅一行，有7個整數，依次表示N,A0,B0,L0,A1,B1,L1（3<=N<=1000，1<= A0<=B0<=L0<=N，1<=A1<=B1<=L1<=N），相鄰兩個整數之間用一個空格分隔。

　　輸出

　　輸出僅一行，若不存在滿足所有條件的01串，則輸出一個整數-1，否則輸出一個滿足所有條件的01串。

　　Problem11海島地圖

　　題目描述

　　給出一個(h*w)的海島地圖，其中圖中1表示陸地，0表示水域，求所有島嶼中，面積最大的一個島嶼

　　輸入

　　輸入第一行為w，h(<=100)，表示圖的長與寬

　　后面有w行，每行有一個長為h的01串，用來描述整個地圖

　　輸出

　　輸出僅一個數，即最大的海島面積

　　五、 數學問題

　　Problem1數的劃分

　　題目描述

　　將整數n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。

　　例如：n=7，k=3，下面三種分法被認為是相同的。

　　1，1，5; 1，5，1; 5，1，1;

　　問有多少種不同的分法。

　　輸入

　　輸入僅一行，即N，K(N<=200,K<=20)

　　輸出

　　輸出僅一個數，即總共的方法數

　　Problem2最優分解方案

　　題目描述

　　給定整數N，將其分解為若干個互不相同的整數，是他們的乘積最大

　　輸入

　　輸入僅一個數，N(N<=1000)

　　輸出

　　輸出最大乘積

　　Problem3出棧序列統計

　　題目描述

　　棧是常用的一種數據結構,有n令元素在棧頂端一側等待進棧,棧頂端另一側是出棧序列.你已經知道棧的操作有兩·種:push和pop,前者是將一個元素進棧,后者是將棧頂元素彈出.現在要使用這兩種操作,由一個操作序列可以得到一系列的輸出序列.請你編程求出對于給定的n,計算并輸出由操作數序列1,2,…,n,經過一系列操作可能得到的輸出序列總數.

　　輸入

　　輸入一個整數n(1<=n<=50)

　　輸出

　　輸出一個整數，即可能輸出序列的總數目。

　　Problem4百事世界杯之旅

　　題目描述

　　每個瓶蓋上有一個球星的名字，有N個不同的球星，平均情況下，要買多少瓶飲料才能集齊所有名字

　　輸入

　　輸入一個數N(<=33)

　　輸出

　　輸出平均情況下的瓶數，若為整數則直接輸出，若為分數，則以真分數形式輸出，格式如下：

　　b

　　a-

　　c

　　Problem5電子鎖

　　題目描述

　　某機要部門安裝了電子鎖。m個工作人員每人發一張磁卡，卡上有開鎖的密碼特征，為了保證安全，規定至少n個人同時使用各自的磁卡才能將鎖打開。現在需要你計算一下，電子鎖上至少要有多少種特征，每個人的磁卡上至少要有幾種特征。同時輸出分配方案。

　　輸入

　　輸入僅一行，有兩個數即m(m<=7)，n(<=m且<=4)

　　輸出

　　輸出第一行為兩個數，既電子鎖上的特征數，與磁卡上的特征數

　　后面n行按字典序數出一個01序列，表識每個人磁卡上的擁有的特征，1表識有，0表示沒有。

　　Problem6堆塔問題

　　題目描述

　　有n個邊長為一的正立方體，在一個寬為1的軌道上堆塔，但它本身不能分離。

　　堆塔時底層必須有支撐，求對于n各正方體，又多少種方案

　　輸入

　　輸入僅一行n(n<=100)

　　輸出

　　輸出也只一行，即總方案數

　　Problem7取數游戲

　　題目描述

　　給出正整數n(<=1000000)和k(<n)，然后按下列方法取數:(n=16,k=4)

　　1: 取1  剩 15

　　2: 取2  剩 13

　　3: 取4  剩 9

　　4: 取8  剩 1

　　第五次取不夠，加上k個，現在共5個

　　5: 取1  剩 4

　　6: 取2  剩 2

　　第七次取不夠，加上k個，現在共6個

　　7: 取1  剩 5

　　8: 取2  剩 3

　　第九次取不夠，加上k個，現在共7個

　　9: 取1  剩 6

　　10: 取1  剩 4

　　11: 取1  剩 0

　　取完共取11次

　　輸入

　　輸入僅一行，即n，k

　　輸出

　　若取得完，則輸出取的次數，否則輸出'Error'

　　Problem8球迷購票

　　題目描述

　　球迷手上有100元與50元的鈔票，每張票50元，現在有m+n個球迷買票(m個手上持50元的，n個手上持100元的)，一開始售票員手上有錢，有多少排隊方案可以不出現沒有錢找的局面

　　輸入

　　輸入僅一行即m，n(m,n<=5000)

　　輸出

　　輸出有一行，即總得方案數

　　Problem9 Fibonacci公約數

　　題目描述

　　給出兩個fibonacci數，求一個最大的fibonacci數，滿足這個數是他們的最大公約數

　　輸入

　　輸入有兩行，分別是兩個Fibonacci數(<=10^2000)

　　輸出

　　即輸出他們的Fibonacci公約數

　　Problem10傳球問題

　　題目描述

　　Grant老師常和小朋友們一起玩一種傳球游戲。游戲是這樣進行的：

　　一群小朋友分成兩組，每組n人，圍成一個圈。每一個小朋友都有一個編號(1..n之間)，這個編號在其所在組中是唯一的。    游戲開始之前，Grant老師會發給每個小朋友一個球，球上也有編號(1..n之間)，并且一個組中的球不會有兩個相同編號。然后，所有小朋友必須閉上眼睛，游戲開始。隨著Grant老師口中的哨子發出的節奏，每個小朋友都用一只手把球傳到右邊，而用另一只手接左邊的來球。

　　突然，Grant老師的哨子停了，關鍵的時刻到了。小朋友馬上睜開眼睛，開始與同組的小朋友之間進行傳球，爭取以最短的時間把球傳到位。傳到位是指一個組中的每一個小朋友手上的球的編號與他自己的編號相同。最后獲勝的就是那個最先把球傳到位的組。如果一旦哪方出現傳球失誤(球沒被接到而落地)，或犯規（一個人手上拿兩個或兩個以上的球）這一組就被判輸。

　　這個游戲非常有趣，小朋友們玩了許多次。他們總結出一條經驗：總是兩個人之間對傳。也就是說，不會出現a把球傳給b，而b沒有把球傳給a的這種情況。這樣可以避免小朋友之間的失誤與犯規。不過還有個關鍵問題就是怎么傳。究竟應該把手上的球傳給誰？

　　現在需要你編一個程序來幫助小朋友們確定傳球方法。你的程序首先需要計算出從一種初始狀態開始：

　　子問題 1：至少需要幾次對傳才能將球傳到位。

　　子問題2：至少需要多少時間才能將球傳到位。每一個時間單位一個小朋友可以不做任何動作，也可以與另外一個小朋友之                 間進行對傳。

　　注意有些對傳可以同時進行。比如小朋友1與小朋友2之間的對傳和小朋友3與小朋友4之間的對傳就可以在一個時間單位之內完成，但是被計作兩次對傳。

　　輸入：

　　輸入第一行是一個整數 n (2<=n<=20000)。接下來有n 行，每行一個整數(1..n)，其中第(i+1)行的整數表示i號小朋友手上的球的編號。

　　輸出：

　　輸出只有二行，每行一個整數，分別表示子問題1和子問題2的解。

　　Problem11約瑟夫問題

　　題目描述

　　n個人排成一圈。從某個人開始，按順時針方向依次編號。從編號為1的人開始順時針"一二一"報數，報到2的人退出圈子。這樣不斷循環下去，圈子里的人將不斷減少。由于人的個數是有限的，因此最終會剩下一個人。試問最后剩下的人最開始的編號。

　　輸入

　　輸入一個正整數n，表示人的個數。輸入數據保證數字n不超過100位。

　　輸出

　　輸出一個正整數。它表示經過"一二一"報數后最后剩下的人的編號。

　　Problem12青蛙過河

　　題目描述

　　大小各不相同的一隊青蛙站在河左岸的石墩（記為A）上，要過到對岸的石墩(記為D)上去。河心有幾片菏葉(分別記為Y1…Ym)和幾個石墩(分別記為S1…Sn)。

　　青蛙的站隊和移動方法規則如下：

　　1．每只青蛙只能站在荷葉、石墩，或者僅比它大一號的青蛙背上（統稱為合法的落腳點）；

　　2．一只青蛙只有背上沒有其它青蛙的時候才能夠從一個落腳點跳到另一個落腳點；

　　3．青蛙允許從左岸A直接跳到河心的石墩、荷葉和右岸的石墩D上，允許從河心的石墩和荷葉跳到右岸的石墩D上；

　　4．青蛙在河心的石墩之間、荷葉之間以及石墩和荷葉之間可以來回跳動；

　　5．青蛙在離開左岸石墩后，不能再返回左岸；到達右岸后，不能再跳回；

　　6．假定石墩承重能力很大，允許無論多少只青蛙都可呆在上面。但是，由于石墩的面積不大，至多只能有一只青蛙直接站在上       面，而其他的青蛙只能依規則1落在比它大一號的青蛙的背上。

　　7．荷葉不僅面積不大，而且負重能力也有限，至多只能有一只青蛙站在上面。

　　8．每一步只能移動一只青蛙，并且移動后需要滿足站隊規則；

　　9．在一開始的時候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依規則6站在比其大一號的青蛙的背上。

　　青蛙希望最終能夠全部移動到D上，并完成站隊。

　　設河心有m片荷葉和n個石墩，請求出這隊青蛙至多有多少只，在滿足站隊和移動規則的前提下，能從A過到D。

　　輸入

　　輸入僅有兩行，每一行僅包含一個整數和一個換行/回車符。第一行的數字為河心的石墩數n（0<=n<=25），第二行為荷葉數m（0<=m<=25）。

　　輸出

　　輸出中僅包含一個數字和一個換行/回車符。該數字為在河心有n個石墩和m片荷葉時，最多能夠過河的青蛙的只數。

　　Problem13棋盤游戲

　　題目描述

　　大小為3的棋盤游戲里有3個白色棋子，3個黑色棋子，和一個有7個格子一線排開的木盒子。3個白棋子被放在一頭，3個黑棋子被放在另一頭，中間的格子空著。

　　初始狀態: WWW_BBB

　　目標狀態: BBB_WWW

　　在這個游戲里有兩種移動方法是允許的：

　　1. 你可以把一個棋子移到與它相鄰的空格；

　　2. 你可以把一個棋子跳過一個(僅一個)與它不同色的棋子到達空格。

　　大小為N的棋盤游戲包括N個白棋子，N個黑棋子，還有有2N+1個格子的木盒子。

　　這里是3-棋盤游戲的解，包括初始狀態，中間狀態和目標狀態：

　　WWW BBB

　　WW WBBB

　　WWBW BB

　　WWBWB B

　　WWB BWB

　　W BWBWB

　　WBWBWB

　　BW WBWB

　　BWBW WB

　　BWBWBW

　　BWBWB W

　　BWB BWW

　　B BWBWW

　　BB WBWW

　　BBBW WW

　　BBB WWW