第42屆信息學(xué)奧林匹克競賽NOI2025第一天試題

2025-07-15 16:36|編輯: 常老師|閱讀: 711

摘要

第42屆全國青少年信息學(xué)奧林匹克競賽（CCF NOI2025）于2025年7月12日-18日在浙江紹興舉行。本文整理了第42屆信息學(xué)奧林匹克競賽NOI2025第一天試題，供考生參考。

由CCF主辦、紹興市第一中學(xué)承辦的第42屆全國青少年信息學(xué)奧林匹克競賽（CCF NOI2025）將于2025年7月12日-18日在浙江紹興舉行。本文整理了第42屆信息學(xué)奧林匹克競賽NOI2025第一天試題，供考生參考。

免費(fèi)福利：

為了方便考生更好備考五大學(xué)科競賽，北京高考在線團(tuán)隊(duì)為大家整理了

《高中五大學(xué)科競賽規(guī)劃備考全攻略》電子版資料

http://www.lasepton.cn/form?xyppid=558524326727388226

《近十年高中競賽試題集》電子版資料，可以直接打印練習(xí)！

免費(fèi)領(lǐng)?。?a href="http://www.lasepton.cn/form?xyppid=558532509428616258" target="_blank" rel="noopener">http://www.lasepton.cn/form?xyppid=558532509428616258

為了幫助同學(xué)們備考，北京高考在線團(tuán)隊(duì)為大家準(zhǔn)備了五大學(xué)科競賽交流分享群，

掃描下方二維碼進(jìn)群??

第42屆信息學(xué)奧林匹克競賽NOI2025第一天試題

PART.01 [NOI 2025] 機(jī)器人

題目描述

NOI2025 正在紹興舉辦，小 Y 為閉幕式表演制作了一個機(jī)器人并打算操控它從倉庫走到禮堂。

紹興的道路系統(tǒng)可以簡化為n個路口以及連接這些路口的m條單行道路，且每條道路有一定的長度。為了方便將道路系統(tǒng)錄入機(jī)器人的芯片，小 Y 對每一個路口連接的所有道路進(jìn)行了編號。具體而言，若有d條道路以路口x為起點(diǎn)，則這d條道路會被小 Y 按照某種順序編號為1∼d，分別稱作以x為起點(diǎn)的第1∼d條道路。

小 Y 的機(jī)器人內(nèi)部有一個參數(shù)p。給定參數(shù)p的上限k與修改費(fèi)用v1?,v2?,…,vk−1?,w2?,w3?,…,wk?。小 Y 將按照如下規(guī)則設(shè)置與修改機(jī)器人的參數(shù)：

初始時(shí)，小 Y 將參數(shù)p設(shè)置為1。
在任意時(shí)刻，小 Y 可以遠(yuǎn)程控制機(jī)器人修改參數(shù)：
- 若p<k，則小 Y 可以花費(fèi)vp?的費(fèi)用將p增加1，即p←p+1；
- 若p>1，則小 Y 可以花費(fèi)wp?的費(fèi)用將p減少1，即p←p−1。

初始時(shí)，小 Y 的機(jī)器人位于機(jī)器人倉庫，即路口1。當(dāng)機(jī)器人位于路口x時(shí)，記以路口x為起點(diǎn)的第p條道路的終點(diǎn)為y，道路長度為z，則小 Y 可以花費(fèi)z的費(fèi)用操控機(jī)器人從x走到y(tǒng)。特別地，若以路口x為起點(diǎn)的道路不足p條，則小 Y 無法操控機(jī)器人走動。

小 Y 并不知道閉幕式表演所在的禮堂位于哪個路口，因此他需要對每個路口都做好準(zhǔn)備。請你幫助他求出將機(jī)器人從倉庫移動到每個路口所需費(fèi)用的最小值。

輸入格式

輸入的第一行包含一個非負(fù)整數(shù)c，表示測試點(diǎn)編號。c=0表示該測試點(diǎn)為樣例。

輸入的第二行包含三個正整數(shù)n,m,k，分別表示路口數(shù)量、道路數(shù)量與參數(shù)p的上限。

輸入的第三行包含k−1個非負(fù)整數(shù)v1?,…,vk−1?，表示增加參數(shù)p的費(fèi)用。

輸入的第四行包含k−1個非負(fù)整數(shù)w2?,…,wk?，表示減少參數(shù)p的費(fèi)用。

