歷年題目訓(xùn)練problemset

1、ljs_yali2017 年 9 月 5 日時(shí)間：3.5 小時(shí)提交程序文件名編譯選項(xiàng)對(duì)于 C+ 語(yǔ)言-lm,-O2-lm,-O2-lm,-O2對(duì)于 C 語(yǔ)言-lm,-O2-lm,-O2-lm,-O2對(duì)于 Pascal 語(yǔ)言-lm,-O2-lm,-O2-lm,-O2對(duì)于 C+ 語(yǔ)言problem.cpptracks.cppballmachine.cpp對(duì)于 C 語(yǔ)言problem.ctracks.cballmachine.c對(duì)于 Pascal 語(yǔ)言problem.pastracks.pasballmachine.pas題目名稱(chēng)序列問(wèn)題雪地行蹤發(fā)球機(jī)器題目類(lèi)型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄problemt

2、racksballmachine輸入文件名problem.racks.inballmachine.in輸出文件名problem.outtracks.outballmachine.out每個(gè)測(cè)試點(diǎn)時(shí)限1.0s2.0s1.0s內(nèi)存限制512MB512MB128MB測(cè)試點(diǎn)數(shù)目102025每個(gè)測(cè)試點(diǎn)分值1054序列問(wèn)題(problem.cpp/c/pas)【問(wèn)題描述】Brunhilda 十分喜歡序列, 她喜歡觀察序列的性質(zhì)?，F(xiàn)在 Brunhilda 手上有 n 個(gè)不同的數(shù), 于是她嘗試將這 n 個(gè)數(shù)字填到長(zhǎng)為 n 的序列 A 中。在她看來(lái)當(dāng)序列 A 的第 i 位上數(shù)字在原來(lái) n 個(gè)數(shù)中恰好是第 i 大

3、時(shí),i 號(hào)位置就是穩(wěn)定的。并且, 當(dāng)序列中恰好有 m 個(gè)位置是穩(wěn)定時(shí), 她的開(kāi)心度就會(huì)加 1。那么, 她想知道, 她的開(kāi)心度最大可能是多少。由于 Brunhilda 的開(kāi)心度可能會(huì)很大，所以你只要輸出開(kāi)心度除以 1000000007 的余數(shù)?！据斎敫袷健繌奈募?problem.in 中讀入數(shù)據(jù)。輸入文件第一行包括一個(gè)整數(shù) T , 表示數(shù)據(jù)組數(shù)。接下來(lái) T 行, 每行兩個(gè)整數(shù), 表示 N 和 M ?！据敵龈袷健枯敵龅轿募?problem.out 中。輸出文件包括 T 行, 每行一個(gè)整數(shù), 表示 Brunhilda 最大的開(kāi)心度?！緲永斎搿?1 02 15 2100 5010000 5000【樣

4、例輸出】0第 2 頁(yè), 共 10 頁(yè)02057802888760695423【提示】 1 mod p, 其中 p 為質(zhì)數(shù),x 1, p)。xp1【子任務(wù)】對(duì)于 100% 的數(shù)據(jù)滿足1 N 106, 0 M N 106。每個(gè)測(cè)試點(diǎn)還滿足如下約束：第 3 頁(yè), 共 10 頁(yè)測(cè)試點(diǎn)編號(hào)NMT1 5 5= 12 8 8= 5 1053 10 10= 14 2000= 0= 5 1055 106= 16 3000 3000= 5 1057= 18 106 106= 5 1059= 110= 5 105雪地行蹤(tracks.cpp/c/pas)【問(wèn)題描述】森林里有一塊矩形的草地, 大雪剛至, 草地如蓋上

