1、CCF全國信息學奧林匹克聯賽NOIP2022丨復賽提咼組dayl請選手務必仔細閱讀本頁內容中文題目名稱小凱的疑惑時間復雜度逛公園央文題目與子目錄名:mathcomplexitypark可執行文件名mathcomplexitypark輸入文件名輸出文件名每個測試點時限1秒1秒3秒測試點數目201010每個測試點分值51010附加樣例文件有有有結果比擬方式全文比擬過濾行末空格及文末回車題目類型傳統傳統傳統運行內存上限256M256M512M.提交源程序文件名對于C+語言對于C語言對于 pascal語言三編譯命令不包含任何優化開關對于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+中函數 main()的返回值類型必須是int,程序正常結束時的返回值必須是0。3、 全國統一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor ,內存 4G,上述時限以此配置為準。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省

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

4、的情況下，小凱用手中的金幣不能準確支付的最貴的物品的價值。【輸入輸出樣例1】3 711見選手目錄下的和【輸入輸出樣例1說明】小凱手中有面值為3和7的金幣無數個，在不找零的前提下無法準確支付價值為 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】見選手目錄下的和【數據規模與約定】對于30%的數據：1a,b50。對于60%的數據：1a,b10,000。對于100%的數據：1a,b1,000,000

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

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

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

8、輸入給出的復雜度一致那么輸出“Yes，不一致那么輸出“ No，假設程序有語法錯誤其中語法錯誤只有：F和E不匹配 新建 的變量與已經存在但未被銷毀的變量重復兩種情況 ，那么輸出“ ERR。注意：即使在程序不會執行的循環體中出現了語法錯誤也會編譯錯誤，要輸出【輸入輸出樣例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是常數復雜度。第二個程序x從1到n是n的一次方的復雜度。 第三個程序有一個 F 開啟循環卻沒有 E 結束，語法錯誤。 第四個程序二重循環， n 的平方的復雜度。 第五個程序兩個一重循環， n 的一次方的復雜度。 第六個程序第一重循環正常，但第二重循環開始即終止因為 n 遠大于 100，100 大于 4。 第七個程序第一重循環無法進入，故為常數復雜度。第八個程序第二重循環中的變量x與第一重循環中的變量重復，出現語法錯誤，輸出ERR。【輸入輸出樣例 2】見選手目錄下的和

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

11、和重邊。其中1號點是公園的入口， ？號點是公園的出口，每條邊有一個非負權值， 代表策策經過這條邊所要花的時間。策策每天都會去逛公園，他總是從1號點進去，從？號點出來。策策喜歡新鮮的事物，他不希望有兩天逛公園的路線完全一樣，同時策策還是一個 特別熱愛學習的好孩子，他不希望每天在逛公園這件事上花費太多的時間。如果1號點到?號點的最短路長為？那么策策只會喜歡長度不超過 ?+ ?勺路線。策策同學想知道總共有多少條滿足條件的路線，你能幫幫他嗎？為防止輸出過大，答案對？取模。如果有無窮多條合法的路線，請輸出-1。【輸入格式】輸入文件名為。第一行包含一個整數 ？代表數據組數。接下來？組數據，對于每組數據：第

12、一行包含四個整數 ?, ?每兩個整數之間用一個空格隔開。接下來？?行，每行三個整數？?？代表編號為？?的點之間有一條權值為？勺有 向邊，每兩個整數之間用一個空格隔開。【輸出格式】輸出文件名為。輸出文件包含？行，每行一個整數代表答案。【輸入輸出樣例1】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見選手目錄下的 和。對于第一組數據，最短路為31 -5, 1 -2 -4 -5, 1 -2 -3 -5 為 3 條合法路徑。【輸入輸出樣例2】 見選手目錄下的和。【數據規模與約定】對于不同的測試點，我們約定各種參數的規模

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

14、easurephala nx可執行文件名cheesetreasurephala nx輸入文件名輸出文件名每個測試點時限1秒1秒2秒測試點數目102020每個測試點分值1055附加樣例文件有有有結果比擬方式全文比擬過濾行末空格及文末回車題目類型傳統傳統傳統運行內存上限256M256M512M.提交源程序文件名對于C+語言對于C語言對于 pascal語言三編譯命令不包含任何優化開關對于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+中函數 main()的返回值類型必須是int,程序正常結束時的返回值必須是0。3、 全國統一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor ,內存 4G,上述時限以此配置為準。4、只提供Linux格式附加樣例文件。5、提交的程序代碼文件的放置位置請參照各省的具體要求。6、 特別提醒：評測在當前最新

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

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

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

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

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

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

22、離的正整數，分別是由一條道路連接的兩個寶藏 屋的編號編號為1n，和這條道路的長度V。【輸出格式】輸出文件名為。輸出共一行，一個正整數，表示最小的總代價【輸入輸出樣例 1】4 51 2 11 3 31 4 12 3 43 4 14見選手目錄下的與【輸入輸出樣例1說明】小明選定讓贊助商打通了 1號寶藏屋。小明開發了道路12,挖掘了 2號寶藏。開發了道路1 4,挖掘了 4號寶藏。還開發了道路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見選手目錄下的與。【

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

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