亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

NOIP2007解題報(bào)告

系統(tǒng) 1587 0

?第一題: ?某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù),每個(gè)數(shù)均不超過1500000000(1.5*109)。已知不相同的數(shù)不超過10000個(gè),現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù),并按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果。

?

解題過程: 直接sort快拍然后掃描一遍即可。


第二題: ?在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問題中,我們?cè)o出一個(gè)字符串展開的例子:如果在輸入的字符串中,含有類似于“d-h”或“4-8”的子串,我們就把它當(dāng)作一種簡寫,輸出時(shí),用連續(xù)遞增的字母或數(shù)字串替代其中的減號(hào),即,將上面兩個(gè)子串分別輸出為“defgh”和“45678”。在本題中,我們通過增加一些參數(shù)的設(shè)置,使字符串的展開更為靈活。具體約定如下: (1)遇到下面的情況需要做字符串的展開:在輸入的字符串中,出現(xiàn)了減號(hào)“-”,減號(hào)兩側(cè)同為小寫字母或同為數(shù)字,且按照ASCII碼的順序,減號(hào)右邊的字符嚴(yán)格大于左邊的字符。 (2)參數(shù)p1:展開方式。p1=1時(shí),對(duì)于字母子串,填充小寫字母;p1=2時(shí),對(duì)于字母子串,填充大寫字母。這兩種情況下數(shù)字子串的填充方式相同。p1=3時(shí),不論是字母子串還是數(shù)字子串,都用與要填充的字母個(gè)數(shù)相同的星號(hào)“*”來填充。 (3)參數(shù)p2:填充字符的重復(fù)個(gè)數(shù)。p2=k表示同一個(gè)字符要連續(xù)填充k個(gè)。例如,當(dāng)p2=3時(shí),子串“d-h”應(yīng)擴(kuò)展為“deeefffgggh”。減號(hào)兩側(cè)的字符不變。 (4)參數(shù)p3:是否改為逆序:p3=1表示維持原有順序,p3=2表示采用逆序輸出,注意這時(shí)仍然不包括減號(hào)兩端的字符。例如當(dāng)p1=1、p2=2、p3=2時(shí),子串“d-h”應(yīng)擴(kuò)展為“dggffeeh”。 (5)如果減號(hào)右邊的字符恰好是左邊字符的后繼,只刪除中間的減號(hào),例如:“d-e”應(yīng)輸出為“de”,“3-4”應(yīng)輸出為“34”。如果減號(hào)右邊的字符按照ASCII碼的順序小于或等于左邊字符,輸出時(shí),要保留中間的減號(hào),例如:“d-d”應(yīng)輸出為“d-d”,“3-1”應(yīng)輸出為“3-1”。

?

解題過程: 按題目描述模擬就好,只要細(xì)心就不會(huì)錯(cuò)。?

?

第三題: 帥帥經(jīng)常跟同學(xué)玩一個(gè)矩陣取數(shù)游戲:對(duì)于一個(gè)給定的n*m的矩陣,矩陣中的每個(gè)元素aij均為非負(fù)整數(shù)。游戲規(guī)則如下: 1. 每次取數(shù)時(shí)須從每行各取走一個(gè)元素,共n個(gè)。m次后取完矩陣所有元素; 2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾; 3. 每次取數(shù)都有一個(gè)得分值,為每行取數(shù)的得分之和,每行取數(shù)的得分 = 被取走的元素值*2^i,其中i表示第i次取數(shù)(從1開始編號(hào)); 4. 游戲結(jié)束總得分為m次取數(shù)得分之和。 帥帥想請(qǐng)你幫忙寫一個(gè)程序,對(duì)于任意矩陣,可以求出取數(shù)后的最大得分。


解題過程: 這題比較有意思,?一開始會(huì)想到貪心,有經(jīng)驗(yàn)的話看數(shù)據(jù)范圍,肯定是動(dòng)態(tài)規(guī)劃拉。首先取數(shù)各行之間沒有關(guān)聯(lián),也就是每行都是要么取頭要么取尾,分開做n次就好了。 F[i][j]表示從第i列到第j列的最大得分,F[i][j]=max{F[i][j-1]*2+2*a[j],F[i+1][j]*2+2*a[i]} 用long?long?可以過7個(gè)點(diǎn),高精度會(huì)有點(diǎn)慢,勉強(qiáng)AC。注意答案可能會(huì)有0,高精度可能會(huì)漏掉輸出。


第四題:

設(shè) T=(V, E, W) 是一個(gè)無圈且連通的無向圖(也稱為無根樹),每條邊帶有正整數(shù)的權(quán),我們稱T為樹網(wǎng)(treenetwork),其中V, E分別表示結(jié)點(diǎn)與邊的集合,W表示各邊長度的集合,并設(shè)T有n個(gè)結(jié)點(diǎn)。

路徑 :樹網(wǎng)中任何兩結(jié)點(diǎn)a,b都存在唯一的一條簡單路徑,用d(a,b)表示以a,b為端點(diǎn)的路徑的長度,它是該路徑上各邊長度之和。我們稱d(a,b)為a,b兩結(jié)點(diǎn)間的距離。 一點(diǎn)v到一條路徑P的距離為該點(diǎn)與P上的最近的結(jié)點(diǎn)的距離:

d(v, P)=min{d(v, u) u 為路徑 P 上的結(jié)點(diǎn)}。

