歷年題目訓練problemset

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

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

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

4、例輸出】0第 2 頁, 共 10 頁02057802888760695423【提示】 1 mod p, 其中 p 為質(zhì)數(shù),x 1, p)。xp1【子任務】對于 100% 的數(shù)據(jù)滿足1 N 106, 0 M N 106。每個測試點還滿足如下約束：第 3 頁, 共 10 頁測試點編號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)【問題描述】森林里有一塊矩形的草地, 大雪剛至, 草地如蓋上

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

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

7、空白雪地,R表示一格中小兔的足跡留在了最上面,F表示狐貍的足跡留在了最上面。地圖中至少有一個足跡?！据敵龈袷健枯敵龅轿募?tracks.out 中。輸出包含一個整數(shù), 表示可以滿足輸入中行蹤的最少的動物數(shù) N 1?！緲永斎搿?5 8 FFR.FRRR.FF.RRRFFR.【樣例輸出】2【子任務】對于 100% 的數(shù)據(jù),1 H, W 4000。每個測試點還滿足如下約束：第 5 頁, 共 10 頁第頁, 共 10 頁測試點編號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無15發(fā)球機器(ballmachine.cpp/c/pas)【問題描述】有一個可看成有根樹的發(fā)球機器, 樹上的節(jié)點被編號成 1 N , 每個節(jié)點為空或包含一個球。初始時, 所有的節(jié)點都是空的。當機器運行時, 它可以支持如下的兩種操作：1. 向發(fā)球機器中添加 k 個球：球被一個一個分別放在了根節(jié)點。只要有一個空節(jié)點在球的下方, 它就會滾下去。如果一個點有多個空的子節(jié)點, 機器會選擇將球向其子樹中最小節(jié)點最小的節(jié)點滾下去。因此, 如果一個球會掉下多層, 那么機器會在每一層都作出決定。例如：如果我們向

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

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