资源描述：
《2010年安徽省青少年信息学奥林匹克竞赛试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、中学组试题题目名称搬砖头寻宝回文串法杖还原源文件名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•在调试程序时请先使用
2、题目中的示例数据，然后再自行设计多组测试数据进行调试。3.测试有严格的吋间限制，请尽可能优化算法。4•命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)程序文件扩展名采用语言环境的默认扩展名。(4)数据文件都是文本文件，输入和输岀文件的扩展名分别是.in和.outo5.程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在程序中含有盘符信息和任何形式的路径信息。6.选手在竞赛结束时应在D盘根目录下建
3、立以参赛号命名的文件夹，并将所完成各题的源程序文件放到该文件夹屮。测试以评测系统编译的可执行文件为准，测试系统使用的是标准的编译指令处理源程序，没有附加任何编译选项，请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。题目1・搬砖头(rock)小可可一直对中国五千年的古老文明非常感兴趣，学习历史知识之余，他报名参加了少年考古队，跟随止式的考古队进行考古发掘，通过实践来更好的领会书本知识。这次考古队发现了一个非常巨大的古墓，具有非常高的考古价值，小可可随队来到了考古现场。经过紧张的发掘，古墓的墓道终于显露出来，但是它被一块块方砖封住了，现在小可可的任务就是
4、帮助考古队将这些方砖移走，打通墓道。由于这些保存完好的古代方砖也是珍贵的文物，所以规定一次最多只能搬三块砖。小可可在搬砖的过程中一直在思考一个问题，他很想知道将这些砖头搬走共有多少种不同的搬法。例如，现在总共有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次搬完，第一次搬
5、一个，第二次搬三个）3,1（分2次搬完，第一次搬三个，第二次搬一个）你能不能帮助小可可解决这个问题呢？输入：共一行。是一个1〜1000的正整数N,表示共有N块砖头。输出：共一行。输出一个正整数表示N块砖头移动的方法数。样例：输入：(rock,in)4输出：(rock,out)72.寻宝(truesure)经过辛勤的工作，墓道终于清理干净，小可可随考古队进入了墓室，在墓室的入口处，小可可发现了一张古代的壁画，这幅壁画清楚的描绘了古墓的平面布局，原来这个古墓有N个墓室，M个双向墓道，每条墓道连接两个不同的墓室，两个墓室之间可能有多条墓道相连，且每条墓道上都可能会有机
6、关。入口墓室标号为1号，主墓室标号为N号，壁画上同时标明了整个古墓内总共有K种机关，并且知道每种机关在每条道路上出现的概率，并且告知了这些机关都可以用一些工具破坏掉，工具也共有K种，第i（lWiWK）种宝剑能且只能破坏第i种机关。每个墓室里都可能有一些这样的工具，包括1号墓室（假设墓室里有的工具数量都为无限多，想拿多少就拿多少）。如果小可可在某条墓道上遇到某种机关，他又没有能破坏这种机关的专用工具，那他将可能会受伤，不能到达N号墓室了。现在小可可一种工具也没有没有，但他有足够的力气来带任意多的工具，他想知道的是能成功到达N号墓室(即主墓室)的最大概率是多少。输入
7、：第一行有三个正整数N,M,K分别用一个空格分开，意义如上所述。接下来M行,每行有P+2个正整数，分别是U,V,pl,p2,・・・,pK,分别用一个空格分开，表示有一条墓道连接U,V(UHV)两个墓室，这条道路上第i(lWiWK)种机关岀现概率为pi%,保证0WpiWIOO,且pl+p2+・・・+pKW100.接下来N行，按顺序分别描述广N号墓室中保有工具的情况，每行K个整数tl,t2,…，tK,分别用一个空格隔开，其屮ti(lWiWK)为1表示该墓室内有能破坏第i种机关的工具，否则ti必为0表示该墓室内没有能破坏第i种机关的工具。输出：只输出一个实数表示小可可
8、能成功到达N号墓室(即主
