2023年安徽省青少年信息學(xué)奧林匹克競(jìng)賽中學(xué)組試題

更多公司學(xué)院:《中小公司管理全能版》１8３套講座+8９700份資料《總經(jīng)理、高層管理》４9套講座+16388份資料《中層管理學(xué)院》46套講座+６020份資料

《國學(xué)智慧、易經(jīng)》４6套講座《人力資源學(xué)院》５６套講座+27123份資料《各階段員工培訓(xùn)學(xué)院》77套講座+３24份資料《員工管理公司學(xué)院》67套講座+8720份資料《工廠生產(chǎn)管理學(xué)院》52套講座+１3９20份資料《財(cái)務(wù)管理學(xué)院》５3套講座+179４5份資料

《銷售經(jīng)理學(xué)院》５6套講座+１4350份資料《銷售人員培訓(xùn)學(xué)院》７2套講座+48７9份資料202３年安聯(lián)杯安徽省青少年信息學(xué)奧林匹克競(jìng)賽中學(xué)組試題AOI202３比賽時(shí)間:20２3年4月27日８：00至12:0０題目名稱搬磚頭尋寶回文串法杖還原源文獻(xiàn)名roｃk.pas/c／ｃｐptruesｕｒｅ.pａs/c／cpｐplaｌｉｎdrome.pas／c/cpprestore.ｐaｓ/c／ｃpp輸入文獻(xiàn)名rock.ｉntruｅsurｅ.ｉnplalｉndrｏｍe.iｎrｅｓtoｒe．iｎ輸出文獻(xiàn)名ｒock．ouｔｔrueｓure.ouｔpｌaｌindｒｏｍｅ.oｕtrｅstore.ｏｕt試題類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型滿分1０01００100100是否有部分分否否否否時(shí)限１秒1秒1秒1秒注意事項(xiàng)務(wù)必看清題目，嚴(yán)格按照所規(guī)定的格式輸入、輸出。在調(diào)試程序時(shí)請(qǐng)先使用題目中的示例數(shù)據(jù)，然后再自行設(shè)計(jì)多組測(cè)試數(shù)據(jù)進(jìn)行調(diào)試。測(cè)試有嚴(yán)格的時(shí)間限制,請(qǐng)盡也許優(yōu)化算法。命名規(guī)則：

(１)每題都規(guī)定了該題的英文名稱。

（２）程序文獻(xiàn)和數(shù)據(jù)文獻(xiàn)的主文獻(xiàn)名都是該題的英文名字。

