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

CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2013）復(fù)賽提高組day11．轉(zhuǎn)圈游戲(circle.cpp/c/pas)【問題描述】n個(gè)小伙伴（編號(hào)從0到n-1）圍坐一圈玩游戲。按照順時(shí)針方向給n個(gè)位置編號(hào)，從0到n-1。最初，第0號(hào)小伙伴在第0號(hào)位置，第1號(hào)小伙伴在第1號(hào)位置，……，依此類推。游戲規(guī)則如下：每一輪第0號(hào)位置上的小伙伴順時(shí)針走到第m號(hào)位置，第1號(hào)位置小伙伴走到第m+1號(hào)位置，……，依此類推，第n?m號(hào)位置上的小伙伴走到第0號(hào)位置，第n-m+1號(hào)位置上的小伙伴走到第1號(hào)位置，……，第n-1號(hào)位置上的小伙伴順時(shí)針走到第m-1號(hào)位置?，F(xiàn)在，一共進(jìn)行了10^k輪，請(qǐng)問x號(hào)小伙伴最后走到了第幾號(hào)位置。輸入文件名為circle.in。輸入共1行，包含4個(gè)整數(shù)n、m、k、x，每兩個(gè)整數(shù)之間用一個(gè)空格隔開。11x3455對(duì)于30%的數(shù)據(jù)，0<k<7；對(duì)于80%的數(shù)據(jù)，0<k<107；對(duì)于100%的數(shù)據(jù)，1<n<1,000,000，0<m<n，0≤x≤n，0<k<109。2．火柴排隊(duì)(match.cpp/c/pas)【問題描述】涵涵有兩盒火柴，每盒裝有n根火柴，每根火柴都有一個(gè)高度。現(xiàn)在將每盒中的火柴各自排成一列，同一列火柴的高度互不相同，兩列火柴之間的距離定義為：，其中ai表示第一列火柴中第i個(gè)火柴的高度，bi表示第二列火柴中第i個(gè)火柴的高度。每列火柴中相鄰兩根火柴的位置都可以交換，請(qǐng)你通過交換使得兩列火柴之間的距離最小。請(qǐng)問得到這個(gè)最小的距離，最少需要交換多少次？如果這個(gè)數(shù)字太大，請(qǐng)輸出這個(gè)最小交換次數(shù)對(duì)99,999,997取模的結(jié)果。nn取模的結(jié)果。1】42314321411122列的前22】4134217242最小距離是10，最少需要交換2次，比如：交換第1列的中間2根火柴的位置，再交換第2列中后2根火柴的位置。對(duì)于10%的數(shù)據(jù)，1≤n≤10；對(duì)于30%的數(shù)據(jù)，1≤n≤100；對(duì)于60%的數(shù)據(jù)，1≤n≤1,000；對(duì)于100%的數(shù)據(jù)，1≤n≤100,000，0≤火柴高度≤231?1。3．貨車運(yùn)輸(truck.cpp/c/pas)【問題描述】A國有n座城市，編號(hào)從1到n，城市之間有m條雙向道路。每一條道路對(duì)車輛都有重量限制，簡稱限重?，F(xiàn)在有q輛貨車在運(yùn)輸貨物，司機(jī)們想知道每輛車在不超過車輛限重的情況下，最多能運(yùn)多重的貨物。Anm條道路。接來m行每行3整數(shù)x每兩個(gè)數(shù)用一空隔示從x號(hào)市到y(tǒng)zqqxyq433124-123333113131413對(duì)于30%的數(shù)據(jù)，0<n<1,000，0<m<10,000，0<q<1,000；對(duì)于60%的數(shù)據(jù)，0<n<1,000，0<m<50,000，0<q<1,000；對(duì)于100%的數(shù)據(jù)，0<n<10,000，0<m<50,000，0<q<30,000，0≤z≤100,000。CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2013）復(fù)賽1．積木大賽(block.cpp/c/pas)【題目描述】春春幼兒園舉辦了一年一度的“積木大賽”。今年比賽的內(nèi)容是搭建一座寬度為n的大廈，大廈可以看成由n塊寬度為1的積木組成，第i塊積木的最終高度需要是?i。在搭建開始之前，沒有任何積木（可以看成塊高度為0的積木）。接下來每次操作，小朋友們可以選擇一段連續(xù)區(qū)間[L,R]，然后將第L塊到第R塊之間（含第L塊和第R塊）所有積木的高度分別增加1。小M是個(gè)聰明的小朋友，她很快想出了建造大廈的最佳策略，使得建造所需的操作次數(shù)最少。但她不是一個(gè)勤于動(dòng)手的孩子，所以想請(qǐng)你幫忙實(shí)現(xiàn)這個(gè)策略，并求出最少的操作次數(shù)。輸入文件為block.in輸入包含兩行，第一行包含一個(gè)整數(shù)n，表示大廈的寬度。第二行包含n個(gè)整數(shù)，第i個(gè)整數(shù)為?i。5234125其中一種可行的最佳方案，依次選擇[1,5][1,3][2,3][3,3][5,5]【數(shù)據(jù)范圍】對(duì)于30%的數(shù)據(jù)，有1≤n≤10；對(duì)于70%的數(shù)據(jù)，有1≤n≤1000；對(duì)于100%的數(shù)據(jù)，有1≤n≤100000，0≤hi≤10000。2．花匠(flower.cpp/c/pas)【問題描述】花匠棟棟種了一排花，每株花都有自己的高度?；▋涸介L越大，也越來越擠。棟棟決定把這排中的一部分花移走，將剩下的留在原地，使得剩下的花能有空間長大，同時(shí)，棟棟希望剩下的花排列得比較別致。具體而言，棟棟的花的高度可以看成一列整數(shù)?1,?2,…,?n。設(shè)當(dāng)一部分花被移走后，剩下的花的高度依次為g1,g2,…,gm，則棟棟希望下面兩個(gè)條件中至少有一個(gè)滿足：條件A：對(duì)于所有的1≤i≤，有g(shù)2i>g2i-1，同時(shí)對(duì)于所有的1≤i≤，有g(shù)2i>g2i+1；條件B：對(duì)于所有的1≤i≤，有g(shù)2i<g2i-1，同時(shí)對(duì)于所有的1≤i≤，有g(shù)2i<g2i+1。注意上面兩個(gè)條件在m=1時(shí)同時(shí)滿足，當(dāng)m>1時(shí)最多有一個(gè)能滿足。請(qǐng)問，棟棟最多能將多少株花留在原地。第二行包含個(gè)整數(shù)，依次為?1,?2,…,?n，表示每株花的高度。55321233【數(shù)據(jù)范圍】對(duì)于20%的數(shù)據(jù)，n≤10；對(duì)于30%的數(shù)據(jù)，n≤25；對(duì)于70%的數(shù)據(jù)，n≤1000，0≤?n≤1000；對(duì)于100%的數(shù)據(jù)，1≤n≤100,000，0≤?n≤1,000,000，所有的?n隨機(jī)生成，所有隨機(jī)數(shù)服從某區(qū)間內(nèi)的均勻分布。3．華容道(puzzle.cpp/c/pas)【問題描述】小B最近迷上了華容道，可是他總是要花很長的時(shí)間才能完成一次。于是，他想到用編程來完成華容道：給定一種局面，華容道是否根本就無法完成，如果能完成，最少需要多少時(shí)間。小B玩的華容道與經(jīng)典的華容道游戲略有不同，游戲規(guī)則是這樣的：1. 在一個(gè)n*m棋盤上有n*m個(gè)格子，其中有且只有一個(gè)格子是空白的，其余n*m-1個(gè)格子上每個(gè)格子上有一個(gè)棋子，每個(gè)棋子的大小都是1*1的；2. 有些棋子是固定的，有些棋子則是可以移動(dòng)的；3. 任何與空白的格子相鄰（有公共的邊）的格子上的棋子都可以移動(dòng)到空白格子上。游戲的目的是把某個(gè)指定位置可以活動(dòng)的棋子移動(dòng)到目標(biāo)位置。給定一個(gè)棋盤，游戲可以玩q次，當(dāng)然，每次棋盤上固定的格子是不會(huì)變的，但是棋盤上空白的格子的初始位置、指定的可移動(dòng)的棋子的初始位置和目標(biāo)位置卻可能不同。第i次玩的時(shí)候，空白的格子在第EXi行第EYi列，指定的可移動(dòng)棋子的初始位置為第SXi行第SYi列，目標(biāo)位置為第TXi行第TYi列。假設(shè)小B每秒鐘能進(jìn)行一次移動(dòng)棋子的操作，而其他操作的時(shí)間都可以忽略不計(jì)。請(qǐng)你告訴小B每一次游戲所需要的最少時(shí)間，或者告訴他不可能完成游戲。3和q；nmq6輸出文件名為puzzle.out。輸出有q行，每行包含1個(gè)整數(shù)，表示每次游戲所需要的最少時(shí)間，如果某次游戲無法完成目標(biāo)則輸出?1。3420111011001003212221222322-1棋盤上劃叉的格子是固定的，紅色格子是目標(biāo)位置，圓圈表示棋子，其中綠色圓圈表示目標(biāo)棋子。1.第一次游戲，空白格子的初始位置是(3,2)（圖中空白所示），游戲的目標(biāo)是將初始位置在(1,2)上的棋子（圖中綠色圓圈所代表的棋子）移動(dòng)到目標(biāo)位置(2,2)（圖中紅色的格子）上。移動(dòng)過程如下：初始狀態(tài)第一步之后第二步之后2.第二次游戲，空白格子的初始位置是（1,2）（圖中空白所示），游戲的目標(biāo)是將初始位置在（2,2）上的棋子（圖中綠色圓圈所示）移動(dòng)到目標(biāo)位置(3,2)上。初始狀態(tài)要將指定塊移入目標(biāo)位置，必須先將空白塊移入目標(biāo)位置，空白塊要移動(dòng)到目標(biāo)位置，必然是從位