5、了潔白的毛毯一般。四處望去一片渺茫, 沒(méi)有植物, 沒(méi)有生機(jī)。住在森林里的若干只小兔 (R) 和狐貍 (F) 正在經(jīng)過(guò)這片草地, 當(dāng)然, 草地上也留下了它們的足跡。“這個(gè)是小兔的。” “那些是狐貍們的吧！”兔子和狐貍總是從草地的左上角進(jìn)入, 并從右下角離開(kāi)。在草地中時(shí), 它們可能會(huì)來(lái)回的走動(dòng)甚至經(jīng)過(guò)自己的足跡。任何時(shí)候, 草地上最多只能有 1 只動(dòng)物, 每只動(dòng)物只會(huì)經(jīng)過(guò)草地一次。每只動(dòng)物的行蹤可以通過(guò)將矩形草地分成若干小格來(lái)進(jìn)行描述。小動(dòng)物們不會(huì)斜著走或跳過(guò)一小格來(lái)到下一格。當(dāng)一個(gè)小動(dòng)物經(jīng)過(guò)草地時(shí), 它會(huì)把在它之前的所有足跡全部覆蓋。例如, 一開(kāi)始一只小兔從左上角穿過(guò)草地到達(dá)右下角（如中圖）。在

6、這之后, 一只狐貍也來(lái)到了草地, 并且將小兔的一部分足跡覆蓋了（如右圖）。.RRR.RRR.R.RRRR.R.RRRFFR.FRRR.FF.RRRFFR.一段時(shí)間后, 你擁有了這個(gè)草地的地圖, 地圖上顯示著每一格是否有足跡并且那些足跡分別是由小兔還是狐貍留下的。你對(duì)當(dāng)?shù)氐囊吧鷦?dòng)物數(shù)量十分感興趣。現(xiàn)在, 請(qǐng)你寫(xiě)一個(gè)程序嘗試得出最少需要 N 只動(dòng)物穿過(guò)草地才可以在雪地中留下這樣的行蹤。第 4 頁(yè), 共 10 頁(yè)【輸入格式】從文件 tracks.in 中讀入數(shù)據(jù)。輸入文件的第一行包含兩個(gè)整數(shù) H 和 W , 分別表示草地地圖的長(zhǎng)和寬。接下來(lái) H 行每行 W 個(gè)字符描述這個(gè)地圖：.表示沒(méi)有被留下印記的

7、空白雪地,R表示一格中小兔的足跡留在了最上面,F表示狐貍的足跡留在了最上面。地圖中至少有一個(gè)足跡。【輸出格式】輸出到文件 tracks.out 中。輸出包含一個(gè)整數(shù), 表示可以滿足輸入中行蹤的最少的動(dòng)物數(shù) N 1。【樣例輸入】 5 8 FFR.FRRR.FF.RRRFFR.【樣例輸出】2【子任務(wù)】對(duì)于 100% 的數(shù)據(jù),1 H, W 4000。每個(gè)測(cè)試點(diǎn)還滿足如下約束：第 5 頁(yè), 共 10 頁(yè)第頁(yè), 共 10 頁(yè)測(cè)試點(diǎn)編號(hào)HW特殊性質(zhì)1 10 10地圖全為 R 或 F2N 23N 34 4000 40005 20 20N 567 500 500N 2008910 4000 4000N 101

8、1 10 4000N 300012 4000 15N 600013 4000 4000N 30014無(wú)15發(fā)球機(jī)器(ballmachine.cpp/c/pas)【問(wèn)題描述】有一個(gè)可看成有根樹(shù)的發(fā)球機(jī)器, 樹(shù)上的節(jié)點(diǎn)被編號(hào)成 1 N , 每個(gè)節(jié)點(diǎn)為空或包含一個(gè)球。初始時(shí), 所有的節(jié)點(diǎn)都是空的。當(dāng)機(jī)器運(yùn)行時(shí), 它可以支持如下的兩種操作：1. 向發(fā)球機(jī)器中添加 k 個(gè)球：球被一個(gè)一個(gè)分別放在了根節(jié)點(diǎn)。只要有一個(gè)空節(jié)點(diǎn)在球的下方, 它就會(huì)滾下去。如果一個(gè)點(diǎn)有多個(gè)空的子節(jié)點(diǎn), 機(jī)器會(huì)選擇將球向其子樹(shù)中最小節(jié)點(diǎn)最小的節(jié)點(diǎn)滾下去。因此, 如果一個(gè)球會(huì)掉下多層, 那么機(jī)器會(huì)在每一層都作出決定。例如：如果我們向