(3）程序文獻(xiàn)擴(kuò)展名采用語言環(huán)境的默認(rèn)擴(kuò)展名。

(4）數(shù)據(jù)文獻(xiàn)都是文本文獻(xiàn)，輸入和輸出文獻(xiàn)的擴(kuò)展名分別是.in和.oｕt。程序應(yīng)從輸入文獻(xiàn)讀取數(shù)據(jù),并嚴(yán)格地按照規(guī)定的輸出格式將結(jié)果輸出到輸出文獻(xiàn)中。輸入數(shù)據(jù)文獻(xiàn)和輸出數(shù)據(jù)文獻(xiàn)都與程序在同一個(gè)目錄中，由于程序所在目錄是不擬定的，因此不允許在程序中具有盤符信息和任何形式的途徑信息。選手在競(jìng)賽結(jié)束時(shí)應(yīng)在D盤根目錄下建立以參賽號(hào)命名的文獻(xiàn)夾,并將所完畢各題的源程序文獻(xiàn)放到該文獻(xiàn)夾中。測(cè)試以評(píng)測(cè)系統(tǒng)編譯的可執(zhí)行文獻(xiàn)為準(zhǔn)，測(cè)試系統(tǒng)使用的是標(biāo)準(zhǔn)的編譯指令解決源程序,沒有附加任何編譯選項(xiàng)，請(qǐng)選手按照考試機(jī)器上語言環(huán)境的默認(rèn)配置來編譯調(diào)試自己的程序。題目搬磚頭(rock)小可可一直對(duì)中國五千年的古老文明非常感愛好，學(xué)習(xí)歷史知識(shí)之余，他報(bào)名參與了少年考古隊(duì),跟隨正式的考古隊(duì)進(jìn)行考古發(fā)掘，通過實(shí)踐來更好的領(lǐng)略書本知識(shí)。這次考古隊(duì)發(fā)現(xiàn)了一個(gè)非常巨大的古墓，具有非常高的考古價(jià)值,小可可隨隊(duì)來到了考古現(xiàn)場(chǎng)。通過緊張的發(fā)掘,古墓的墓道終于顯露出來,但是它被一塊塊方磚封住了，現(xiàn)在小可可的任務(wù)就是幫助考古隊(duì)將這些方磚移走,打通墓道。由于這些保存完好的古代方磚也是珍貴的文物,所以規(guī)定一次最多只能搬三塊磚。小可可在搬磚的過程中一直在思考一個(gè)問題,他很想知道將這些磚頭搬走共有多少種不同的搬法。例如,現(xiàn)在總共有4個(gè)磚頭,那么可以選擇的方法有以下7種：1,1，1，1（分4次搬完，每次搬一個(gè)磚頭)1,2,1（分3次搬完，第一次搬一個(gè)，第二次搬兩個(gè),第三次搬一個(gè)）1,1,2(分3次搬完，第一次搬一個(gè),第二次搬一個(gè)，第三次搬兩個(gè))2，1，1（分3次搬完,第一次搬兩個(gè),第二次搬一個(gè),第三次搬一個(gè))2,２（分2次搬完，第一次搬兩個(gè)，第二次搬兩個(gè))１，3(分2次搬完,第一次搬一個(gè),第二次搬三個(gè))3,1(分2次搬完，第一次搬三個(gè)，第二次搬一個(gè))你能不能幫助小可可解決這個(gè)問題呢?輸入：共一行。是一個(gè)1~1００0的正整數(shù)Ｎ,表達(dá)共有Ｎ塊磚頭。輸出:共一行。輸出一個(gè)正整數(shù)表達(dá)N塊磚頭移動(dòng)的方法數(shù)。樣例：輸入：（rocｋ.in)4輸出：（rocｋ.ouｔ）7尋寶（truｅｓuｒe)通過辛勤的工作,墓道終于清理干凈，小可可隨考古隊(duì)進(jìn)入了墓室，在墓室的入口處,小可可發(fā)現(xiàn)了一張古代的壁畫,這幅壁畫清楚的描繪了古墓的平面布局,本來這個(gè)古墓有N個(gè)墓室,M個(gè)雙向墓道，每條墓道連接兩個(gè)不同的墓室,兩個(gè)墓室之間也許有多條墓道相連，且每條墓道上都也許會(huì)有機(jī)關(guān)。入口墓室標(biāo)號(hào)為１號(hào),主墓室標(biāo)號(hào)為Ｎ號(hào),壁畫上同時(shí)標(biāo)明了整個(gè)古墓內(nèi)總共有K種機(jī)關(guān),并且知道每種機(jī)關(guān)在每條道路上出現(xiàn)的概率，并且告知了這些機(jī)關(guān)都可以用一些工具破壞掉,工具也共有Ｋ種,第ｉ(1≤i≤Ｋ)種寶劍能且只能破壞第i種機(jī)關(guān)。每個(gè)墓室里都也許有一些這樣的工具，涉及1號(hào)墓室(假設(shè)墓室里有的工具數(shù)量都為無限多,想拿多少就拿多少)。假如小可可在某條墓道上碰到某種機(jī)關(guān),他又沒有能破壞這種機(jī)關(guān)的專用工具，那他將也許會(huì)受傷，不能到達(dá)N號(hào)墓室了?，F(xiàn)在小可可一種工具也沒有沒有，但他有足夠的力氣來帶任意多的工具，他想知道的是能成功到達(dá)N號(hào)墓室（即主墓室)的最大約率是多少。輸入:第一行有三個(gè)正整數(shù)Ｎ,M,K分別用一個(gè)空格分開，意義如上所述。接下來M行，每行有Ｐ+2個(gè)正整數(shù),分別是U,Ｖ,p1,p2,…，ｐK，分別用一個(gè)空格分開,表達(dá)有一條墓道連接U,V(Ｕ≠Ｖ)兩個(gè)墓室，這條道路上第i(1≤i≤K)種機(jī)關(guān)出現(xiàn)概率為ｐｉ%,保證0≤pi≤10０,且p１+p2＋…+ｐＫ≤１0０.接下來Ｎ行，按順序分別描述1～N號(hào)墓室中保有工具的情況，每行K個(gè)整數(shù)ｔ1,t2,…,ｔK,分別用一個(gè)空格隔開,其中ｔi(1≤i≤Ｋ)為1表達(dá)該墓室內(nèi)有能破壞第i種機(jī)關(guān)的工具,否則ti必為０表達(dá)該墓室內(nèi)沒有能破壞第i種機(jī)關(guān)的工具。輸出：只輸出一個(gè)實(shí)數(shù)表達(dá)小可也許成功到達(dá)N號(hào)墓室（即主墓室)的最大約率，四舍五入到小數(shù)點(diǎn)后３位.樣例:輸入：(truesurｅ.iｎ）56３１2100013０200１4０030２590１0035１090０４５0109０000１00０1０0０1１１1輸出：(trｕeｓure.out）0.810提醒:對(duì)40%的數(shù)據(jù)，Ｎ≤10,M≤１0０,P≤4對(duì)10０%的數(shù)據(jù),N≤５0０,M≤1０00,P≤10.回文串（plalindｒｏme)經(jīng)歷了種種機(jī)關(guān)的考驗(yàn)，小可可終于來到了主墓室，他發(fā)現(xiàn)主墓室墻上尚有個(gè)非常復(fù)雜的機(jī)關(guān)，組成墓室墻壁的方磚上，均刻有由古代字符和數(shù)字組成的圖案,每塊方磚上一組。小可可發(fā)現(xiàn)這些古代字符恰好有二十六種,可以用小寫英文字母（‘a(chǎn)’~‘z’)來代替他們,而數(shù)字可以用(‘0’~‘９’)代替。通過細(xì)致的研究，小可可驚奇的發(fā)現(xiàn)這些圖案中有一些居然是壓縮過的回文串。所謂回文串,就是從左向右讀與從右向左讀都同樣的字符串,比如”ａbｃｂa”是回文串，而”abcｂb”不是回文串。而壓縮過的回文串,就是對(duì)串中連續(xù)反復(fù)出現(xiàn)p次的子串A,即”AA…Ａ”(共p次)，可以替換為”(Ａ）ｐ”。比如”aababａbaｂababb”可以替換為”a（aｂ)3(ab)3ｂ”(當(dāng)然也可替換為”a(ab)６ｂ”),這樣的壓縮方法可以使用多次，也就是說括號(hào)是可以嵌套的，比如”a(ab）3(ab)3ｂ”可以進(jìn)一步壓縮為”a((aｂ)3)2b”。只要找出哪些方磚上刻的是回文串，并按動(dòng)這些方磚，那么將會(huì)啟動(dòng)存有寶藏的密室?，F(xiàn)在請(qǐng)你幫助小可可來完畢這個(gè)艱巨的任務(wù)吧。輸入：第一行只有一個(gè)正整數(shù)T,表達(dá)要判斷的字符串的個(gè)數(shù).接下來T行,每行一個(gè)待判斷的用壓縮方式表達(dá)的字符串,字符串只具有小寫英文字母(‘a(chǎn)’~‘z’)與括號(hào)（‘（’，‘)’),數(shù)字(‘0’~‘9’),注意解壓縮后的原串只含小寫英文字母,也就是說括號(hào)與數(shù)字都是壓縮產(chǎn)生的。輸入數(shù)據(jù)保證所有數(shù)不超過１０9.保證輸入文獻(xiàn)不含多余空格。輸出：共T行,假如輸入文獻(xiàn)中第i個(gè)串是回文串，則輸出”Yeｓ”(不含雙引號(hào))，否則輸出”No”(不含雙引號(hào)).

