小可可

?

更多企業學院：

中小企業管理全能版?183套講座+89700份資料

總經理、高層管理?49套講座+16388份資料

中層管理學院?46套講座+6020份資料

國學智慧、易經?46套講座

人力資源學院?56套講座+27123份資料

各階段員工培訓學院?77套講座+324份資料

員工管理企業學院?67套講座+8720份資料

工廠生產管理學院?52套講座+13920份資料

財務管理學院?53套講座+17945份資

料

銷售經理學院?56套講座+14350份資料

銷售人員培訓學院?72套講座+4879份資料

2021年安聯杯安徽省青少年信息學奧林匹克競賽

(jìngsài)

中學組試題(shìtí)

AOI2021

比賽(bǐsài)時間：2021年4月27日8:00至12:00

題目名稱搬磚頭尋寶回文串法杖復原

源文件名

/c//c//c/cp

p

/c/cpp

輸入文件名

輸出文件名

試題類型傳統型傳統型傳統型傳統型

總分值

1

是否有局部分否否否否

時限1秒1秒1秒1秒

考前須知(xūzhī)

1.務必看清題目，嚴格按照所要求的格式輸入(shūrù)、輸出。

2.在調試程序時請先使用題目中的例如數據，然后再自行設計多組測試數據

進行調試。

3.測試有嚴格的時間限制，請盡可能優化算法。

4.命名規那么：

(1)每題都規定了該題的英文名稱。

(2)程序文件和數據文件的主文件名都是該題的英文名字。

(3)程序文件擴展名采用語言環境的默認擴展名。

(4)數據文件都是文本文件，輸入和輸出文件的擴展名分別是.in和.out。

5.程序應從輸入文件讀取數據，并嚴格地按照規定的輸出格式將結果輸出到

輸出文件中。輸入數據文件和輸出數據文件都與程序在同一個目錄中，由

于程序所在目錄是不確定的，因此(yīncǐ)不允許在程序中含有盤符信息和

任何形式的路徑信息。

6.選手(xuǎnshǒu)在競賽結束時應在D盤根目錄下建立以參賽號命名的文件

夾，并將所完成各題的源程序文件放到該文件夾中。測試以評測系統編譯

的可執行文件為準，測試系統使用的是標準的編譯指令處理源程序，沒有

附加任何編譯選項，請選手按照考試機器上語言環境的默認配置來編譯調

試自己的程序。

題目(tímù)

1.搬磚頭(zhuāntóu)〔rock〕

小可可一直(yīzhí)對中國五千年的古老文明非常感興趣，學習歷史知識之

余，他報名參加了少年考古隊，跟隨正式的考古隊進行考古開掘(kāijué)，通過

實踐來更好的領會書本知識。這次考古隊發現了一個非常巨大的古墓，具有非

常高的考古價值，小可可隨隊來到了考古現場。經過(jīngguò)緊張的開掘，古

墓的墓道終于顯露出來，但是它被一塊塊方磚封住了，現在小可可的任務就是

幫助考古隊將這些方磚移走，打通墓道。由于這些保存完好的古代方磚也是珍

貴的文物，所以規定一次最多只能搬三塊磚。小可可在搬磚的過程中一直在思

考一個問題，他很想知道將這些磚頭搬走共有多少種不同的搬法。

例如，現在總共有4個磚頭，那么可以選擇的方法有以下7種：

1，1，1，1〔分4次搬完，每次搬一個磚頭〕

1，2，1〔分3次搬完，第一次搬一個，第二次搬兩個，第三次搬一個〕

1，1，2〔分3次搬完，第一次搬一個，第二次搬一個，第三次搬兩個〕

2，1，1〔分3次搬完，第一次搬兩個，第二次搬一個，第三次搬一個〕

2，2〔分2次搬完，第一次搬兩個，第二次搬兩個〕

1，3〔分2次搬完，第一次搬一個，第二次搬三個〕

3，1〔分2次搬完，第一次搬三個，第二次搬一個〕

你能不能幫助小可可解決這個問題呢？

輸入：共一行。是一個1～1000的正整數N，表示共有Ｎ塊磚頭。

輸出：共一行。輸出一個正整數表示N塊磚頭移動的方法數。

樣例：

輸入(shūrù)：〔〕

4

輸出(shūchū)：〔〕

7

2.尋寶〔truesure〕

經過辛勤(xīnqín)的工作，墓道終于清理干凈，小可可隨考古隊進入了墓