9、下圖的根節(jié)點(diǎn)放置兩個(gè)球, 它們會(huì)停在 1 和 3 號(hào)節(jié)點(diǎn)：第一個(gè)球會(huì)從 4 號(hào)點(diǎn)滾向 3 號(hào)點(diǎn)因?yàn)?3 號(hào)點(diǎn)是空的并且它擁有 1 號(hào)點(diǎn)在其子樹(shù)中；然后它會(huì)滾向 1 號(hào)節(jié)點(diǎn)。第二個(gè)球從 4 號(hào)點(diǎn)滾向 3 號(hào)點(diǎn)然后停在那里。2. 從一個(gè)特定的節(jié)點(diǎn)移除一個(gè)球：這個(gè)節(jié)點(diǎn)將會(huì)變空, 并且它上面的所有節(jié)點(diǎn)上的球都會(huì)順次掉下來(lái) (如果有的話)。如果我們?nèi)缦聢D依次從發(fā)球機(jī)器中移除 5,7 和 8 號(hào)節(jié)點(diǎn)的球,1,2 和 3 號(hào)節(jié)點(diǎn)將會(huì)變空。第 7 頁(yè), 共 10 頁(yè)【輸入格式】從文件 ballmachine.in 中讀入數(shù)據(jù)。輸入的第一行包含兩個(gè)整數(shù) N 和 Q, 分別表示這棵樹(shù)的節(jié)點(diǎn)個(gè)數(shù)和操作的總個(gè)數(shù)。接下

10、來(lái)的 N 行描述這個(gè)發(fā)球機(jī)器。每一行包含一個(gè)描述該節(jié)點(diǎn)的整數(shù)：第 i 行是 i 號(hào)節(jié)點(diǎn)的父親節(jié)點(diǎn), 如果 i 號(hào)節(jié)點(diǎn)是根節(jié)點(diǎn), 則該數(shù)會(huì)是 0。接下來(lái)的 Q 行每行包含兩個(gè)整數(shù)描述一次操作。其中 1 k 表示 1 號(hào)操作,k 表示需要將 k 個(gè)球放入發(fā)球機(jī)器。2 x 表示 2 號(hào)操作,x 表示被移除的球所在的節(jié)點(diǎn)編號(hào)。數(shù)據(jù)保證所有的操作都是合法的, 即：操作不會(huì)要求加入多于當(dāng)前空節(jié)點(diǎn)數(shù)的球, 也不會(huì)從一個(gè)空節(jié)點(diǎn)移除一個(gè)球?！据敵龈袷健枯敵龅轿募?ballmachine.out 中。對(duì)于操作 1, 輸出一個(gè)整數(shù)表示最后一個(gè)加入發(fā)球機(jī)器的球停在了哪里。對(duì)于操作 2, 輸出一個(gè)整數(shù)表示在移除當(dāng)前節(jié)點(diǎn)的球后會(huì)有多少個(gè)球掉落?！緲永斎?1】2 5011 22 11 12 21 1【樣例輸出 1】10111第 8 頁(yè), 共 10 頁(yè)【樣例輸入 2】8 401223346【樣例輸出】22【子任務(wù)】對(duì)于 100% 的數(shù)據(jù),1 N, Q 105。每個(gè)測(cè)試點(diǎn)還滿足如下約束：第 9 頁(yè), 共 10 頁(yè)第 10 頁(yè), 共 10 頁(yè)測(cè)試點(diǎn)編號(hào)NQ特殊性質(zhì)1 2 2無(wú)2 300 300345= 1023= 500每