資源描述:
《安徽省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