《某某青少年信息学奥林匹克竞赛中学组试题.》由会员分享，可在线阅读，更多相关《某某青少年信息学奥林匹克竞赛中学组试题.（12页珍藏版）》请在金锄头文库上搜索。
1、n更多企业学院： 中小企业管理全能版183套讲座+89700份资料总经理、高层管理49套讲座+16388份资料中层管理学院46套讲座+6020份资料国学智慧、易经46套讲座人力资源学院56套讲座+27123份资料各阶段员工培训学院77套讲座+ 324份资料员工管理企业学院67套讲座+ 8720份资料工厂生产管理学院52套讲座+ 13920份资料财务管理学院53套讲座+ 17945份资料销售经理学院56套讲座+ 14350份资料销售人员培训学院72套讲座+ 4879份资料2010年安联杯安徽省青少年信息学奥林匹克竞赛中学组试题AOI 2010比赛时间：2010年4月27日8:00至12:00题目
2、名称搬砖头寻宝回文串法杖还原源文件名rock.pas/c/cpptruesure.pas/c/cppplalindrome.pas/c/cpprestore.pas/c/cpp输入文件名rock.intruesure.inplalindrome.inrestore.in输出文件名rock.outtruesure.outplalindrome.outrestore.out试题类型传统型传统型传统型传统型满分100100100100是否有部分分否否否否时限1秒1秒1秒1秒注意事项1. 务必看清题目，严格按照所要求的格式输入、输出。2. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数
3、据进行调试。3. 测试有严格的时间限制，请尽可能优化算法。4. 命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)程序文件扩展名采用语言环境的默认扩展名。(4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。5. 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在程序中含有盘符信息和任何形式的路径信息。6. 选手在竞赛结束时应在D盘根目录下建立以参赛号命名的文件夹，并将所完成各题的源程序文件放到该文件夹中。
4、测试以评测系统编译的可执行文件为准，测试系统使用的是标准的编译指令处理源程序，没有附加任何编译选项，请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。题目1. 搬砖头（rock）小可可一直对中国五千年的古老文明非常感兴趣，学习历史知识之余，他报名参加了少年考古队，跟随正式的考古队进行考古发掘，通过实践来更好的领会书本知识。这次考古队发现了一个非常巨大的古墓，具有非常高的考古价值，小可可随队来到了考古现场。经过紧张的发掘，古墓的墓道终于显露出来，但是它被一块块方砖封住了，现在小可可的任务就是帮助考古队将这些方砖移走，打通墓道。由于这些保存完好的古代方砖也是珍贵的文物，所以规定一次最多只
5、能搬三块砖。小可可在搬砖的过程中一直在思考一个问题，他很想知道将这些砖头搬走共有多少种不同的搬法。例如，现在总共有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次搬完，第一次搬三个，第二次搬一个）你能不能帮助小可可解决这个问题呢？输入：共一行。是一个110
6、00的正整数N，表示共有块砖头。 输出：共一行。输出一个正整数表示N块砖头移动的方法数。样例：输入：（rock.in） 4输出：（rock.out） 72. 寻宝（truesure）经过辛勤的工作，墓道终于清理干净，小可可随考古队进入了墓室，在墓室的入口处，小可可发现了一张古代的壁画，这幅壁画清楚的描绘了古墓的平面布局，原来这个古墓有N个墓室，M个双向墓道，每条墓道连接两个不同的墓室,两个墓室之间可能有多条墓道相连，且每条墓道上都可能会有机关。入口墓室标号为1号，主墓室标号为N号，壁画上同时标明了整个古墓内总共有K种机关，并且知道每种机关在每条道路上出现的概率，并且告知了这些机关都可以用一些工
7、具破坏掉，工具也共有K种，第i(1iK)种宝剑能且只能破坏第i种机关。每个墓室里都可能有一些这样的工具，包括号墓室（假设墓室里有的工具数量都为无限多，想拿多少就拿多少）。如果小可可在某条墓道上遇到某种机关，他又没有能破坏这种机关的专用工具，那他将可能会受伤，不能到达N号墓室了。现在小可可一种工具也没有没有，但他有足够的力气来带任意多的工具，他想知道的是能成功到达N号墓室（即主墓室）的最大概率是多少。输入：第一行有三个正整数N,M,K分别用一个空格分开，意义如上所述。接下来M行,每行有P+2个正整数，分别是U,V,p1,p2,pK,分别用一个空格分开，表示有一条墓道连接U,V(UV)两个墓室，这
8、条道路上第i(1iK)种机关出现概率为pi%,保证0pi100，且p1+p2+pK 100.接下来N行，按顺序分别描述1N号墓室中保有工具的情况，每行K个整数t1,t2,tK，分别用一个空格隔开,其中ti(1iK)为1表示该墓室内有能破坏第i种机关的工具，否则ti必为0表示该墓室内没有能破坏第i种机关的工具。输出：只输出一个实数表示小可可能成功到达N号墓室（即主墓室）的最大概率，四舍五入到小数点后3位.样例：输入：（truesure.in）5 6 31 2 10 0 01 3 0 20 01 4 0 0 302 5 90 10 03 5 10 90 04 5 0 10 900 0 01 0 0
9、0 1 00 0 11 1 1输出：（truesure.out）0.810提示：对40%的数据，N10,M100,P4对100%的数据，N500,M1000,P10.3. 回文串（plalindrome）经历了种种机关的考验，小可可终于来到了主墓室，他发现主墓室墙上还有个非常复杂的机关，组成墓室墙壁的方砖上，均刻有由古代字符和数字组成的图案，每块方砖上一组。小可可发现这些古代字符恰好有二十六种，可以用小写英文字母(az)来代替他们，而数字可以用(09)代替。经过细致的研究，小可可惊奇的发现这些图案中有一些居然是压缩过的回文串。所谓回文串，就是从左向右读与从右向左读都一样的字符串，比如”abcb
10、a”是回文串，而”abcbb”不是回文串。而压缩过的回文串，就是对串中连续重复出现p次的子串A,即”AAA”(共p次),可以替换为”(A)p”。比如”aababababababb”可以替换为”a(ab)3(ab)3b”(当然也可替换为”a(ab)6b”),这样的压缩方法可以使用多次，也就是说括号是可以嵌套的，比如”a(ab)3(ab)3b”可以进一步压缩为”a(ab)3)2b”。只要找出哪些方砖上刻的是回文串，并按动这些方砖，那么将会开启存有宝藏的密室。现在请你帮助小可可来完成这个艰巨的任务吧。输入：第一行只有一个正整数T,表示要判断的字符串的个数.接下来T行，每行一个待判断的用压缩方式表示的
11、字符串，字符串只含有小写英文字母(az)与括号(, ),数字(09),注意解压缩后的原串只含小写英文字母，也就是说括号与数字都是压缩产生的。输入数据保证所有数不超过109.保证输入文件不含多余空格。输出：共T行，如果输入文件中第i个串是回文串，则输出”Yes”(不含双引号),否则输出”No”(不含双引号).样例：输入：(plalindrome.in) 5a(ab)5)2b(abb)5(bba)5(ab)5(c)5(ba)5(asdodsfklj)0)8(a)10)10000)10000000)10000000(abcd)100000(dcba)99999)1输出：(plalindrome.ou
12、t) NoYesYesYesNo样例说明： 第二个串展开后为”abbabbabbabbabbbbabbabbabbabba”是回文串第三个串要注意”(A)0”这种表示方式也是合法的.第四个串说明在输入串长度允许的范围内，解压缩后的原串可能会很长.提示：对30%的数据，每个输入串解压缩后的长度不超过200000。对100%的数据，T20,每个输入串长度不超过300,所有压缩后紧跟在括号后的数(也即重复次数)不超过109,解压缩后串的长度可能超过长整形(PASCAL中int64,C+中long long)能表示的最大整数.4. 法杖还原（restore）小可可解开了最后一个机关后，终于开启了密室。
13、考古队惊奇的发现密室里面保存了各种各样的稀世珍宝，有好多都是考古史上从来没有发现过的，具有极高的研究价值。但是由于年代过于久远或者别的原因，有些文物已经损坏。小可可发现一个盒子里有一些水晶做的棍子，考古队员告诉他这些棍子是古代宗教活动中使用的法杖，每个都是一样的长度，非常珍贵。但是这些水晶法杖都已经断裂，最长的都不超过50cm了。小可可想如果能把这些法杖都恢复到原状那有多好啊！但是由于断裂后的法杖都混在一起，小可可根本就无法知道原来究竟有多少根法杖及这些法杖原来的长度是多少。为了尽可能简化工作，考古队决定按照这些法杖原来长度的最小值进行恢复，作为这次考古旅程的最后一项工作，你能帮助小可可对法杖
14、进行复原吗？输入：共两行。第一为一个整数N，表示断裂后法杖的个数，并且这个数字不大于64。第二行共N个整数，代表断裂后法杖的具体长度。输出：共一行。表示原来法杖的最小长度。这里假设所有法杖的长度均为大于0的整数。样例：输入：(restore.in) 95 2 1 5 2 1 5 2 1输出：(restore.out) 6我高二。230*75%+255*25% 最后一名进安徽省队。去年NOI和今年WC的所有同伴，除了那名女选手，全军覆没。我的运气比他们好了一点点，刚好没有成为制度牺牲品。对于试题我可以讲的详细点。不仅题目悲剧，数据才更“神奇”，我只能用“神奇”来形容这些题目的数据了。第一题赤裸裸的高精度加法，FI=FI-1+FI-2+FI-3，N=1000； 题目已经够简单了，可数据才更让人惊奇，事实证明： 只需要使用 int64或者longlong就可以得到满分，换句话说实际的数据中N100。第二题简单的SPFA+状态压缩即可。但题意确是如此的含糊不清，直接导致了无数本该满分的人得了0分，其中也包括本人。无疑，此题对于高中和初中的同学们应该会有较好的区分度，因为去年联赛高中组刚刚考了一道类似的题目。至关重要的一题，就因为题意表达不清而pass
