今天做的還可以,當(dāng)然,對(duì)我來(lái)說(shuō)。唯一的缺點(diǎn)是別人當(dāng)水題做的D我沒(méi)做出來(lái)。簡(jiǎn)單的BFS,我愣是不會(huì)。哎,還是要把基礎(chǔ)打好啊。最后A掉3道,還有一道線段樹(shù)的沒(méi)有過(guò),過(guò)些時(shí)間補(bǔ)上。我該抓緊時(shí)間復(fù)習(xí)了...
A - River Pollution
線段樹(shù),求面積的并,很基礎(chǔ)的線段樹(shù)+離散化+掃描線,但我就是不會(huì)~
B - Middle number
今天這個(gè)是第一個(gè)過(guò)的,如果這個(gè)不過(guò)我相信后邊會(huì)更加艱難。給定一個(gè)數(shù)的序列,然后不斷的插入數(shù)字并保持遞增,最后詢問(wèn)中間的數(shù)是多少。如果
數(shù)的個(gè)數(shù)是偶數(shù),輸出中間兩個(gè)中小的。數(shù)據(jù)很大,時(shí)間是5s,我冒了個(gè)險(xiǎn),第一次先排序,每次二分找到要插入的位置,然后順序修改后邊的序列,過(guò)了!
二分的效率啊!!我看到后邊這個(gè)題無(wú)數(shù)人TLE到死。。。這個(gè)題給了我很大信心,不然。。。
現(xiàn)在知道了,正解是用兩個(gè)堆,一個(gè)大頂堆,一個(gè)小頂堆,大頂堆只能和小頂堆元素個(gè)數(shù)相同或者正好多一個(gè)。開(kāi)始時(shí)將小的一般給大頂堆,大的一半給小頂堆,插入時(shí)和堆頂元素比一下,若大于大頂堆的堆頂元素,則插給小堆,否則給了大堆。詢問(wèn)時(shí)只需輸出大堆的堆頂元素就可以了。
C - Game of Stones
JL出的題,乍一看很難,但是后來(lái)才知道簡(jiǎn)單的要命:兩個(gè)人A和B玩游戲,有兩堆石子M和N,每次兩個(gè)人都至少?gòu)膬啥阎腥我庖欢涯弥辽僖粋€(gè)石子,直到兩堆石子都為空最后一個(gè)拿的人WIN。,A總是第一個(gè)拿,給定M和N,問(wèn)A能否獲勝。( 0 < M , N < 10^50 )
答案:如果M==N,A輸,否則,A贏。我考慮到奇偶上了,結(jié)果WA了5次,哎。。。
D - The longest athletic track
給定N個(gè)點(diǎn),和一棵生成樹(shù)(N-1條邊),最后問(wèn)最長(zhǎng)的一條路是多少。
上圖的答案是80。
求樹(shù)的直徑,兩次BFS,第一次任選起點(diǎn),則終點(diǎn)一定是直徑的一個(gè)端點(diǎn)。然后再來(lái)一次BFS就可以了。
E - Buy Car
Brent喜歡騎摩托,現(xiàn)在有N個(gè)城市,Brent 想把所有城市逛一遍,但是他怕油不夠。每升油可以跑10km,他可以在任何一個(gè)城市加油。給出M條邊,
最后問(wèn)Brent的摩托的容量最小是多少,如果不能逛完所有城市,輸出-1。
簡(jiǎn)單的最小生成樹(shù)(正是Brent講座講的~),找出最小生成樹(shù)最小的一條邊長(zhǎng)度為A。如果A%10==0,答案是A/10;否則答案是A/10+1;
最后排名大概是10名?(除去老隊(duì)員和admin大概是7,8名的樣子),問(wèn)題應(yīng)該不大了。嘻嘻,加油吧~ 可惡的BFS。。。一定搞定它。