樹網(wǎng)的直徑 :樹網(wǎng)中最長的路徑稱為樹網(wǎng)的直徑。對(duì)于給定的樹網(wǎng)T,直徑不一定是唯一的,但可以證明:各直徑的中點(diǎn)(不一定恰好是某個(gè)結(jié)點(diǎn),可能在某條邊的內(nèi)部)是唯一的,我們稱該點(diǎn)為樹網(wǎng)的中心。

偏心距 ECC(F):樹網(wǎng)T中距路徑F最遠(yuǎn)的結(jié)點(diǎn)到路徑F的距離,即

ECC(F)=max{d(v,F),v∈V}

任務(wù) :對(duì)于給定的樹網(wǎng) T=(V, E,W) 和非負(fù)整數(shù)s,求一個(gè)路徑F,它是某直徑上的一段路徑(該路徑兩端均為樹網(wǎng)中的結(jié)點(diǎn)),其長度不超過s(可以等于s),使偏心距ECC(F)最小。我們稱這個(gè)路徑為樹網(wǎng)T=(V,E,W)的 (Core)。必要時(shí),F(xiàn)可以退化為某個(gè)結(jié)點(diǎn)。一般來說,在上述定義下,核不一定只有一個(gè),但最小偏心距是唯一的。

下面的圖給出了樹網(wǎng)的一個(gè)實(shí)例。圖中,A-B與A-C是兩條直徑,長度均為20。點(diǎn)W是樹網(wǎng)的中心,EF邊的長度為5。如果指定s=11,則樹網(wǎng)的核為路徑DEFG(也可以取為路徑DEF),偏心距為8。如果指定s=0(或s=1、s=2),則樹網(wǎng)的核為結(jié)點(diǎn)F,偏心距為12。

解題過程: 這題題目看了n久才看明白,實(shí)在坑爹,先是想不明白題目中說的?“各直徑的中點(diǎn)(不一定恰好是某個(gè)結(jié)點(diǎn),可能在某條邊的內(nèi)部)是唯一的”,而且我還找到了反例。還好這個(gè)東西是廢話用不著的。 直徑有很多,但實(shí)際上只要在一條直徑上找就好了(證明不來。。。但自己畫有多條直徑的圖的時(shí)候,畫出來的都是對(duì)稱的。。)。。 因此找到一條直徑,把路徑記錄下來,然后 用兩個(gè)指針i,j分別表示起點(diǎn)和終點(diǎn),i指針每次往前移動(dòng)一個(gè),然后j指針盡可能往后移動(dòng), 因?yàn)榇_定起點(diǎn)的路徑肯定是越長越好,粗略的證明見注釋,然后對(duì)路徑中的每一個(gè)點(diǎn)為起點(diǎn)做一次DFS(先把路徑中的點(diǎn)標(biāo)記為已經(jīng)訪問過),就可以求出偏心距。關(guān)鍵是找到直徑,做法是 隨便取一個(gè)點(diǎn)做DFS,找到與它相距最遠(yuǎn)的一個(gè)點(diǎn),那么這個(gè)點(diǎn)必定是某條直徑的一個(gè)端點(diǎn)。然后在以這個(gè)點(diǎn)為起點(diǎn)做DFS找到最遠(yuǎn)的點(diǎn),就是直徑的另外一端了。然后在做一次DFS把整條直徑給找出來。?證明用反證法。

注釋:對(duì)于 ?確定起點(diǎn)的路徑肯定是越長越好的證明:假設(shè)目前枚舉的路徑為S,要再添加一個(gè)點(diǎn)X進(jìn)來,讓路徑更長一點(diǎn),變成路徑T。樹網(wǎng)中到直徑的入口為X的點(diǎn)Y,(即Y到路徑的最短距離為Dist(X,Y))。Dist(X,Y)一定不會(huì)大于原路徑S的偏心距,否則S偏心距的路徑可以由Y出發(fā)經(jīng)過X到路徑S上來,就大于Dist(X,Y)了,出現(xiàn)矛盾。
2014-07-28 22:16:01

NOIP2007解題報(bào)告


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 亚洲精品国产精品一区二区 | 精品夜夜春夜夜爽久久 | 精品久久久久久 | 96精品专区国产在线观看高清 | 色综合久久久久久久久久久 | 日韩中文字幕免费 | 波多野结衣免费播放 | 国产一区二区在线观看视频 | 亚洲天堂爱爱 | 成人99国产精品 | 免费在线一级毛片 | 久9热精品视频在线观看 | 天天躁夜夜躁很很躁麻豆 | 国内精品久久久久久久亚洲 | 怡红院成人永久免费看 | 亚州免费一级毛片 | 国产视频精品视频 | 亚洲伊人久久综合影院2021 | 成 人 a v免费视频 | www.国产一区二区三区 | 四虎综合网| 波多野结衣久久高清免费 | 久久99精品国产麻豆不卡 | 精品福利一区二区三区免费视频 | 伊人久久综在合线亚洲91 | 全高清特级毛片 | 99久久免费国产精精品 | 婷婷在线视频 | 天天草夜夜操 | 九九99香蕉在线视频美国毛片 | 欧美不卡在线观看 | 亚洲欧美一区二区三区国产精品 | 亚洲精品国产成人中文 | 久久久噜噜噜久久老司机 | 日韩午夜在线视频不卡片 | 奇米777视频 | 天堂成人在线 | 色女人久久 | 国产精品久久久久久久久久98 | 天天插天天操 | 国产亚洲欧美日韩综合综合二区 |