noip2017提高組試題(day1+day2)-Word版

1、CCF全國信息學(xué)奧林匹克聯(lián)賽NOIP2022丨復(fù)賽提咼組dayl請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容中文題目名稱小凱的疑惑時間復(fù)雜度逛公園央文題目與子目錄名:mathcomplexitypark可執(zhí)行文件名mathcomplexitypark輸入文件名輸出文件名每個測試點時限1秒1秒3秒測試點數(shù)目201010每個測試點分值51010附加樣例文件有有有結(jié)果比擬方式全文比擬過濾行末空格及文末回車題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內(nèi)存上限256M256M512M.提交源程序文件名對于C+語言對于C語言對于 pascal語言三編譯命令不包含任何優(yōu)化開關(guān)對于C+語言g+ -o math math.cpp -lmg+ -o

2、complexity complexity.cpp -lmg+ -o park park.cpp -lm對于C語言-lmgcc -o complexity complexity.c -lm-lm對于 pascal語言考前須知：1、文件名程序名和輸入輸出文件名必須使用英文小寫。2、 C/C+中函數(shù) main()的返回值類型必須是int,程序正常結(jié)束時的返回值必須是0。3、 全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor ,內(nèi)存 4G,上述時限以此配置為準(zhǔn)。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省

3、的具體要求。6、 特別提醒：評測在當(dāng)前最新公布的NOI Lin ux下進行，各語言的編譯器版本以其為準(zhǔn)。1 .小凱的疑惑(math.cpp/c/pas)【問題描述】小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且彼此互素。每種金幣小凱都有 無數(shù)個。在不找零的情況下，僅憑這兩種金幣，有些物品他是無法準(zhǔn)確支付的?，F(xiàn)在小凱 想知道在無法準(zhǔn)確支付的物品中，最貴的價值是多少金幣？注意：輸入數(shù)據(jù)保證存在小凱 無法準(zhǔn)確支付的商品?！据斎敫袷健枯斎胛募麨?。輸入數(shù)據(jù)僅一行，包含兩個正整數(shù) a和b,它們之間用一個空格隔開，表示小凱手 中金幣的面值?！据敵龈袷健枯敵鑫募麨?。輸出文件僅一行，一個正整數(shù)N，表示不找零

4、的情況下，小凱用手中的金幣不能準(zhǔn)確支付的最貴的物品的價值?！据斎胼敵鰳永?】3 711見選手目錄下的和【輸入輸出樣例1說明】小凱手中有面值為3和7的金幣無數(shù)個，在不找零的前提下無法準(zhǔn)確支付價值為 1、 2、4、5、8、11的物品，其中最貴的物品價值為11，比11貴的物品都能買到，比方:12 = 3 * 4 + 7 * 013 = 3 * 2 + 7 * 114 = 3 * 0 + 7 * 215 = 3 * 5 + 7 * 0【輸入輸出樣例2】見選手目錄下的和【數(shù)據(jù)規(guī)模與約定】對于30%的數(shù)據(jù)：1a,b50。對于60%的數(shù)據(jù)：1a,b10,000。對于100%的數(shù)據(jù)：1a,b1,000,000

5、,0002 .時間復(fù)雜度(complexity.cpp/c/pas)【問題描述】小明正在學(xué)習(xí)一種新的編程語言A+，剛學(xué)會循環(huán)語句的他沖動地寫了好多程序并給出了他自己算出的時間復(fù)雜度，可他的編程老師實在不想一個一個檢查小明的程序， 于是你的時機來啦！下面請你編寫程序來判斷小明對他的每個程序給出的時間復(fù)雜度是否 正確。A+語言的循環(huán)結(jié)構(gòu)如下：F i x y循環(huán)體E其中“ Fixy 表示新建變量 變量i不可與未被銷毀的變量重名 并初始化為x， 然后判斷i和y的大小關(guān)系，假設(shè)i小于等于y那么進入循環(huán)，否那么不進入。每次循環(huán)結(jié) 束后i都會被修改成i +1，一旦i大于y終止循環(huán)。x和y可以是正整數(shù)x和y的