輸入的第i+4（1≤i≤n）行包含若干個正整數(shù)，其中第一個非負(fù)整數(shù)di?表示以路口i為起點(diǎn)的道路數(shù)量，接下來2di?個正整數(shù)yi,1?,zi,1?,yi,2?,zi,2?,…,yi,di??,zi,di??，表示以路口i為起點(diǎn)的道路，其中yi,j?,zi,j?（1≤j≤di?）分別表示編號為j的道路的終點(diǎn)與長度。

輸出格式

輸出一行n個整數(shù)，其中第i（1≤i≤n）個數(shù)表示小 Y 將機(jī)器人從倉庫移動到路口i所需費(fèi)用的最小值。特別地，若小 Y 無法將機(jī)器人從倉庫移動到該路口，則輸出−1。

輸入輸出樣例

說明/提示

樣例 1 解釋

小 Y 可以按照以下方案將機(jī)器人分別從倉庫移動到路口1∼4：

對于路口1：小 Y 的機(jī)器人初始時(shí)即位于路口1，因此所需費(fèi)用為0。
對于路口2：小 Y 操控機(jī)器人沿以路口1為起點(diǎn)的第1條道路走到路口2，所需費(fèi)用為5。
對于路口3：小 Y 將參數(shù)p增加1，然后操控機(jī)器人沿以路口1為起點(diǎn)的第2條道路走到路口3，所需費(fèi)用為2+1=3。
對于路口4：小 Y 將參數(shù)p增加1，然后操控機(jī)器人沿以路口1為起點(diǎn)的第2條道路走到路口3，再操控機(jī)器人沿以路口3為起點(diǎn)的第2條道路走到路口4，所需費(fèi)用為2+1+1=4。

可以證明，上述移動方案的所需費(fèi)用均為最小值。

對于路口5：由于小 Y 無法將機(jī)器人移動到路口5，因此輸出−1。

樣例 2

見選手目錄下的robot/robot2.in與robot/robot2.ans。

該樣例滿足測試點(diǎn)3∼5的約束條件。

樣例 3

見選手目錄下的robot/robot3.in與robot/robot3.ans。

該樣例滿足測試點(diǎn)6∼8的約束條件。

樣例 4

見選手目錄下的robot/robot4.in與robot/robot4.ans。

該樣例滿足測試點(diǎn)9,10的約束條件。

樣例 5

見選手目錄下的robot/robot5.in與robot/robot5.ans。

該樣例滿足測試點(diǎn)16∼18的約束條件。

數(shù)據(jù)范圍

對于所有測試數(shù)據(jù)，保證：

1≤n,m≤3×105，1≤k≤2.5×105；
對于所有1≤i≤k−1，均有0≤vi?≤109；
對于所有2≤i≤k，均有0≤wi?≤109；
對于所有1≤i≤n，均有0≤di?≤k，且∑i=1n?di?=m；
對于所有1≤i≤n，1≤j≤di?，均有1≤yi,j?≤n，1≤zi,j?≤109。

測試點(diǎn)編號	n,m≤	k≤	特殊性質(zhì)
1,2	6	6	C
3∼5	103	103	C
6∼8	5×104	102	無
9,10	105	105	AB
11,12	105	105	A
13∼15	105	105	C
16∼18	105	105	無
19,20	3×105	2.5×105	無

特殊性質(zhì) A：保證v1?=v2?=?=vk−1?=0且w2?=w3?=?=wk?=0。
特殊性質(zhì) B：保證對于所有1≤i≤n，1≤j≤di?，均有zi,j?=1。

特殊性質(zhì) C：保證至多存在 10 個i滿足di?≥10。

PART.02[NOI 2025]序列變換

給定兩個長度為n的整數(shù)序列B=[b1?,…,bn?]，C=[c1?,…,cn?]。對于長度為n的非負(fù)整數(shù)序列D=[d1?,…,dn?]，設(shè)S(D)為所有滿足di?=0的下標(biāo)i的集合，定義f(D)=∑i∈S(D)?bi?，g(D)=∏i∈S(D)?ci?。特別地，若S(D)為空，則f(D)=0，g(D)=1。

小 L 有一個長度為n的正整數(shù)序列A=[a1?,…,an?]。小 L 可以對序列A做如下修改：

選擇序列A的兩個相鄰的下標(biāo)i,j（即1≤i,j≤n且∣i−j∣=1），若ai?≤aj?，則將aj?改為aj?−ai?，同時(shí)將ai?改為0。

