NOIP2013提高組復(fù)賽試題day1+day2

1、全國信息學(xué)奧林匹克聯(lián)賽（2013）復(fù)賽提高組11轉(zhuǎn)圈游戲（）【問題描述】n個(gè)小伙伴（編號從0到1）圍坐一圈玩游戲。按照順時(shí)針方向給n個(gè)位置編號，從0到1。最初，第0號小伙伴在第0號位置，第1號小伙伴在第1號位置，依此類推。游戲規(guī)則如下：每一輪第0號位置上的小伙伴順時(shí)針走到第m號位置，第1號位置小伙伴走到第1號位置，依此類推，第n-m號位置上的小伙伴走到第0號位置，第1號位置上的小伙伴走到第1號位置，第1號位置上的小伙伴順時(shí)針走到第1號位置?，F(xiàn)在，一共進(jìn)行了10k輪，請問x號小伙伴最后走到了第幾號位置?！据斎搿枯斎胛募麨?。輸入共1行，包含4個(gè)整數(shù)n、mk、x，每兩個(gè)整數(shù)之間用一個(gè)空格隔開。【輸

2、出】輸出文件名為。輸出共1行，包含1個(gè)整數(shù)，表示10k輪后x號小伙伴所在的位置編號。【輸入輸出樣例】103455【數(shù)據(jù)說明】對于30%的數(shù)據(jù)，0<k<7;對于80%的數(shù)據(jù)，0<k<107;對于100%的數(shù)據(jù)，1<n<1,000,000,0<m<n,0wx<n,0<k<102.火柴排隊(duì)()【問題描述】涵涵有兩盒火柴，每盒裝有n根火柴，每根火柴都有一個(gè)高度。現(xiàn)在將每盒中的火柴各自排成一列，同一列火柴的高度互不相同，兩列火柴之間的距離定義為：】，其中表示第一列火柴中第i個(gè)火柴的高度，表示第二列火柴中第i個(gè)火柴的高度。每列火柴中相鄰兩根

3、火柴的位置都可以交換，請你通過交換使得兩列火柴之間的距離最小。請問得到這個(gè)最小的距離，最少需要交換多少次？如果這個(gè)數(shù)字太大，請輸出這個(gè)最小交換次數(shù)對99,999,997取模的結(jié)果?！据斎搿枯斎胛募楣踩校谝恍邪粋€(gè)整數(shù)n表示每盒中火柴的數(shù)目。第二行有n個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示第一列火柴的高度。第三行有n個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示第二列火柴的高度。【輸出】輸出文件為。輸出共一行，包含一個(gè)整數(shù)，表示最少交換次數(shù)對99,999,997取模的結(jié)果?！据斎胼敵鰳永?】42 3143 2141【輸入輸出樣例說明】最小距離是0，最少需要交換1次，比如：交換第1列的前2

4、根火柴或者交換第2列的前2根火柴。【輸入輸出樣例2】4134217242【輸入輸出樣例說明】最小距離是10，最少需要交換2次，比如：交換第1列的中間2根火柴的位置，再交換第2列中后2根火柴的位置。【數(shù)據(jù)范圍】對于10%的數(shù)據(jù)，1<n<10；對于30%的數(shù)據(jù)，1<n<100;對于60%的數(shù)據(jù)，1<nW1,000;對于100%的數(shù)據(jù)，1wnW100,000,0W火柴高度W231-1。3貨車運(yùn)輸()【問題描述】A國有n座城市，編號從1到n，城市之間有m條雙向道路。每一條道路對車輛都有重量限制，簡稱限重?，F(xiàn)在有q輛貨車在運(yùn)輸貨物，司機(jī)們想知道每輛車在不超過車輛限重的情況下

