數(shù)據(jù)結(jié)構(gòu)競賽題目集錦

1、數(shù)據(jù)結(jié)構(gòu)競賽題目集錦1. 發(fā)現(xiàn)環(huán)（題目來源：2017藍(lán)橋杯決賽）問題描述小明的實(shí)驗(yàn)室有 N臺電腦，編號1No原本這N臺電腦之間有N-1條數(shù)據(jù)鏈接相連，恰 好構(gòu)成一個樹形網(wǎng)絡(luò)。在樹形網(wǎng)絡(luò)上，任意兩臺電腦之間有唯一的路徑相連。不過在最近一次維護(hù)網(wǎng)絡(luò)時(shí)，管理員誤操作使得某兩臺電腦之間增加了一條數(shù)據(jù)鏈接， 于是網(wǎng)絡(luò)中出現(xiàn)了環(huán)路。環(huán)路上的電腦由于兩兩之間不再是只有一條路徑，使得這些電腦上的數(shù)據(jù)傳輸出現(xiàn)了 BUG為了恢復(fù)正常傳輸。小明需要找到所有在環(huán)路上的電腦，你能幫助他嗎？ 輸入格式第一行包含一個整數(shù) No以下N行每行兩個整數(shù) a和b,表示a和b之間有一條數(shù)據(jù)鏈接相連。對于30%勺數(shù)據(jù)，1 = N =

2、1000對于 100%勺數(shù)據(jù)，1 = N = 100000,1 = a, b = N輸入保證合法。輸出格式按從小到大的順序輸出在環(huán)路上的電腦的編號，中間由一個空格分隔。樣例輸入51 23 12 42 55 3樣例輸出1 2 3 52. 小朋友排隊(duì)（題目來源：第五屆藍(lán)橋杯預(yù)賽 C/C+本科B組）問題描述n個小朋友站成一排?，F(xiàn)在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個小朋友。每個小朋友都有一個不高興的程度。開始的時(shí)候，所有小朋友的不高興程度都是0。如果某個小朋友第一次被要求交換，則他的不高興程度增加 1,如果第二次要求他交換，則他的不高興程度增加 2 （即不高興程度為 3）

3、，依次類推。當(dāng)要求某個小朋友第k次交換時(shí)，他的不高興程度增加 k。請問，要讓所有小朋友按從低到高排隊(duì)，他們的不高興程度之和最小是多少。如果有兩個小朋友身高一樣，則他們誰站在誰前面是沒有關(guān)系的。 輸入格式輸入的第一行包含一個整數(shù) n,表示小朋友的個數(shù)。第二行包含n個整數(shù)H1 H2Hn，分別表示每個小朋友的身高。 輸出格式輸出一行，包含一個整數(shù)，表示小朋友的不高興程度和的最小值。樣例輸入33 2 1樣例輸出93. 剪郵票（題目來源：2016年藍(lán)橋杯） 問題描述如圖1所示,有12張連在一起的12生肖的郵票。現(xiàn)在你要從中剪下 5張來，要求必須 是連著的（僅僅連接一個角不算相連）。比如，圖 2,圖3中，

4、粉紅色所示部分就是合格的 剪取。請你計(jì)算，一共有多少種不同的剪取方法。圖1123456789101112圖2123456789101112圖34. 泊松分酒（題目來源：第三屆藍(lán)橋杯）問題描述泊松是法國數(shù)學(xué)家、物理學(xué)家和力學(xué)家。他一生致力科學(xué)事業(yè)，成果頗多。有許多著名的公式定理以他的名字命名，比如概率論中著名的泊松分布。有一次閑暇時(shí)，他提出過一個有趣的問題，后稱為：“泊松分酒”。在我國古代也提出過類似問題，遺憾的是沒有進(jìn)行徹底探索，其中流傳較多是：“韓信走馬分油”問題。有3個容器，容量分別為 12升，8升，5升。其中12升中裝滿油，另外兩個空著。要 求你只用3個容器操作，最后使得某個容器中正好有

5、6升油。下面的列表是可能的操作狀態(tài)記錄：12,0,04,8,04.3.59,3,09,0,31,8,31.6.5每行3個數(shù)據(jù)，分別表示12, 8，6升容器中的油量第一行表示初始狀態(tài)，第二行表示把12升倒入8升容器后的狀態(tài)，第三行是8升倒入5升，當(dāng)然，同一個題目可能有多種不同的正確操作步驟。本題目的要求是，請你編寫程序，由用戶輸入：各個容器的容量，開始的狀態(tài)，和要求 的目標(biāo)油量，程序則通過計(jì)算輸出一種實(shí)現(xiàn)的步驟（不需要找到所有可能的方法）。如果沒有可能實(shí)現(xiàn)，則輸出：“不可能”。例如，用戶輸入：12,8,5,12,0,0,6用戶輸入的前三個數(shù)是容器容量（由大到小），接下來三個數(shù)是三個容器開始時(shí)的油

6、量配置，最后一個數(shù)是要求得到的油量（放在哪個容器里得到都可以）則程序可以輸出（答案不唯一，只驗(yàn)證操作可行性）：12,0,04,8,04.3.59,3,09,0,31,8,31.6.5每一行表示一個操作過程中的油量狀態(tài)。5. 分巧克力（題目來源：第八屆藍(lán)橋杯 ） 問題描述兒童節(jié)那天有 K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友們。小明一共有N塊巧克力，其中第i塊是Hi x Wi的方格組成的長方形。為了公平起見，小明需要從這N塊巧克力中切出 K塊巧克力分給小朋友們。切出的巧克力需要滿足：1. 形狀是正方形，邊長是整數(shù)2. 大小相同例如一塊6x5的巧克力可以切出 6塊2x2的巧克力或者

7、2塊3x3的巧克力。當(dāng)然小朋友們都希望得到的巧克力盡可能大，你能幫小Hi計(jì)算出最大的邊長是多少么？輸入格式第一行包含兩個整數(shù) N和K。（1 = N, K = 100000）以下N行每行包含兩個整數(shù)Hi和 Wi。（1 = Hi, Wi = 100000）輸入保證每位小朋友至少能獲得一塊1x1的巧克力。輸出格式輸出切出的正方形巧克力最大可能的邊長。樣例輸入:2 106 55 6樣例輸出：26. 密文搜索（題目來源：2015年藍(lán)橋杯決賽） 問題描述福爾摩斯從X星收到一份資料，全部是小寫字母組成。他的助手提供了另一份資料：許多長度為8的密碼列表。福爾摩斯發(fā)現(xiàn)，這些密碼是被打亂后隱藏在先前那份資料中的。 請你編寫一個程序，從第一份資料中搜索可能隱藏密碼的位置。要考慮密碼的所有排列可能性。輸入格式輸入第一行：一個字符串s，全部由小寫字母組成，長度小于1024*1024緊接著一行是 一個整數(shù)n,表示以下有n行密碼，1