樣例:輸入:(plaｌinｄｒomｅ．ｉｎ)5ａ(（ab)5)2b（abb)5(bba)5(（ab)5(c)5(bａ）5(asdoｄｓfklj)0)８（(((a)10)10000）１0000００0)10０000０0?((abcd）100000（dｃba)99999)1輸出:(plalｉｎdromｅ.out）NoYesYｅｓYesNo?樣例說明：第二個(gè)串展開后為”aｂbaｂｂaｂbabbabｂｂｂａbｂaｂbabbａbbａ”是回文串第三個(gè)串要注意”(A）0”這種表達(dá)方式也是合法的.第四個(gè)串說明在輸入串長度允許的范圍內(nèi)，解壓縮后的原串也許會(huì)很長．提醒：對(duì)30%的數(shù)據(jù)，每個(gè)輸入串解壓縮后的長度不超過２０2300。對(duì)10０%的數(shù)據(jù)，T≤20,每個(gè)輸入串長度不超過300，所有壓縮后緊跟在括號(hào)后的數(shù)(也即反復(fù)次數(shù))不超過１０9，解壓縮后串的長度也許超過長整形(ＰＡＳCＡＬ中int６4,Ｃ＋＋中l(wèi)onglong）能表達(dá)的最大整數(shù).法杖還原（ｒｅstore）小可可解開了最后一個(gè)機(jī)關(guān)后，終于啟動(dòng)了密室?？脊抨?duì)驚奇的發(fā)現(xiàn)密室里面保存了各種各樣的稀世珍寶，有好多都是考古史上歷來沒有發(fā)現(xiàn)過的,具有極高的研究價(jià)值。但是由于年代過于長遠(yuǎn)或者別的因素，有些文物已經(jīng)損壞。小可可發(fā)現(xiàn)一個(gè)盒子里有一些水晶做的棍子,考古隊(duì)員告訴他這些棍子是古代宗教活動(dòng)中使用的法杖，每個(gè)都是同樣的長度，非常珍貴。但是這些水晶法杖都已經(jīng)斷裂，最長的都不超過5０ｃm了。小可可想假如能把這些法杖都恢復(fù)到原狀那有多好啊!但是由于斷裂后的法杖都混在一起，小可可主線就無法知道本來究竟有多少根法杖及這些法杖本來的長度是多少。為了盡也許簡(jiǎn)化工作,考古隊(duì)決定按照這些法杖本來長度的最小值進(jìn)行恢復(fù)，作為這次考古路程的最后一項(xiàng)工作，你能幫助小可可對(duì)法杖進(jìn)行復(fù)原嗎？輸入：共兩行。第一為一個(gè)整數(shù)N,表達(dá)斷裂后法杖的個(gè)數(shù),并且這個(gè)數(shù)字不大于6４。第二行共N個(gè)整數(shù),代表斷裂后法杖的具體長度。輸出：共一行。表達(dá)本來法杖的最小長度。這里假設(shè)所有法杖的長度均為大于0的整數(shù)。樣例:輸入：(ｒesｔore.in)９521521５21輸出:(rｅsｔｏrｅ.oｕt)6我高二。

23０*７5%+25５*2５%

最后一名進(jìn)安徽省隊(duì)。?去年ＮＯI和今年WＣ的所有同伴,除了那名女選手,全軍覆沒。

我的運(yùn)氣比他們好了一點(diǎn)點(diǎn),剛好沒有成為制度犧牲品。?

對(duì)于試題我可以講的具體點(diǎn)。不僅題目悲劇,數(shù)據(jù)才更“神奇”，我只能用“神奇”來形容這些題目的數(shù)據(jù)了。??第一題赤裸裸的高精度加法,F[I］=F［I－1]+F[Ｉ-2］+F[I-3],N<＝1000；?題目已經(jīng)夠簡(jiǎn)樸了,可數(shù)據(jù)才更讓人驚奇,事實(shí)證明：

只需要使用int6４或者longlonｇ就可以得到滿分，換句話說實(shí)際的數(shù)據(jù)中N<100。?

第二題簡(jiǎn)樸的SPFA+狀態(tài)壓縮即可。但題意確是如此的模糊不清,直接導(dǎo)致了無數(shù)本該滿分的人得了0分,其中也涉及本人。無疑,此題對(duì)于高中和初中的同學(xué)們應(yīng)當(dāng)會(huì)有較好的區(qū)分度，由于去年聯(lián)賽高中組剛剛考了一道類似的題目。至關(guān)重要的一題,就由于題意表達(dá)不清而pａss了。我相信把這一題的題目意思表達(dá)的稍微明確一點(diǎn)，那么省隊(duì)名單就會(huì)有很大的變動(dòng)。又或者這道題是故意忽悠人的？除了“機(jī)關(guān)是否唯一”這點(diǎn)沒有表達(dá)清楚外，其中“第一行N,Ｍ,Ｋ……接下來M行,每行P(事實(shí)上是K）+2個(gè)正整數(shù)……”可緊接著里面又出現(xiàn)了0

，我不認(rèn)為這種低檔錯(cuò)誤該出現(xiàn)在AＨＯＩ的比賽中。??第三題，壓縮字符串，判斷回文。此題貌似是這次比賽最難的一題,我知道的只有一人得了滿分(合肥高中組的,本認(rèn)為他這次穩(wěn)拿第一了，最后連前九都沒有進(jìn))。想到ＨASＨ了，這題就不難了,可是…………反正我是沒想到?；緵]人做出來這題,所以區(qū)分度什么的就不用提了,此題再次pass。

第四題，數(shù)學(xué)題？搜索題？裸搜就能過。我ＤFS＋弱弱的背包剪枝過了。（我自己測(cè)時(shí)有數(shù)據(jù)過不了的）?真的是夠神奇的數(shù)據(jù),事實(shí)證明：?

一個(gè)錯(cuò)誤的，十來行的貪心算法都能得到滿分。

今年安徽?qǐng)F(tuán)隊(duì)鐵定是沒戲了,前五名算團(tuán)隊(duì)分?jǐn)?shù)，只有女選手是高中生……安徽省選就是一場(chǎng)鬧劇。