5、，最多能運(yùn)多重的貨物。【輸入】輸入文件名為。輸入文件第一行有兩個(gè)用一個(gè)空格隔開的整數(shù)n,m表示A國有n座城市和m條道路。接下來m行每行3個(gè)整數(shù)x、y、z，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示從x號城市到y(tǒng)號城市有一條限重為z的道路。注意：x不等于y，兩座城市之間可能有多條道路。接下來一行有一個(gè)整數(shù)q，表示有q輛貨車需要運(yùn)貨。接下來q行，每行兩個(gè)整數(shù)x、y，之間用一個(gè)空格隔開，表示輛貨車需要從x城市運(yùn)輸貨物到y(tǒng)城市，注意：x不等于y【輸出】輸出文件名為輸出共有q行，每行一個(gè)整數(shù)，表示對于每一輛貨車，它的最大載重是多少。如果貨車不能到達(dá)目的地，輸出-1。【輸入輸出樣例】433124-12333311

6、3131413【數(shù)據(jù)說明】對于30%的數(shù)據(jù)，0<n<1,000，0<m<10,000,0<q<1,000；對于60%的數(shù)據(jù)，0<n<1,000，0<m<50,000，0<q<1,000；對于100%的數(shù)據(jù)，0<n<10,000，0<m<50,000，0<q<30,000,0wz<100,000。全國信息學(xué)奧林匹克聯(lián)賽(2013)復(fù)賽提高組21.積木大賽()【題目描述】春春幼兒園舉辦了一年一度的“積木大賽”。今年比賽的內(nèi)容是搭建一座寬度為n的大廈，大廈可以看成由n塊寬度為1的積木組成

7、，第i塊積木的最終高度需要是?i。在搭建開始之前，沒有任何積木（可以看成塊高度為0的積木）。接下來每次操作，小朋友們可以選擇一段連續(xù)區(qū)間，然后將第L塊到第R塊之間（含第L塊和第R塊）所有積木的高度分別增加1。小M是個(gè)聰明的小朋友，她很快想出了建造大廈的最佳策略，使得建造所需的操作次數(shù)最少。但她不是一個(gè)勤于動手的孩子，所以想請你幫忙實(shí)現(xiàn)這個(gè)策略，并求出最少的操作次數(shù)?！据斎搿枯斎胛募檩斎氚瑑尚校谝恍邪粋€(gè)整數(shù)n，表示大廈的寬度。第二行包含n個(gè)整數(shù)，第i個(gè)整數(shù)為?i?！据敵觥枯敵鑫募閮H一行，即建造所需的最少操作數(shù)。【輸入輸出樣例】5234125【樣例解釋】其中一種可行的最佳方案，依次選擇

8、1,51,32,33,35,5【數(shù)據(jù)范圍】對于30%的數(shù)據(jù)，有1<nW10;對于70%的數(shù)據(jù)，有1WnW1000;對于100%的數(shù)據(jù)，有1WnW100000,0WW10000。2.花匠()【問題描述】花匠棟棟種了一排花，每株花都有自己的高度。花兒越長越大，也越來越擠。棟棟決定把這排中的一部分花移走，將剩下的留在原地，使得剩下的花能有空間長大，同時(shí)，棟棟希望剩下的花排列得比較別致。具體而言，棟棟的花的高度可以看成一列整數(shù)？1,?2,，？n。設(shè)當(dāng)一部分花被移走后，剩下的花的高度依次為g1,g2,，則棟棟希望下面兩個(gè)條件中至少有一個(gè)滿足：條件A:對于所有的1WiW，有g(shù)2i>g21，同時(shí)

9、對于所有的1WiWa，有g(shù)2i>g21；條件B:對于所有的1WiW3，有g(shù)2i<g21,同時(shí)對于所有的1WiW0，有g(shù)2i<g210注意上面兩個(gè)條件在m=1時(shí)同時(shí)滿足，當(dāng)m>1時(shí)最多有一個(gè)能滿足。請問，棟棟最多能將多少株花留在原地【輸入】輸入文件為。輸入的第一行包含一個(gè)整數(shù)，表示開始時(shí)花的株數(shù)第二行包含個(gè)整數(shù)，依次為？1,?2，,?n,表示每株花的高度?！据敵觥枯敵鑫募椤］敵鲆恍?，包含一個(gè)整數(shù)，表示最多能留在原地的花的株數(shù)。【輸入輸出樣例】5532123【輸入輸出樣例說明】有多種方法可以正好保留3株花，例如，留下第1、4、5株，高度分別為5、1、2,滿足條件Bo【數(shù)據(jù)