6、大小關(guān)系不定或變量n。n是一個表示數(shù)據(jù)規(guī)模的 變量，在時間復(fù)雜度計算中需保存該變量而不能將其視為常數(shù)，該數(shù)遠大于100?！癊表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時，這個循環(huán)體新建的變量也被銷毀。注：此題中為了書寫方便，在描述復(fù)雜度時，使用大寫英文字母“O表示通常意義下“ 的概念?！据斎敫袷健枯斎胛募麨?。輸入文件第一行一個正整數(shù) t，表示有t t < 10丨個程序需要計算時間復(fù)雜度。 每個程序我們只需抽取其中“ F i x y和“ E即可計算時間復(fù)雜度。注意：循環(huán)結(jié)構(gòu)允許嵌套。接下來每個程序的第一行包含一個正整數(shù) L和一個字符串，L代表程序行數(shù)，字符串 表示這個程序的復(fù)雜度，0(1) 表示常數(shù)復(fù)雜

7、度，0(nw) 表示復(fù)雜度為？?，其中w 是一個小于100的正整數(shù)輸入中不包含引號，輸入保證復(fù)雜度只有0(1)和O(nAw) 兩 種類型。接下來L行代表程序中循環(huán)結(jié)構(gòu)中的“ F i x y "或者 “ E 。程序行假設(shè)以“F開頭，表示進入一個循環(huán)，之后有空格別離的三個字符串i x y , 其中i是一個小寫字母保證不為“ n，表示新建的變量名，x和y可能是正整數(shù)或 n，假設(shè)為正整數(shù)那么一定小于 100。程序行假設(shè)以“ E開頭，那么表示循環(huán)體結(jié)束。【輸出格式】輸出文件名為。輸出文件共t行，對應(yīng)輸入的t個程序，每行輸出“ Yes或“No或者“ ERR輸 出中不包含引號，假設(shè)程序?qū)嶋H復(fù)雜度與

8、輸入給出的復(fù)雜度一致那么輸出“Yes，不一致那么輸出“ No，假設(shè)程序有語法錯誤其中語法錯誤只有：F和E不匹配 新建 的變量與已經(jīng)存在但未被銷毀的變量重復(fù)兩種情況 ，那么輸出“ ERR。注意：即使在程序不會執(zhí)行的循環(huán)體中出現(xiàn)了語法錯誤也會編譯錯誤，要輸出【輸入輸出樣例1】82 0(1)F i 1 1E2 0( n")F x 1 nE1 0(1)F x 1 n4 0( n2)F x 5 nF y 10 nEE4 0( n2)F x 9 nEF y 2 nE4 0( n")F x 9 nF y n 4EE4 0(1)F y n 4F x 9 nEE4 0( n2)F x 1 n

9、F x 1 10EEYesYesERRYesNoYesYesERR見選手目錄下的 和?！据斎胼敵鰳永?1說明】第一個程序i從1到1是常數(shù)復(fù)雜度。第二個程序x從1到n是n的一次方的復(fù)雜度。 第三個程序有一個 F 開啟循環(huán)卻沒有 E 結(jié)束，語法錯誤。 第四個程序二重循環(huán)， n 的平方的復(fù)雜度。 第五個程序兩個一重循環(huán)， n 的一次方的復(fù)雜度。 第六個程序第一重循環(huán)正常，但第二重循環(huán)開始即終止因為 n 遠大于 100，100 大于 4。 第七個程序第一重循環(huán)無法進入，故為常數(shù)復(fù)雜度。第八個程序第二重循環(huán)中的變量x與第一重循環(huán)中的變量重復(fù)，出現(xiàn)語法錯誤，輸出ERR?！据斎胼敵鰳永?2】見選手目錄下的和

10、?！緮?shù)據(jù)規(guī)模與約定】對于 30%的數(shù)據(jù)：不存在語法錯誤，數(shù)據(jù)保證小明給出的每個程序的前 L/2 行一定 為以 F 開頭的語句，第 L/2+1 行至第 L 行一定為以 E 開頭的語句， L<=10 ，假設(shè) x、y 均為整數(shù)，x 一定小于y,且只有y有可能為n。對于50%的數(shù)據(jù)：不存在語法錯誤，Lv=100,且假設(shè)x、y均為整數(shù)，x 一定小于y， 且只有 y 有可能為 n。對于 70%的數(shù)據(jù)：不存在語法錯誤,Lv=100。對于 100%的數(shù)據(jù)： Lv=100。3.逛公園(park.cpp/c/pas)【問題描述】策策同學(xué)特別喜歡逛公園。公園可以看成一張？?個點？?條邊構(gòu)成的有向圖，且沒有自環(huán)

