安徽省2009年省選題day1

ID:12521135

大小:36.00 KB

頁(yè)數(shù):5頁(yè)

時(shí)間:2018-07-17

安徽省2009年省選題day1_第1頁(yè)
安徽省2009年省選題day1_第2頁(yè)
安徽省2009年省選題day1_第3頁(yè)
安徽省2009年省選題day1_第4頁(yè)
安徽省2009年省選題day1_第5頁(yè)
資源描述:

《安徽省2009年省選題day1》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)

1、1.行星序列(seq)“神州“載人飛船的發(fā)射成功讓小可可非常激動(dòng),他立志長(zhǎng)大后要成為一名宇航員假期一始,他就報(bào)名參加了“小小宇航員夏令營(yíng)”,在這里小可可不僅學(xué)到了豐富的宇航知識(shí),還參與解決了一些模擬飛行中發(fā)現(xiàn)的問(wèn)題,今天指導(dǎo)老師交給他一個(gè)任務(wù),在這次模擬飛行的路線上有N個(gè)行星,暫且稱(chēng)它們?yōu)橐粋€(gè)行星序列,并將他們從1至n標(biāo)號(hào),在宇宙未知力量的作用下這N個(gè)行星的質(zhì)量是不斷變化的,所以他們對(duì)飛船產(chǎn)生的引力也會(huì)不斷變化,小可可的任務(wù)就是在飛行途中計(jì)算這個(gè)行星序列中某段行星的質(zhì)量和,以便能及時(shí)修正飛船的飛行線路,最終到達(dá)目的地,行

2、星序列質(zhì)量變化有兩種形式:1,行星序列中某一段行星的質(zhì)量全部乘以一個(gè)值2,行星序列中某一段行星的質(zhì)量全部加上一個(gè)值由于行星的質(zhì)量和很大,所以求出某段行星的質(zhì)量和后只要輸出這個(gè)值模P的結(jié)果即可,小可可被這個(gè)任務(wù)難住了,聰明的你能夠幫他完成這個(gè)任務(wù)嗎?輸入:第一行兩個(gè)整數(shù)N和P(1<=p<=1000000000);第二行含有N個(gè)非負(fù)整數(shù),從左到右依次為a1,a2,…………,an(0<=ai<。100000000,1<=i<=n),其中ai表示第i個(gè)行星的質(zhì)量:第三行有一個(gè)整數(shù)m,表示模擬行星質(zhì)量變化以及求質(zhì)量和等操作的總次數(shù)

3、。從第四行開(kāi)始每行描述一個(gè)操作,輸入的操作有以下三種形式:操作1:1tgc表示把所有滿(mǎn)足t<=i<=g的行星質(zhì)量ai改為ai*c操作2:2tgc表示把所有滿(mǎn)足t<=i<=g的行星質(zhì)量ai改為ai+c操作3:3tg表示輸出所有滿(mǎn)足t<=i<=g的ai的和模p的值其中:1<=t<=g<=N,0<=c<=10000000注:同一行相鄰的兩數(shù)之間用一個(gè)空格隔開(kāi),每行開(kāi)頭和末尾沒(méi)有多余空格輸出:對(duì)每個(gè)操作3,按照它在輸入中出現(xiàn)的順序,依次一行輸出一個(gè)整數(shù)表示所求行星質(zhì)量和樣例:輸入:743123456751255324237931

4、3347輸出:2358樣例說(shuō)明:略提示:100%的數(shù)據(jù)中,M,N<=10000040%的數(shù)據(jù)中,M,N<=10000(Neilc-lc提醒你,直接模擬可能是一個(gè)點(diǎn)都過(guò)不去,加上每次mod的優(yōu)化,可以過(guò)3到4個(gè)點(diǎn)……正解是用線段樹(shù)來(lái)做)Timelimit:3000ms2.同類(lèi)分布(self)在模擬飛行的過(guò)程中,小可可發(fā)現(xiàn)在一個(gè)未知星球周?chē)植贾S多同類(lèi)的小行星帶,而這些小行星帶的分布非常有規(guī)律,經(jīng)過(guò)研究發(fā)現(xiàn)實(shí)些小行星帶到未知星球的距離為x(x為非負(fù)整數(shù))與如下的函數(shù)有一定的關(guān)系:dsum(x)=0(x=0)dsum(x)=

5、dsum【xdiv10】+xmod10(x<>0)即x可以被dsum(x)整除。小可可非常希望能研究出距離這個(gè)未知星球的某一區(qū)域內(nèi)小行星帶的分布規(guī)律,具體來(lái)說(shuō),就是在與未知行星距離a和b的范圍內(nèi)分布了多少個(gè)小行星帶,你能幫助他解決這個(gè)問(wèn)題嗎?輸入:輸入文件僅一行,包含兩個(gè)正整數(shù)a和b(a<=b).輸出:輸出文件中僅包含一個(gè)整數(shù),表示[a,b]內(nèi)分布多少個(gè)小行星帶。樣例1:輸入:110輸出:10樣例2:輸入:12345679123456791234567912346789輸出:37提示:100%的數(shù)據(jù)中,a,b不超過(guò)100

6、000000000000000(10的18次方);30%的數(shù)據(jù)中,b-a不超過(guò)1000000Timelimit:5000ms3.最小截?cái)嘤钪媛眯锌偸浅霈F(xiàn)一些意想不到的問(wèn)題,這次小可可所駕駛的宇宙飛船所停的空間站發(fā)生了故障,這個(gè)宇宙空間站非常大,它由N個(gè)子站組成,子站之間有M條單向通道,假設(shè)其中第i(1<=i<=M)條單向通道連接了xi,yi兩個(gè)中轉(zhuǎn)站,那么xi子站可以通過(guò)這個(gè)通道到達(dá)yi子站,如果截?cái)噙@條通道,需要代價(jià)ci?,F(xiàn)在為了將故障的代價(jià)控制到最小,小可可必須想出一個(gè)截?cái)喾桨?,使a站不能到達(dá)b子站,并且截?cái)嗟拇鷥r(jià)之

7、和最小。我們稱(chēng)之為最小截?cái)?,小可可很快解決了這個(gè)故障,但是愛(ài)思考的小可可并不局限于此,為了今后更方便的解決同類(lèi)故障,他考慮對(duì)每條單向通道:1,是否存在一個(gè)最小代價(jià)路徑截?cái)喾桨?,其中該通道被切斷?,是否對(duì)任何一個(gè)最小代價(jià)路徑切斷方案,都有該通道被切斷?聰明的你能幫小可可解決他的疑問(wèn)嗎?輸入:第一行有4個(gè)整數(shù),依次為N,M,a和b;第二行到第(m+1)行每行3個(gè)正整數(shù)x,y,c表示x子站到y(tǒng)子站之間有單向通道相連,單向通道的起點(diǎn)是x終點(diǎn)是y,切斷它的代價(jià)是c(1<=c<=10000);兩個(gè)子站之間可能有多條通道直接連接。輸

8、出:對(duì)每一個(gè)單向通道,按輸入的順序,依次輸出一行包含兩個(gè)非0即1的整數(shù),分別表示對(duì)問(wèn)題一和問(wèn)題二的回答(其中1表示是,0表示否)。每行兩個(gè)整數(shù)之間用一個(gè)空格分隔開(kāi)。樣例:輸入:6716123132244251355462563輸出:10100010001010提示:100%的數(shù)據(jù)中,N<=4000,M<=600007

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶(hù)上傳,版權(quán)歸屬用戶(hù),天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶(hù)請(qǐng)聯(lián)系客服處理。
关闭