小可可



更多企业学院：

中小企业管理全能版?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