集訓(xùn)隊(duì)作業(yè)解題報(bào)告tournament

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