室，在墓室的入口處，小可可發現了一張古代(gǔdài)的壁畫，這幅壁畫清楚的

描繪了古墓的平面布局，原來這個古墓有N個墓室(mùshì)，M個雙向墓道，每

條墓道連接兩個不同的墓室,兩個墓室之間可能有多條墓道相連，且每條墓道上

都可能會有機關。入口墓室標號為1號，主墓室標號為N號，壁畫上同時標明

了整個古墓內總共有K種機關，并且知道每種機關在每條道路上出現的概率，

并且告知了這些機關都可以用一些工具破壞掉，工具也共有K種，第i(1≤i≤K)

種寶劍能且只能破壞第i種機關。每個墓室里都可能有一些這樣的工具，包括

１號墓室〔假設墓室里有的工具數量都為無限多，想拿多少就拿多少〕。如果

小可可在某條墓道上遇到某種機關，他又沒有能破壞這種機關的專用工具，那

他將可能會受傷，不能到達N號墓室了。現在小可可一種工具也沒有沒有，但

他有足夠的力氣來帶任意多的工具，他想知道的是能成功到達N號墓室〔即主

墓室〕的最大概率是多少。

輸入：第一行有三個正整數N,M,K分別用一個空格分開，意義如上所述。接下

來M行,每行有P+2個正整數，分別是U,V,p1,

p

2

,…,p

K

,分別用一個空格分

開，表示有一條墓道連接U,V(U≠V)兩個墓室，這條道路上第i(1≤i≤K)種

機關出現概率為pi

%,保證0≤p

i

≤100，且p

1

+p

2

+…+p

K

≤100.

接下來N行，按順序分別描述(miáoshù)1~N號墓室中保有工具的情

況，每行K個整數(zhěngshù)t1

,t

2

,…,t

K

，分別(fēnbié)用一個空格隔開,其

中ti

(1≤i≤K)為1表示(biǎoshì)該墓室(mùshì)內有能破壞第i種機關的工

具，否那么ti

必為0表示該墓室內沒有能破壞第i種機關的工具。

輸出：只輸出一個實數表示小可可能成功到達N號墓室〔即主墓室〕的最大概

率，四舍五入到小數點后3位.

樣例：

輸入：〔〕

563

121000

130200

140030

2590100

3510900

4501090

000

100

010

001

111

輸出：〔〕

提示：對40%的數據，N≤10,M≤100,P≤4

對100%的數據，N≤500,M≤1000,P≤10.

3.回文串〔plalindrome〕

經歷了種種機關的考驗，小可可終于來到了主墓室，他發現主墓室墻上還

有個非常復雜的機關，組成墓室墻壁的方磚上，均刻有由古代字符和數字組成

的圖案，每塊方磚上一組。小可可發現這些古代字符恰好有二十六種，可以用

小寫英文字母(‘a’~‘z’)來代替他們，而數字可以用(‘0’~‘9’)代替。經過細致的研

究，小可可驚奇的發現這些圖案中有一些居然是壓縮過的回文串。所謂回文

串，就是從左向右讀與從右向左讀都一樣的字符串，比方〞abcba〞是回文串，

而〞abcbb〞不是回文串。而壓縮過的回文串，就是對串中連續重復出現p次的

子串A,即〞AA…A〞(共p次),可以替換為〞(A)p〞。比方〞aababababababb〞可

以替換為〞a(ab)3(ab)3b〞(當然也可替換為〞a(ab)6b〞),這樣的壓縮方法可以使

用屢次，也就是說括號是可以嵌套的，比方〞a(ab)3(ab)3b〞可以進一步壓縮

為〞a((ab)3)2b〞。只要找出哪些方磚上刻的是回文串，并按動這些方磚，那么

將會開啟存有寶藏的密室。現在請你幫助小可可來完成這個艱巨的任務吧。

輸入(shūrù)：第一行只有(zhǐyǒu)一個正整數T,T行，每行一個(yīɡè)待判斷的

用壓縮方式表示的字符串，字符串只含有小寫英文字母(‘a’~‘z’)與括號

(‘(’,‘)’),數字(‘0’~‘9’),注意解壓縮后的原串只含小寫英文字母，也就是說

括號與數字都是壓縮產生的。輸入數據保證所有數不超過109.保證

(bǎozhèng)輸入文件不含多余空格。

輸出(shūchū)：共T行，如果輸入文件中第i個串是回文串，那么輸出〞Yes〞

(不含雙引號),否那么輸出〞No〞(不含雙引號).

樣例：

輸入：()

5

