noip模擬題0039冬令營選手命題a.king

1、A. 擒賊先擒王(King)公元 3941 年 10 月，宇宙中最具野心的 X 星人發(fā)現(xiàn)了地球。他們以月球為據(jù)點，向人類開戰(zhàn)。同年 12 月 7 日，X 星人一次成功的到重創(chuàng)，以至在軍事力量上，人類無法與X 星人抗衡。，使人類遭X 星人正沉醉在成功的喜悅中時，人類社會的頭號軍事材料。Military Committee，世界反，地潛入月球，盜取了X 星的一份WREAMC(World Resist Extraterrestrial Aggres)于 12 月 8 日凌晨 4 時接到了這份材料，通過 3 小時的所有成員的個人檔外來研究，WREAMC 有足夠的案。據(jù)宇宙法513 條：說明該材料中包含

2、了X 星是宇宙生物的唯一標識。然而，WREAMC 發(fā)現(xiàn)，X 星 的個人集中有些所描述的內(nèi)容本質(zhì)上是一樣的。換句話說，某些成員在該集中出現(xiàn)。WREAMC 猜想，某個成員的集出現(xiàn)的頻率越高，該成員在 X在該星中的地位就越高。而出現(xiàn)頻率最高的，自然就是 X 星應(yīng)該相信WREAMC 成員的的首領(lǐng)（你不必懷疑該猜想的正確性，）。正所謂“擒賊先擒王”，在人類軍事力量處于劣勢的情況下，WREAMC 決定集中力量，消滅 X 星的首領(lǐng)。你的任務(wù)就是根據(jù)這份集，幫助WREAMC 找到 X 星首領(lǐng)的。為了便于你的研究，WREAMC 已經(jīng)將(BNF)：集簡化成了巴-瑙爾范式= ( | , | )= = = 0 | 1

3、 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |注：其中“=”表示定義為，“|”表示或，“”內(nèi)的項可以重復(fù)任意多次或不出現(xiàn)。X 星人的個人和人類的一樣，包括了本人的各種屬性。為了便于研究，用不同的整數(shù)來表示不同的屬性，數(shù)值相同則屬性相同。與人類略有不同，X 星人的個人中還包含他親生的個人。X 星人的個人X 星人的個人中的屬性中的屬性女女都可能有重復(fù)，這些重復(fù)將被忽略?？梢园慈我忭樞蛟谥谐霈F(xiàn)?！据斎胛募枯斎胛募牡?1 行為輸入文件的第 2 行至第n集中的條數(shù)n(1n100)。行每行表示一條字符。每條的長度不超過輸入文件中沒有多余的空格。輸入文件中保證X 星中有且僅有一個首

