集訓(xùn)隊(duì)作業(yè)解題報(bào)告tournament_第1頁(yè)
集訓(xùn)隊(duì)作業(yè)解題報(bào)告tournament_第2頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、N個(gè)選手參加了一次比賽,比賽的規(guī)則如下:每次任意選擇兩個(gè)不同的選手?jǐn)?shù)據(jù)規(guī)模:N=100000,以前比賽盤數(shù) M=1000000判斷選手PP能戰(zhàn)勝的選手,再通過這選手找他們能戰(zhàn)勝的對(duì)手(P a,a b,那么就可如果最終其他選手都能被淘汰,那么P 就可能成為冠軍,否則肯定不能。O(N+M),則判斷所有人的復(fù)雜度就成了 O(N2+NM),考慮到數(shù)據(jù)這個(gè)復(fù)雜度顯然是不能接受的性質(zhì)一:如果A 能得到冠軍,而 B 能戰(zhàn)勝 A,則 B 能得到冠軍。AB擊敗A,B2)BABA淘汰剩下的選手。最后剩下 A,B B B BB都可以戰(zhàn)勝,那么B 就可以?shī)Z冠。通過這個(gè)性質(zhì),得到解題思路設(shè)兩個(gè)U,V,U 表示能得到冠軍

2、選手的集合,V 表示尚未確定選手U 中(方法下面有說明,而剩UQ 進(jìn)行處理V 中掃VPQ,則由性質(zhì)一可知P可以成為冠軍,那么就從 VQQU U 每個(gè)元素U 以?shī)Z冠的,而因?yàn)樗屑蟄中的選手均能戰(zhàn)勝集合VV中選用最直接的方法,先讓 1v2,勝者再同 3 號(hào)選手比賽,這樣一直下去,決出勝利 下來LN 比賽,只要N 是否擊敗過L 即可,若N 擊敗L,則勝利者必定是N,否則無論 L 之前是否戰(zhàn)勝N 都讓 L 繼續(xù)成為勝利者。這樣每次度是O(N+M)。在U 中選取元素P V 中哪些元素可以戰(zhàn)勝P其補(bǔ)集,即哪些元素不能戰(zhàn)P。不能戰(zhàn)勝 P 的元素顯然P 曾戰(zhàn)勝過的,因素P 后,集合|V|=Degree(p

3、),所以總掃描次數(shù)不超過Degree(Pi)=M。因而整個(gè)算法復(fù)雜度為 O(N+M)XIOlimpiadinInformaticsThe IIstageSourcefile:tur.(=pas,p) Memory limit: 32 MBAlternativeformats:TheInternationalX-GameFederation anisesatournamentinwhichprogrammesthatplay thisgameparticipate.nprogrammesnumberedfrom1tontakepartinthecompetition.The rulesofthe

4、tournamentareasfollows:whilethereremainsmorethanoneprogrammeinthe tournament, twoofthem (distinct)are randomly chosentoplaya game. Thedefeated one (therearenodrawsintheX-Game)dropsoutofthetournamentandthewholeprocedureis repeated.Thesoleprogrammewhichstaysinthetournamentafteralln-1gameshavebeen play

5、ed is the winner.The fedaration has a table of results of previous tournaments. It is known, that the programmesplaydeterministicly(i.e.inrepeatablefashion)andinexactlythesamewayas in previous tournaments.So, if twoprogrammes have already played one against another then their next game will end with

6、 the same result. If, however, they have never played against each other, thee of the game cannotbepredicted - both have a chance of winning.Thefederationwouldliketoknowalistofallprogrammeswhichhaveachanceof winning the tournament.Writeaprogrammereadsfromthestandardinputthenumberofparticipatingprogr

7、ammesandthetable of results of their previous games,determinesallprogrammeswhichhaveachanceofwinningthewritesetothestandardlineoftheinputcontainsanintegern,1=n=100.000.Thenextnlinescontain the table of results of previous games: i+1st line contains an integer k_i, 0 = k_i n, followedby k_i numbers o

8、fprogrammes,not equal to i, in increasing order - those are the numbersofprogrammes,withwhichtheprogramme ihas previously won.The numbersin linesareseparatedbysinglespaces.Thenumberofallknownresultsofpreviousgamesdoes not exceed 1.000.000.The and only line of the standard output should contain the number w of programmes which have a chance of winning the tournament, followed by w number

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論