小 L 可以進(jìn)行任意多次修改操作，也可以不進(jìn)行任何修改。對于所有序列A通過以上修改操作可以得到的序列D，小 L 想求出f(D)的最大值以及g(D)之和，請你幫助他求出這兩個值。形式化地，記T(A)為序列A通過以上修改操作可以得到的所有序列的集合，你需要求出maxD∈T(A)?f(D)以及∑D∈T(A)?g(D)。其中，由于∑D∈T(A)?g(D)可能較大，你只需要求出其對1,000,000,007取模后的結(jié)果。

輸入格式

本題包含多組測試數(shù)據(jù)。

輸入的第一行包含兩個非負(fù)整數(shù)c,t，分別表示測試點(diǎn)編號與測試數(shù)據(jù)組數(shù)。c=0表示該測試點(diǎn)為樣例。

接下來依次輸入每組測試數(shù)據(jù)，對于每組測試數(shù)據(jù)：

第一行包含一個正整數(shù)n，表示序列長度。
第二行包含n個正整數(shù)a1?,…,an?，表示序列A。
第三行包含n個整數(shù)b1?,…,bn?，表示序列B。
第四行包含n個正整數(shù)c1?,…,cn?，表示序列C。

輸出格式

對于每組測試數(shù)據(jù)，僅輸出一行，其中包含兩個整數(shù)，分別表示maxD∈T(A)?f(D)以及∑D∈T(A)?g(D)對1,000,000,007取模后的結(jié)果。注意：maxD∈T(A)?f(D)不需要對1,000,000,007取模。

本題包含兩個小問，正確回答其中任意一個小問均可獲得部分分?jǐn)?shù)。具體評分規(guī)則請參見【評分方式】。

輸入輸出樣例

說明/提示

樣例 1 解釋

該樣例共包含三組測試數(shù)據(jù)。

對于第一組測試數(shù)據(jù)，可以得到以下 4 個序列：

D=[5,6,6]，f(D)=0，g(D)=1；
D=[0,1,6]，f(D)=3，g(D)=1；
D=[5,0,0]，f(D)=6+9=15，g(D)=2×3=6；
D=[0,0,5]，f(D)=3+6=9，g(D)=1×2=2。

故maxD∈T(A)?f(D)=max{0,3,15,9}=15，∑D∈T(A)?g(D)=1+1+6+2=10。

樣例 2

見選手目錄下的sequence/sequence2.in與sequence/sequence2.ans。

該樣例滿足測試點(diǎn) 3、4 的約束條件。

樣例 3

見選手目錄下的sequence/sequence3.in與sequence/sequence3.ans。

該樣例滿足測試點(diǎn) 5、6 的約束條件。

樣例 4

見選手目錄下的sequence/sequence4.in與sequence/sequence4.ans。

該樣例滿足測試點(diǎn) 7 的約束條件。

樣例 5

見選手目錄下的sequence/sequence5.in與sequence/sequence5.ans。

該樣例滿足測試點(diǎn) 11、12 的約束條件。

樣例 6

見選手目錄下的sequence/sequence6.in與sequence/sequence6.ans。

該樣例滿足測試點(diǎn)16∼18的約束條件。

設(shè)N為單個測試點(diǎn)內(nèi)所有測試數(shù)據(jù)的n的和。對于所有測試數(shù)據(jù)，保證：

1≤t≤20；
1≤n≤5,000，N≤4×104；
對于所有1≤i≤n，均有1≤Ai?≤109；
對于所有1≤i≤n，均有−109≤Bi?≤109；
對于所有1≤i≤n，均有1≤Ci?≤109。

測試點(diǎn)編號	n≤	N≤	特殊性質(zhì)
1,2	8	102	無
3,4	200	400	B
5,6	200	400	無
7	500	103	A
8∼10	500	103	B
11,12	500	103	無
13	3500	3×104	A
14,15	3500	3×104	B
16∼18	3500	4×104	無
19,20	5000	4×104	無

特殊性質(zhì) A：保證A1?=A2?=?=An?=1。
特殊性質(zhì) B：保證對于所有1≤i≤n，Ai?均在[1,109]中獨(dú)立均勻隨機(jī)生成。

評分方式

對于每個測試點(diǎn)：