11、和重邊。其中1號點是公園的入口， ？號點是公園的出口，每條邊有一個非負(fù)權(quán)值， 代表策策經(jīng)過這條邊所要花的時間。策策每天都會去逛公園，他總是從1號點進去，從？號點出來。策策喜歡新鮮的事物，他不希望有兩天逛公園的路線完全一樣，同時策策還是一個 特別熱愛學(xué)習(xí)的好孩子，他不希望每天在逛公園這件事上花費太多的時間。如果1號點到?號點的最短路長為？那么策策只會喜歡長度不超過 ?+ ?勺路線。策策同學(xué)想知道總共有多少條滿足條件的路線，你能幫幫他嗎？為防止輸出過大，答案對？取模。如果有無窮多條合法的路線，請輸出-1?！据斎敫袷健枯斎胛募麨椤５谝恍邪粋€整數(shù) ？代表數(shù)據(jù)組數(shù)。接下來？組數(shù)據(jù)，對于每組數(shù)據(jù)：第

12、一行包含四個整數(shù) ?, ?每兩個整數(shù)之間用一個空格隔開。接下來？?行，每行三個整數(shù)？?？代表編號為？?的點之間有一條權(quán)值為？勺有 向邊，每兩個整數(shù)之間用一個空格隔開?！据敵龈袷健枯敵鑫募麨?。輸出文件包含？行，每行一個整數(shù)代表答案?！据斎胼敵鰳永?】235 7 2 10-11 2 12 4 04 5 22 3 23 4 13 5 21 5 32 2 0 101 2 02 1 0見選手目錄下的 和。對于第一組數(shù)據(jù)，最短路為31 -5, 1 -2 -4 -5, 1 -2 -3 -5 為 3 條合法路徑?！据斎胼敵鰳永?】 見選手目錄下的和?！緮?shù)據(jù)規(guī)模與約定】對于不同的測試點，我們約定各種參數(shù)的規(guī)模

13、不會超過如下測試點編號?是否有0邊155100否125100020000否351000200050否451000200050否551000200050否651000200050是751000002000000否8310000020000050否9310000020000050是10310000020000050是對于 100%的數(shù)據(jù)，1 < 2? 109, 1 < ?戶？0 < ? 1000。 數(shù)據(jù)保證：至少存在一條合法的路線。CCF全國信息學(xué)奧林匹克聯(lián)賽NOIP2022丨復(fù)賽提高組day2請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容中文題目名稱奶酪寶藏列隊央文題目與子目錄名:cheesetr

14、easurephala nx可執(zhí)行文件名cheesetreasurephala nx輸入文件名輸出文件名每個測試點時限1秒1秒2秒測試點數(shù)目102020每個測試點分值1055附加樣例文件有有有結(jié)果比擬方式全文比擬過濾行末空格及文末回車題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內(nèi)存上限256M256M512M.提交源程序文件名對于C+語言對于C語言對于 pascal語言三編譯命令不包含任何優(yōu)化開關(guān)對于C+語言g+ -o cheese cheese.cpp -lmg+ -o treasure treasure.cpp -lmg+ -o phala nx phala nx.cpp -lm對于C語言gcc -o che

15、ese cheese.c -lmgcc -o treasure treasure.c -lmgcc -o phala nx phala nx.c -lm對于 pascal語言考前須知：1、文件名程序名和輸入輸出文件名必須使用英文小寫。2、 C/C+中函數(shù) main()的返回值類型必須是int,程序正常結(jié)束時的返回值必須是0。3、 全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor ,內(nèi)存 4G,上述時限以此配置為準(zhǔn)。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省的具體要求。6、 特別提醒：評測在當(dāng)前最新