4、領(lǐng)?！据敵鑫募枯敵鑫募袃尚休敵鑫募谝恍袨橐粋€整數(shù)，表示 AAA的次數(shù)。首領(lǐng)在集中出現(xiàn)輸出文件第二行為X 星首領(lǐng)在輸入文件首次出現(xiàn)的的序號?！据斎胼敵鰳永縄nput.txt6(3,3,(1,3),2,(2,3),(3,2)(2,(3,1),3,(3,2),(1,3,1)(2,3,(3,1),(1,3,1)(1231231231)(1231231231)(1231231231)Output.txt21解題1判斷兩個是否相等在解決這道題目之前，先分析怎樣判斷兩個是否相等。本題中123具有以下特點：由若干屬性和若干子組成。中重復(fù)的屬性描述和本質(zhì)相同的子都將被忽略。中屬性具有無序性。由此可見，實

5、際上是一個由屬性組成的集合。由于本題中采用可以看作是一個非空有限集合，且該不同的整數(shù)來表示不同的屬性，因此，集合的元素既可以是整數(shù)，也可以是集合。這種集合簡稱為“可嵌套的集合”。而判斷兩個是否相等，實質(zhì)上就是比較它們對應(yīng)的集合是否相等。下面給出“可嵌套的集合”的具體定義：若干整數(shù)組成的集合是“可嵌套的集合”；若干“可嵌套的集合”和若干整數(shù)組成的集合是“可嵌套的集合”。由此可見，“可嵌套的集合”有著明顯的遞歸定義，因此，容易想到采用具有遞歸性質(zhì)的數(shù)據(jù)結(jié)構(gòu)來描述這種集合。顯然，一個沒有重復(fù)元素的可嵌套的集合可以用一棵多叉樹來表示。例如，集合1,2,3,1,2,3可以表示成圖 1 所示的樹：Root

6、132321圖一判斷兩個集合是否相等，可以通過比較它們所對應(yīng)的多叉樹是否相等。由于集合元素的無序性，需要先將樹的節(jié)點按一定規(guī)則排序，然后再進行比較。若集合中有重復(fù)元素，則要先將重復(fù)元素剔除掉。而判斷元素是否重復(fù)，又可以通過“判斷兩個集合是否相等”的函數(shù)來完成。這種方法是建立在樹形結(jié)構(gòu)上的。由于多叉樹的和管理都不方便，可以考慮不建樹，直接對讀入的字符串進行處理。即將一個原始規(guī)則做適當(dāng)?shù)恼{(diào)整，使之用一個限定格式的串表示。這樣，兩個可以歸結(jié)為兩個串之間的比較。串，按一定的比較，就用過程 Adjust(var S:string)來完成對以下幾步組成：串S 的調(diào)整。Adjust 過程主要由1將S 的元素

7、分離出來，記為t1,t2,tm；2若ti是子，則 Adjust(ti)；3將t1,t2,tm排序，去掉重復(fù)的元素后按順序連接起來，并重新賦值給串S。由于本題所給的數(shù)據(jù)范圍比較小，這種算法的時空復(fù)雜度都可以承受。但編程有些麻煩。下面介紹一種我認為編程復(fù)雜度更低的算法。這種算法建立在集合相等的另一種表示方法之上，即兩個集合 A、B 相等，當(dāng)且僅當(dāng)A 包含B 且 B 包含A。下面定義兩個函數(shù)：Func Equal(A,B:string): Func Include(A,B:string):;判斷集合 A 和 B 是否相等; 判斷集合 A 是否包含于集合 B判斷集合A 和B 是否相等可以分以下 3 種

8、情況：上面這三種情況，條件 1、2 可以看作是邊界條件，條件 3 可以看作是判斷集合是否相等的遞推求值公式。這三種情況可以用一條語句進行處理，即：Equal:=(A=B) or L(A) and L(B) and Include(A,B) and Include(B,A);其中，L(S)返回 S 是否不只包含一個屬性（單元素）Include(A,B)可以通過下面步驟實現(xiàn)：最后，還要注意一點：屬性 01 和 1 都有可能在中出現(xiàn)，且 01 和 1 是相等的。因此，比較兩個屬性是否相等，不能簡單的直接用字符串比較?？梢缘耐瑫r將中多余的 0 去掉，再比較它們是否相等。在讀入2求出“首領(lǐng)”的知道了如何

9、判斷兩個集合是否相等，接下來的工作就好做了。主程序如下：for i:=1 to n do Checkedi:=False; MaxCount:=0;for i:=1 to n do將集合A 的元素分離為 A1,A2,An將集合B 的元素分離為B1,B2,Bm如果存在i(1in)，使得表達式Equal(Ai,B1) or Equal(Ai,B2) or or Equal(Ai,Bm)的值為False，則說明元素 Ai沒有在集合 B 中出現(xiàn)。因此，集合A 不包含于集合B。否則，若所有的i，上述表達式均成立，則集合A 包含于集合BY1. 串 A=串 BN集合A=集合BY2. 集合A 是單元素或者集合

10、B 是單元素N集合A集合B3集合A 包含集合BY且集合B 包含集合AN集合A=集合B集合A 集合Bif not Checkedi then begin Checkedi:=True; Count:=1;for j:=i+1 to n doif not Checkedj thenif Equal(Si,Sj) then begin比較 Inc(Count);Checkedj:=True end;if CountMaxCount then begin MaxCount:=Count;King:=i endend;Wrin(MaxCount); Wrin(King)i 和j3小結(jié)這道題目的關(guān)鍵在于比

11、較兩個“”是否相等。根據(jù)“”的描述，很容易聯(lián)想到廣義表這種數(shù)據(jù)結(jié)構(gòu)。廣義表一般用樹來表示，但由于題目中涉及到對樹點的刪除、排序，操作復(fù)雜，空間消耗也很大。由于“”中的屬性以及“子”具有無序性和無重復(fù)性，因此，可以采用集合來表示“ 兩個集合是否相等?！薄＿@樣，比較兩個“”是否相等，實際上就是判斷一般來說，題目中給出的數(shù)據(jù)對象都十分具體，而要將其抽象成計算機能夠處理的數(shù)據(jù)結(jié)構(gòu)。本題若采用廣義表的結(jié)構(gòu)，之所以沒有集合方便，就在于集合能更精確的描述“問題是非常重要的?！边@個數(shù)據(jù)對象。由此可見，數(shù)學(xué)模型的選擇對解決出題說明King 是這三道題目當(dāng)中相對最簡單的一題。由于所給出的數(shù)據(jù)規(guī)模并不大，因此，很多算法都能解決這道題。本文中就提到了兩種不同的算法。正因為該題算法具有多樣性，因此，處于不同水平的選手都可以找到適合自己的算法。但不同的算法有著不同的編程復(fù)雜度。“磨刀不誤砍柴功”，在競賽中，應(yīng)該花一定的時間，以確定一個編程復(fù)雜度比較低的算法。為了選手是否細心，在題目中我并沒有規(guī)定整數(shù)的首位數(shù)字不為 0。這在一定程度上增加了這道題目的難度。本題主要選手選擇算法的能力和細心程度。測試數(shù)據(jù)說明“擒賊先擒王”是本次作業(yè)中相對最簡單的題目。的是選手選擇算法的能力和細心程度