

下載本文檔
版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度個(gè)人棋牌室承包經(jīng)營(yíng)合同范本
- 2025年茶藝師服務(wù)禮儀試題及答案
- 2025年計(jì)算機(jī)技術(shù)與軟件專業(yè)審查試題及答案
- 2025年度新能源汽車充電位租賃與車位共享合作協(xié)議
- 二零二五年度山林分割與林業(yè)產(chǎn)業(yè)發(fā)展合作協(xié)議
- 2025年智慧工地施工安全責(zé)任協(xié)議范本
- 二零二五年度家長(zhǎng)監(jiān)督孩子勞動(dòng)權(quán)益保障協(xié)議
- 2025年度校園社團(tuán)特色團(tuán)建服務(wù)與文化交流合同
- 二零二五年度婚前財(cái)產(chǎn)分割協(xié)議與婚后財(cái)產(chǎn)共有合同
- 二零二五年度城市景觀美化專用護(hù)欄圍擋工程合同
- 廚房設(shè)備購(gòu)銷合同范本(一)與廚房設(shè)備采購(gòu)合同8篇
- 2025年中儲(chǔ)糧吉林分公司招聘(74人)筆試參考題庫(kù)附帶答案詳解
- 化糞池清掏協(xié)議書范本
- 2024-2025學(xué)年九年級(jí)化學(xué)人教版教科書解讀
- 2025年長(zhǎng)春醫(yī)學(xué)高等專科學(xué)校單招職業(yè)技能測(cè)試題庫(kù)及完整答案1套
- 2025年中國(guó)大唐集團(tuán)有限公司重慶分公司高校畢業(yè)生招聘筆試參考題庫(kù)附帶答案詳解
- 2025年西安鐵路職業(yè)技術(shù)學(xué)院高職單招高職單招英語(yǔ)2016-2024歷年頻考點(diǎn)試題含答案解析
- 化工原理完整(天大版)課件
- 《無人機(jī)槳發(fā)匹配試驗(yàn)技術(shù)規(guī)范》
- 2025年度酒店客房預(yù)訂渠道拓展與合作協(xié)議3篇
- 運(yùn)輸公司安全生產(chǎn)管理制度
評(píng)論
0/150
提交評(píng)論