10、范圍】對于20%的數(shù)據(jù)，nW10;對于30%的數(shù)據(jù)，nW25;對于70%的數(shù)據(jù)，nW1000,0W?nW1000；對于100%的數(shù)據(jù)，1WnW100,000,0W?nW1,000,000,所有的？門隨機(jī)生成，所有隨機(jī)數(shù)服從某區(qū)間內(nèi)的均勻分布。3.華容道()【問題描述】小B最近迷上了華容道，可是他總是要花很長的時(shí)間才能完成一次。于是，他想到用編程來完成華容道：給定一種局面，華容道是否根本就無法完成，如果能完成，最少需要多少時(shí)間。小B玩的華容道與經(jīng)典的華容道游戲略有不同，游戲規(guī)則是這樣的：1. 在一個(gè)n*m棋盤上有n*m個(gè)格子，其中有且只有一個(gè)格子是空白的，其余n*1個(gè)格子上每個(gè)格子上有一個(gè)棋子，

11、每個(gè)棋子的大小都是1*1的；2. 有些棋子是固定的，有些棋子則是可以移動的；3. 任何與空白的格子相鄰（有公共的邊）的格子上的棋子都可以移動到空白格子上。游戲的目的是把某個(gè)指定位置可以活動的棋子移動到目標(biāo)位置。給定一個(gè)棋盤，游戲可以玩q次，當(dāng)然，每次棋盤上固定的格子是不會變的，但是棋盤上空白的格子的初始位置、指定的可移動的棋子的初始位置和目標(biāo)位置卻可能不同。第i次玩的時(shí)候，空白的格子在第行第列，指定的可移動棋子的初始位置為第行第列，目標(biāo)位置為第行第列。假設(shè)小B每秒鐘能進(jìn)行一次移動棋子的操作，而其他操作的時(shí)間都可以忽略不計(jì)。請你告訴小B每一次游戲所需要的最少時(shí)間，或者告訴他不可能完成游戲?！据斎?/p>

12、】輸入文件為。第一行有3個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，依次表示n、m和q；接下來的n行描述一個(gè)n*m的棋盤，每行有m個(gè)整數(shù)，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，每個(gè)整數(shù)描述棋盤上一個(gè)格子的狀態(tài)，0表示該格子上的棋子是固定的，1表示該格子上的棋子可以移動或者該格子是空白的。接下來的q行，每行包含6個(gè)整數(shù)依次是、，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，表示每次游戲空白格子的位置，指定棋子的初始位置和目標(biāo)位置?！据敵觥枯敵鑫募麨椤］敵鲇衠行，每行包含1個(gè)整數(shù)，表示每次游戲所需要的最少時(shí)間，如果某次游戲無法完成目標(biāo)則輸出-1?！据斎胼敵鰳永?420111011001003212221222322-1【輸入輸出樣例說明】棋盤上劃叉的格子是固定的，紅色格子是目標(biāo)位置，圓圈表示棋子，其中綠色圓圈表示目標(biāo)棋子。1.第一次游戲，空白格子的初始位置是（3,2）（圖中空白所示），游戲的目標(biāo)是將初始位置在（1,2）上的棋子（圖中綠色圓圈所代表的棋子）移動到目標(biāo)位置（2,2）（圖中紅色的格子）上。移動過程如下：初始狀態(tài)第一步之后第二步之后2.第二次游戲，空白格子的初始位置是（1,2）（圖中空白所示），游戲的目標(biāo)是將初始位置在（2,2）上的棋子（圖中綠色圓圈所示）移動到目標(biāo)位置（3,2）上。初始狀態(tài)XIo0AcXI1劊要將指定塊移入目