a((ab)5)2b

(abb)5(bba)5

((ab)5(c)5(ba)5(asdodsfklj)0)8

((((a)10)1)10000000

((abcd)100000(dcba)99999)1

輸出(shūchū)：()

No

Yes

Yes

Yes

No

樣例說明(shuōmíng)：

第二個串展開(zhǎnkāi)后為〞abbabbabbabbabbbbabbabbabbabba〞是回文(huí

wén)串

第三個串要注意(zhùyì)〞(A)0〞這種表示方式也是合法的.

第四個串說明在輸入串長度允許的范圍內，解壓縮后的原串可能會很長.

提示：

對30%的數據，每個輸入串解壓縮后的長度不超過200000。

對100%的數據，T≤20,每個輸入串長度不超過300,所有壓縮后緊跟在括

號后的數(也即重復次數)不超過109,解壓縮后串的長度可能超過長整形

(PASCAL中int64,C++中longlong)能表示的最大整數.

4.法杖復原〔restore〕

小可可解開了最后一個機關后，終于開啟了密室。考古隊驚奇的發現密室

里面保存了各種各樣的稀世珍寶，有好多都是考古史上從來沒有發現過的，具

有極高的研究價值。但是由于年代過于久遠或者別的原因，有些文物已經損

壞。小可可發現一個盒子里有一些水晶做的棍子，考古隊員告訴他這些棍子是

古代宗教活動中使用的法杖，每個都是一樣的長度，非常珍貴。但是這些水晶

法杖都已經斷裂，最長的都不超過50cm了。小可可想如果能把這些法杖都恢

復到原狀那有多好啊！但是由于斷裂后的法杖都混在一起，小可可根本就無法

知道原來究竟有多少根法杖及這些法杖原來的長度是多少。為了盡可能簡化工

作，考古隊決定按照這些法杖原來長度的最小值進行恢復，作為這次考古旅程

的最后一項工作，你能幫助小可可對法杖進行復原嗎？

輸入(shūrù)：共兩行(liǎnɡxínɡ)。第一為一個整數N，表示(biǎoshì)斷裂(duàn

liè)后法杖的個數，并且這個(zhège)數字不大于64。第二行共N個整

數，代表斷裂后法杖的具體長度。

輸出：共一行。表示原來法杖的最小長度。這里假設所有法杖的長度均為大于

0的整數。

樣例：

輸入：()

9

521521521

輸出：()

6

我高二。230*75%+255*25%最后一名進安徽省隊。

去年NOI和今年WC的所有同伴，除了那名女選手，全軍覆沒。

我的運氣比他們好了一點點，剛好沒有成為制度犧牲品。

對于試題我可以講的詳細點。不僅題目悲劇，數據才更“神奇〞，我只能用“神

奇〞來形容這些題目的數據了。

第一題赤裸裸的高精度加法，F[I]=F[I-1]+F[I-2]+F[I-3]，N<=1000；

題目已經夠簡單了，可數據才更讓人驚奇，事實證明：

只需要使用int64或者longlong就可以得到總分值，換句話說實際的數據中

N<100。

第二題簡單的SPFA+狀態壓縮即可。但題意確是如此的模糊不清，直接導致了

無數本該總分值的人得了0分，其中也包括本人。無疑，此題對于高中和初中

的同學們應該會有較好的區分度，因為去年聯賽高中組剛剛考了一道類似的題

目。至關重要的一題，就因為題意表達不清而pass了。我相信把這一題的題目

意思表達的稍微明確一點，那么省隊名單就會有很大的變動。又或者這道題是

成心忽悠人的？除了“機關是否唯一〞這點沒有表達清楚外，其中“第一行

N,M,K……接下來M行，每行P(實際上是K)+2個正整數……〞可緊接著里面

又出現了0，我不認為這種低級錯誤該出現在AHOI的比賽中。

第三題，壓縮字符串，判斷回文。此題貌似是這次比賽最難的一題，我知道的

只有一人得了總分值〔合肥高中組的，本以為他這次穩拿第一了，最后連前九

都沒有進〕。想到HASH了，這題就不難了，可是…………反正我是沒想到。

根本沒人做出來這題，所以區分度什么的就不用提了，此題再次pass。

第四題，數學題？搜索題？裸搜就能過。我DFS+弱弱的背包剪枝過了。〔我

自己測時有數據過不了的〕

真的是夠神奇的數據，事實證明：

一個錯誤的，十來行的貪心算法都能得到總分值。

今年安徽團隊鐵定是沒戲了，前五名算團隊分數，只有女選手是高中生……

安徽省選就是一場鬧劇。

安徽省選今天結束。我來說說情況

安徽一開始就定了政策，說NOIP成績算省選25%的分，而NOIP初高中試卷

不同，初中組就平均分都比高中組高100分，最高分380，高中組NOIP最高才

250左右。各市領隊紛紛提意見都沒用，組委會那些人一直說題難就能拉開初

高中差距。后來(hòulái)NOI政策下來，說安徽省隊擴名額到9人，大家也就作

罷。

結果今天考完才明白這安徽省選就跟沒選一樣。

總共四題：

第一題是弱DP，放NOIP里都算簡單題。

第三題是一個判斷回文串的題，全場貌似就一人hash過了，其他幾乎全暴零。

第四題用最樸素的搜索就80，加點背包優化就AC。

由此看出，第1,3,4完全是無區分度的題，那第二題呢：歧義題。說一個路上有

多少概率有機關什么什么的。題目表述有問題，先說機關是獨立的，又給了個

莫名其妙的式子，后來才知道因為機關其實不是獨立的那個式子才有意義。導

致安徽的那些高手，參加過以往的好幾屆NOI，冬令營，國家隊選拔，拿過牌

等等的選手全暴零，這題AC的人都覺得自己理解錯。搞得往屆省隊的那些人

都去找組委會理論，當然完全沒有得到什么滿意的答復(dáfù)。

134完全沒區分度，2歧義，AHOI這四題就跟沒考一樣，安徽省隊就完全是在

按NOIP成績來選。NOIP那個難度水平和NOI的差距，就不用說了。。以

NOIP的難度來選拔，太失敗了。

九人(jiǔrén)的省隊，六人是初中的。高中三人一個是必須的女生，另兩人一高

一，一高二當然是NOIP都考得比擬(bǐnǐ)好。安徽省隊就去NOI丟人現眼

吧。。看那幾個只能做NOIP難度的初中生能考出什么好成績。

估計安徽拿金銀銅沒希望了，能拿到不少(bùshǎo)"年齡最小的參賽選手"獎

大家來看看神奇的

AHOI2021〔附試題〕

這次AHOI2021是歷屆來最神奇的AHOI

考試由原來的兩試，一試3題3小時改為一試4題4小時

選拔省隊時noip成績占1/4〔noip成績*1/4+省賽成績*3/4〕

普及組提高組統一計算〔就是說，普及組起始分數會比提高組普遍高〕

第一題，遞推+高精(裸的)

第二題，狀態壓縮的spfa〔裸的，聽說分層什么的也都能過〕

第三題，壓縮字符串的回文判定，比擬rp，貌似是兩遍hash，大家普遍暴力30

〔wtj神牛AC〕

第四題，搜索+垃圾剪枝〔裸的〕

正當大家以為普遍330時，下午發下來的成績是普遍230。。

第二題，題目明顯是每條路的機關互不相關，但是標程是每條路只可能有一個

機關

p1+p2+…+pK

≤100

只有這一句貌似有這方面的暗示。

LLL與另一位語文神牛AC，其余普遍0

zouxun神牛200，本菜與幾位大蝦并列230。

wtj神牛，第一題測試系統錯誤〔他手測、用cena測皆AC〕0分，第二題，和

眾人一起0分，于是悲劇的拿了200。

LLL330第一名，另有一300，初中有一270。

省隊9個，LLL，語文神牛，XJY〔去年加試由于時間被淘汰出省隊的那位大

蝦，本次230，由于noip255分，搭上末班車〕

其余6位皆為初中。

wtj神牛討要說法未果，關于noip的問題幾個月前老師們都提過，一直未果，

現在說規那么定了就無法改變，而且說“這是的問題是經驗，下次就不會有了〞

其余的都不說了，大家自己看看題目吧，看看今年noi2021安徽省初中神牛們

的神奇表現。

小學組的題目也順便附上〔我還沒看。。不過好似有4個總分值〕

內容總結

（1）2021年安聯杯安徽省青少年信息學奧林匹克競賽

中學組試題

AOI2021

比賽時間：2021年4月27日8:00至12:00

考前須知

務必看清題目，嚴格按照所要求的格式輸入、輸出

（2）命名規那么：

(1)每題都規定了該題的英文名稱

（3）(3)程序文件擴展名采用語言環境的默認擴展名

（4）(4)數據文件都是文本文件，輸入和輸出文件的擴展名分別是.in

和.out