noip2011提高組day2

《noip2011提高組day2》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、全國信息學(xué)奧林匹克聯(lián)賽（NOIP2011）復(fù)賽提高組day2全國信息學(xué)奧林匹克聯(lián)賽（NOIP2011）復(fù)賽提高組day2（請選手務(wù)必仔細閱讀本頁內(nèi)容）一．題目概況中文題目名稱計算系數(shù)聰明的質(zhì)監(jiān)員觀光公交英文題目與子目錄名factorqcbus可執(zhí)行文件名factorqcbus輸入文件名factor.inqc.inbus.in輸出文件名factor.outqc.outbus.out每個測試點時限1秒1秒1秒測試點數(shù)目102020每個測試點分值1055附加樣例文件有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)二．提交源程序

2、文件名對于C++語言factor.cppqc.cppbus.cpp對于C語言factor.cqc.cbus.c對于pascal語言factor.pasqc.Pasbus.pas三．編譯命令（不包含任何優(yōu)化開關(guān)）對于C++語言g++-ofactorg++-oqcqc.cppg++-obusbus.cppfactor.cpp-lm–lm-lm對于C語言gcc-ofactorfactor.cgcc-oqcqc.c–lmgcc-obusbus.c-lm-lm對于pascal語言fpcfactor.pasfpcqc.pasfpcbus.pas四．運行內(nèi)存

3、限制內(nèi)存上限128M128M128M注意事項：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C++中函數(shù)main()的返回值類型必須是int，程序正常結(jié)束時的返回值必須是0。3、全國統(tǒng)一評測時采用的機器配置為：CPUP43.0GHz，內(nèi)存1G，上述時限以此配置為準(zhǔn)。4、特別提醒：評測在NOILinux下進行。第1頁共4頁全國信息學(xué)奧林匹克聯(lián)賽（NOIP2011）復(fù)賽提高組day21．計算系數(shù)(factor.cpp/c/pas)【問題描述】knm給定一個多項式(ax+by)，請求出多項式展開后xy項的系數(shù)?！据斎搿枯斎胛募麨閒a

4、ctor.in。共一行，包含5個整數(shù)，分別為a，b，k，n，m，每兩個整數(shù)之間用一個空格隔開?！据敵觥枯敵鑫募麨閒actor.out。輸出共1行，包含一個整數(shù)，表示所求的系數(shù)，這個系數(shù)可能很大，輸出對10007取模后的結(jié)果?！据斎胼敵鰳永縡actor.infactor.out113123【數(shù)據(jù)范圍】對于30%的數(shù)據(jù)，有0≤k≤10；對于50%的數(shù)據(jù)，有a=1，b=1；對于100%的數(shù)據(jù)，有0≤k≤1,000，0≤n,m≤k，且n+m=k，0≤a，b≤1,000,000。2．聰明的質(zhì)監(jiān)員(qc.cpp/c/pas)【問題描述】小T是一名質(zhì)量監(jiān)

5、督員，最近負(fù)責(zé)檢驗一批礦產(chǎn)的質(zhì)量。這批礦產(chǎn)共有n個礦石，從1到n逐一編號，每個礦石都有自己的重量wi以及價值vi。檢驗礦產(chǎn)的流程是：1、給定m個區(qū)間[Li，Ri]；2、選出一個參數(shù)W；3、對于一個區(qū)間[Li，Ri]，計算礦石在這個區(qū)間上的檢驗值Yi：Yi=∑1*∑vj，j∈[Li,Ri]且wj≥W，j是礦石編號jjm這批礦產(chǎn)的檢驗結(jié)果Y為各個區(qū)間的檢驗值之和。即：Y=∑Yii=1若這批礦產(chǎn)的檢驗結(jié)果與所給標(biāo)準(zhǔn)值S相差太多，就需要再去檢驗另一批礦產(chǎn)。小T不想費時間去檢驗另一批礦產(chǎn)，所以他想通過調(diào)整參數(shù)W的值，讓檢驗結(jié)果盡可能的靠近標(biāo)準(zhǔn)值S，即使得

6、S-Y的絕對值最小。請你幫忙求出這個最小值?！据斎搿枯斎胛募c.in。第2頁共4頁全國信息學(xué)奧林匹克聯(lián)賽（NOIP2011）復(fù)賽提高組day2第一行包含三個整數(shù)n，m，S，分別表示礦石的個數(shù)、區(qū)間的個數(shù)和標(biāo)準(zhǔn)值。接下來的n行，每行2個整數(shù)，中間用空格隔開，第i+1行表示i號礦石的重量wi和價值vi。接下來的m行，表示區(qū)間，每行2個整數(shù)，中間用空格隔開，第i+n+1行表示區(qū)間[Li,Ri]的兩個端點Li和Ri。注意：不同區(qū)間可能重合或相互重疊。【輸出】輸出文件名為qc.out。輸出只有一行，包含一個整數(shù)，表示所求的最小值?！据斎胼敵鰳永縬c.

7、inqc.out5315101525354555152433【輸入輸出樣例說明】當(dāng)W選4的時候，三個區(qū)間上檢驗值分別為20、5、0，這批礦產(chǎn)的檢驗結(jié)果為25，此時與標(biāo)準(zhǔn)值S相差最小為10?！緮?shù)據(jù)范圍】對于10%的數(shù)據(jù)，有1≤n，m≤10；對于30%的數(shù)據(jù)，有1≤n，m≤500；對于50%的數(shù)據(jù)，有1≤n，m≤5,000；對于70%的數(shù)據(jù)，有1≤n，m≤10,000；612對于100%的數(shù)據(jù)，有1≤n，m≤200,000，0

8、市，擁有n個美麗的景點。由于慕名而來的游客越來越多，Y市特意安排了一輛觀光公交車，為游客提供更便捷的交通服務(wù)。觀光公交車在第0分鐘出現(xiàn)在1號景點，隨后