16、公布的NOI Lin ux下進行，各語言的編譯器版本以其為準(zhǔn)。1 .奶酪(cheese.cpp/c/pas)【問題描述】現(xiàn)有一塊大奶酪，它的高度為 h，它的長度和寬度我們可以認(rèn)為是無限大的，奶酪 中 間有許多半徑相同的球形空洞。我們可以在這塊奶酪中建立空間坐標(biāo)系，在坐標(biāo)系中，奶酪的 下外表為z = 0，奶酪的上外表為z = h?，F(xiàn)在，奶酪的下外表有一只小老鼠Jerry，它知道奶酪中所有空洞的球心所在的坐標(biāo)。如果兩個空洞相切或是相交，那么 Jerry可以從其中一個空洞跑到另一個空洞，特別 地，如果一個空洞與下外表相切或是相交，Jerry那么可以從奶酪下外表跑進空洞；如果一個空洞與上外表相切或是相

17、交，Jerry那么可以從空洞跑到奶酪上外表。位于奶酪下外表的 Jerry想知道，在 不破壞奶酪的情況下，能否利用已有的空洞跑 到奶酪的上外表去？空間內(nèi)兩點?(?, ?, ?、?(?, ?, ?的距離公式如下：dist(?, ?) = v(? - ?)2 + (? - ?)2 + (? - ?)2【輸入格式】輸入文件名為。每個輸入文件包含多組數(shù)據(jù)。輸入文件的第一行，包含一個正整數(shù)T,代表該輸入文件中所含的數(shù)據(jù)組數(shù)。接下來是T組數(shù)據(jù)，每組數(shù)據(jù)的格式如下：第一行包含三個正整數(shù)n, h和r,兩個數(shù)之間以一個空格分開，分別代表奶酪中空 洞的數(shù)量，奶酪的高度和空洞的半徑。接下來的n行，每行包含三個整數(shù) x

18、、y、z,兩個數(shù)之間以一個空格分開，表示空 洞球心坐標(biāo)為(? ?o【輸出格式】輸出文件名為。輸出文件包含T行，分別對應(yīng)T組數(shù)據(jù)的答案，如果在第i組數(shù)據(jù)中，Jerry能從下 外表跑到上外表，那么輸出“ Yes ，如果不能，那么輸出“ No均不包含引號?！据斎胼敵鰳永?】3Yes2 4 1No0 0 1Yes0 0 32 5 10 0 10 0 42 5 20 0 22 0 4見選手目錄下的和?！据斎胼敵鰳永?說明】第一組數(shù)據(jù)，由奶酪的剖面圖可見：第一個空洞在0，0，0與下外表相切 第二個空洞在0，0，4與上外表相切 兩個空洞在0, 0，2相切輸出Yes第二組數(shù)據(jù)，由奶酪的剖面圖可見:兩個空洞既不

19、相交也不相切輸出No第三組數(shù)據(jù)，由奶酪的剖面圖可見:兩個空洞相交且與上下外表相切或相交輸出Yes【輸入輸出樣例2】 見選手目錄下的和?！緮?shù)據(jù)規(guī)模與約定】對于20%的數(shù)據(jù)，n = 1, 1 < h , r < 10,000,坐標(biāo)的絕對值不超過10,000。對于40%的數(shù)據(jù)，1 < n < 8, 1 < h , r w 10,000,坐標(biāo)的絕對值不超過 10,000。對 于80%的數(shù)據(jù)，1 w n w 1,000, 1 w h , r w 10,000,坐標(biāo)的絕對值不超過10,000。對 于 100%的數(shù)據(jù)，1 w n w 1,000, 1 w h , r w 1,0

20、00,000,000, T w 20,坐標(biāo)的 絕對值不超過 1,000,000,000。2.寶藏treasure.cpp/c/pas)【問題描述】參與考古挖掘的小明得到了一份藏寶圖，藏寶圖上標(biāo)出了n個深埋在地下的寶藏屋,也給出了這n個寶藏屋之間可供開發(fā)的 m條道路和它們的長度。小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個寶藏屋距離地面都很遠， 也就是說，從地面打通一條到某個寶藏屋的道路是很困難的，而開發(fā)寶藏屋之間的道路那么 相對容易很多。小明的決心感動了考古挖掘的贊助商，贊助商決定免費贊助他打通一條從地面到某 個寶藏屋的通道，通往哪個寶藏屋那么由小明來決定。在此根底上，小明還需要考慮如何

21、開鑿寶藏屋之間的道路。已經(jīng)開鑿出的道路可以 任意通行不消耗代價。每開鑿出一條新道路，小明就會與考古隊一起挖掘出由該條道路所 能到達的寶藏屋的寶藏。另外，小明不想開發(fā)無用道路，即兩個已經(jīng)被挖掘過的寶藏屋之 間的道路無需再開發(fā)。新開發(fā)一條道路的代價是：這條道路的長度 x從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經(jīng)過的 寶藏屋的數(shù)量包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋。請你編寫程序為小明選定由贊助商打通的寶藏屋和之后開鑿的道路，使得工程總代 價最小，并輸出這個最小值?！据斎敫袷健枯斎胛募麨?。第一行兩個用空格別離的正整數(shù)n和m，代表寶藏屋的個數(shù)和道路數(shù)。接下來m行，每行三個用空格別

22、離的正整數(shù)，分別是由一條道路連接的兩個寶藏 屋的編號編號為1n，和這條道路的長度V?！据敵龈袷健枯敵鑫募麨?。輸出共一行，一個正整數(shù)，表示最小的總代價【輸入輸出樣例 1】4 51 2 11 3 31 4 12 3 43 4 14見選手目錄下的與【輸入輸出樣例1說明】小明選定讓贊助商打通了 1號寶藏屋。小明開發(fā)了道路12,挖掘了 2號寶藏。開發(fā)了道路1 4,挖掘了 4號寶藏。還開發(fā)了道路4 3,挖掘了 3號寶 藏。工程總代價為：1 X 1 +1x 1 + 1x 2 = 4(1 2)(14)(4 3)【樣例輸入輸出 2】4 51 2 11 3 31 4 12 3 43 4 25見選手目錄下的與?！?/p>

23、輸入輸出樣例2說明】小明選定讓贊助商打通了 1號寶藏屋。小明開發(fā)了道路12,挖掘了 2號寶藏。開發(fā)了道路1 3,挖掘了 3號寶藏。還開發(fā)了道路14,挖掘了 4號寶藏。工程總代價為：1 X 1 + 3x 1 + 1 X 1 = 5(1 2)(13)(1 4)【輸入輸出樣例3】見選手目錄下的和。數(shù)據(jù)規(guī)模與約定】對于 20%的數(shù)據(jù)：保證輸入是一棵樹，1 <n<8, v< 5000且所有的v都相等。對于 40%的數(shù)據(jù)：K nW 8, 0< m< 1000, v< 5000 且所有的 v 都相等。對于 70%的數(shù)據(jù)：1WnW8,0WmW1000,vW 5000對于 1

24、00% 的數(shù)據(jù)： 1WnW12,0WmW1000,vW 5000003 .列隊(phala nx.cpp/c/pas)【問題描述】Sylvia是一個熱愛學(xué)習(xí)的女孩子。前段時間，Sylvia參加了學(xué)校的軍訓(xùn)。眾所周知，軍訓(xùn)的時候需要站方陣。Sylvia所在的方陣中有n x m名學(xué)生，方陣的行數(shù)為n,列數(shù)為m。為了便于管理，教官在訓(xùn)練開始時，按照從前到后，從左到右的順序給方陣中 的學(xué)生從1至U n x m編上了號碼參見后面的樣例。即：初始時，第i行第j列 的學(xué)生的編號是(i - 1) x m + jo然而在練習(xí)方陣的時候，經(jīng)常會有學(xué)生因為各種各樣的事情需要離隊。在一天 中，一共發(fā)生了 q件這樣的離隊事件。每一次離隊事件可以用數(shù)對(？ (1 <x<n,1 < y< n描述，表示第x行第y列的學(xué)生離隊。在有學(xué)生離隊后，隊伍中出現(xiàn)了一個空位。為了隊伍的整齊，教官會依次下達 這樣的兩條指令：1. 向左看齊。這時第一列保持不動，所有學(xué)生向左填補空缺。不難發(fā)現(xiàn)在這條 指令之后，空位在第x行第m列。2. 向前看齊。這時第一行保持不動，所有學(xué)生向前填補空缺。不難發(fā)現(xiàn)在這條 指令之后，空位在第n行第m列。教官規(guī)定不能有兩個或更多學(xué)生同時離隊。即在前一個離隊的學(xué)生歸隊之后， 下一個學(xué)生才能離隊。因此在每一個離隊的學(xué)