正確回答所有測試數(shù)據(jù)的maxD∈T(A)?f(D)，可獲得該測試點(diǎn)40%的分?jǐn)?shù)；
正確回答所有測試數(shù)據(jù)的∑D∈T(A)?g(D)對1,000,000,007取模后的結(jié)果，可獲得該測試點(diǎn)60%的分?jǐn)?shù)。

注意：即使選手僅回答了其中一個問題，也需要按照輸出格式輸出兩個整數(shù)，分別對應(yīng)兩個問題的答案。

PART.03[NOI 2025] 數(shù)字樹

給定一棵4n−1個結(jié)點(diǎn)的二叉樹，其中每個非葉結(jié)點(diǎn)都有恰好兩個子結(jié)點(diǎn)。非葉結(jié)點(diǎn)編號為1到2n−1，葉子結(jié)點(diǎn)編號為2n到4n−1。初始時(shí)，每個葉子結(jié)點(diǎn)上都沒有數(shù)字。

定義一個 DFS 序是優(yōu)美的，當(dāng)且僅當(dāng)按該 DFS 序?qū)⑺袠?biāo)有數(shù)字的葉子結(jié)點(diǎn)上的數(shù)字拼成一個序列時(shí)，該序列可以通過若干次消除相鄰相同數(shù)字的方式得到空序列。例如，在下圖中，若葉子結(jié)點(diǎn)4,6上標(biāo)有數(shù)字1，葉子結(jié)點(diǎn)5,7上標(biāo)有數(shù)字2，則按 DFS 序[1,4,2,7,3,5,6]將所有標(biāo)有數(shù)字的葉子結(jié)點(diǎn)上的數(shù)字拼成的序列為[1,2,2,1]，可以通過消除相鄰的2的方式得到[1,1]，再通過消除相鄰的1的方式得到空序列，因此該 DFS 序是優(yōu)美的；而按 DFS 序[1,4,2,3,5,6,7]將所有標(biāo)有數(shù)字的葉子結(jié)點(diǎn)上的數(shù)字拼成的序列為[1,2,1,2]，無法通過若干次消除相鄰相同數(shù)字的方式得到空序列，因此該 DFS 序不是優(yōu)美的。

給定n次操作，第i(1≤i≤n) 次操作會選擇兩個沒有數(shù)字的葉子結(jié)點(diǎn)，然后將這兩個結(jié)點(diǎn)標(biāo)上數(shù)字i。保證在每次操作后，存在至少一個優(yōu)美的 DFS 序。你需要求出每次操作后的優(yōu)美的 DFS 序的數(shù)量。由于答案可能較大，你只需要求出答案對1,000,000,007取模后的結(jié)果。

輸入格式

輸入的第一行包含一個非負(fù)整數(shù)c，表示測試點(diǎn)編號。c=0表示該測試點(diǎn)為樣例。

輸入的第二行包含一個正整數(shù)n，表示二叉樹的結(jié)點(diǎn)個數(shù)為4n−1。

輸入的第i+2(1≤i≤2n−1) 行包含兩個正整數(shù)li?和ri?，分別表示結(jié)點(diǎn)i的左右子結(jié)點(diǎn)。保證i<li?,ri?≤4n−1，且所有的li?,ri?互不相同。

輸入的第i+2n−1(1≤i≤n) 行包含兩個正整數(shù)ai?,bi?，表示第i次操作選擇的葉子結(jié)點(diǎn)的編號。保證2n≤ai?,bi?≤4n−1，且所有的ai?,bi?互不相同。

輸出格式

輸出n行，其中第i(1≤i≤n) 行包含一個非負(fù)整數(shù)，表示第i次操作后的優(yōu)美的 DFS 序的數(shù)量對1,000,000,007取模后的結(jié)果。

輸入輸出樣例

說明/提示

樣例 1 解釋

該樣例即【題目描述】中所示的例子。

第一次操作后，葉子結(jié)點(diǎn)4和6上標(biāo)有數(shù)字1，葉子結(jié)點(diǎn)5和7上沒有數(shù)字，因此按任意 DFS 序拼成的序列均為[1,1]，即所有的23=8個 DFS 序都是優(yōu)美的。
第二次操作后，葉子結(jié)點(diǎn)4∼7上分別標(biāo)有數(shù)字1,2,1,2，因此共有4個優(yōu)美的 DFS 序，分別為[1,4,2,3,6,5,7],[1,4,2,7,3,5,6],[1,2,3,6,5,7,4],[1,2,7,3,5,6,4]。