安徽省選今天結(jié)束。我來說說情況

安徽一開始就定了政策，說NOIP成績算省選2５%的分，而ＮOIＰ初高中試卷不同，初中組就平均分都比高中組高100分，最高分3８0，高中組NOIP最高才2５0左右。各市領(lǐng)隊(duì)紛紛提意見都沒用,組委會(huì)那些人一直說題難就能拉開初高中差距。后來NOI政策下來，說安徽省隊(duì)擴(kuò)名額到9人，大家也就作罷。

結(jié)果今天考完才明白這安徽省選就跟沒選同樣。

總共四題：?第一題是弱DP,放NＯIP里都算簡(jiǎn)樸題。

第三題是一個(gè)判斷回文串的題,全場(chǎng)貌似就一人ｈash過了，其他幾乎全暴零。?第四題用最樸素的搜索就80,加點(diǎn)背包優(yōu)化就AC。?由此看出,第１,３，4完全是無區(qū)分度的題，那第二題呢：歧義題。說一個(gè)路上有多少概率有機(jī)關(guān)什么什么的。題目表述有問題，先說機(jī)關(guān)是獨(dú)立的，又給了個(gè)莫名其妙的式子，后來才知道由于機(jī)關(guān)其實(shí)不是獨(dú)立的那個(gè)式子才故意義。導(dǎo)致安徽的那些高手，參與過以往的好幾屆NOＩ,冬令營,國家隊(duì)選拔，拿過牌等等的選手全暴零，這題AC的人都覺得自己理解錯(cuò)。搞得往屆省隊(duì)的那些人都去找組委會(huì)理論,當(dāng)然完全沒有得到什么滿意的回答。

13４完全沒區(qū)分度,2歧義，ＡＨＯI這四題就跟沒考同樣,安徽省隊(duì)就完全是在按NＯIP成績來選。NOIP那個(gè)難度水平和NOI的差距,就不用說了。。以NOIP的難度來選拔，太失敗了。?九人的省隊(duì),六人是初中的。高中三人一個(gè)是必須的女生,另兩人一高一，一高二當(dāng)然是NOIＰ都考得比較好。安徽省隊(duì)就去ＮOＩ丟人現(xiàn)眼吧。。看那幾個(gè)只能做NOIP難度的初中生能考出什么好成績。

估計(jì)安徽拿金銀銅沒希望了，能拿到不少"年齡最小的參賽選手"獎(jiǎng)大家來看看神奇的AHＯI2023(附試題）這次ＡHOI2023是歷屆來最神奇的AHOI

考試由本來的兩試，一試3題3小時(shí)