当前位置:首页 >> IT/计算机 >>

2010安徽省信息学竞赛(中学组)解题报告


2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

2010 年安联杯安徽省青少年信息学奥林匹克竞赛 中学组试题

AOI 2010
比赛时间:2010 年 4 月 27 日 8:00 至 12:00 题目名称 源文件名 输入文件名 输出文件名 试题类型 满分 是否有部分分 时限 搬砖头 rock.pas/c/cpp rock.in rock.out 传统型 100 否 1秒 寻宝
truesure.pas/c/cpp truesure.in truesure.out

回文串
plalindrome.pas/c/cpp plalindrome.in plalindrome.out

传统型 100 否 1秒

传统型 100 否 1秒

法杖还原 restore.pas/c/cpp restore.in restore.out 传统型 100 否 1秒

注意事项 1. 务必看清题目,严格按照所要求的格式输入、输出。 2. 在调试程序时请先使用题目中的示例数据,然后再自行设计多组测试数据进 行调试。 3. 测试有严格的时间限制,请尽可能优化算法。 4. 命名规则: (1)每题都规定了该题的英文名称。 (2)程序文件和数据文件的主文件名都是该题的英文名字。 (3)程序文件扩展名采用语言环境的默认扩展名。 (4)数据文件都是文本文件,输入和输出文件的扩展名分别是.in 和.out。 5. 程序应从输入文件读取数据,并严格地按照规定的输出格式将结果输出到输 出文件中。输入数据文件和输出数据文件都与程序在同一个目录中,由于程 序所在目录是不确定的,因此不允许在程序中含有盘符信息和任何形式的路 径信息。 6. 选手在竞赛结束时应在 D 盘根目录下建立以参赛号命名的文件夹,并将所完 成各题的源程序文件放到该文件夹中。测试以评测系统编译的可执行文件为 准, 测试系统使用的是标准的编译指令处理源程序, 没有附加任何编译选项, 请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。

安徽

芜湖

2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

题目 1. 搬砖头(rock) 砖头( )
小可可一直对中国五千年的古老文明非常感兴趣,学习历史知识之余,他报 名参加了少年考古队,跟随正式的考古队进行考古发掘,通过实践来更好的领会 书本知识。这次考古队发现了一个非常巨大的古墓,具有非常高的考古价值,小 可可随队来到了考古现场。经过紧张的发掘,古墓的墓道终于显露出来,但是它 被一块块方砖封住了,现在小可可的任务就是帮助考古队将这些方砖移走,打通 墓道。由于这些保存完好的古代方砖也是珍贵的文物,所以规定一次最多只能搬 三块砖。小可可在搬砖的过程中一直在思考一个问题,他很想知道将这些砖头搬 走共有多少种不同的搬法。 例如,现在总共有 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块砖头。 输出:共一行。输出一个正整数表示 N 块砖头移动的方法数。 样例: 输入: (rock.in) 4 输出: (rock.out) 7

2. 寻宝(truesure) 寻宝( )
安徽 芜湖

2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

经过辛勤的工作,墓道终于清理干净,小可可随考古队进入了墓室,在墓室 的入口处,小可可发现了一张古代的壁画,这幅壁画清楚的描绘了古墓的平面布 局,原来这个古墓有 N 个墓室,M 个双向墓道,每条墓道连接两个不同的墓室, 两个墓室之间可能有多条墓道相连,且每条墓道上都可能会有机关。入口墓室标 号为 1 号,主墓室标号为 N 号,壁画上同时标明了整个古墓内总共有 K 种机关, 并且知道每种机关在每条道路上出现的概率, 并且告知了这些机关都可以用一些 工具破坏掉,工具也共有 K 种,第 i(1≤i≤K)种宝剑能且只能破坏第 i 种机关。每 个墓室里都可能有一些这样的工具,包括1号墓室(假设墓室里有的工具数量都 为无限多,想拿多少就拿多少) 。如果小可可在某条墓道上遇到某种机关,他又 没有能破坏这种机关的专用工具,那他将可能会受伤,不能到达 N 号墓室了。 现在小可可一种工具也没有没有,但他有足够的力气来带任意多的工具,他想知 道的是能成功到达 N 号墓室(即主墓室)的最大概率是多少。 输入:第一行有三个正整数 N,M,K 分别用一个空格分开,意义如上所述。接下来 M 行,每行有 P+2 个正整数,分别是 U,V,p1,p2,…,pK,分别用一个空格分开, 表示有一条墓道连接 U,V(U≠V)两个墓室,这条道路上第 i(1≤i≤K)种机关 出现概率为 pi%,保证 0≤pi≤100,且 p1+p2+…+pK ≤100. 接下来 N 行,按顺序分别描述 1~N 号墓室中保有工具的情况,每行 K 个 整数 t1,t2,…,tK, 分别用一个空格隔开,其中 ti(1≤i≤K)为 1 表示该墓室内有能 有 破坏第 i 种机关的工具,否则 ti 必为 0 表示该墓室内没有 没有能破坏第 i 种机 没有 关的工具。 输出:只输出一个实数表示小可可能成功到达 N 号墓室(即主墓室)的最大概 率,四舍五入到小数点后 3 位. 样例: 输入: (truesure.in) 563 1 2 10 0 0 1 3 0 20 0 1 4 0 0 30 2 5 90 10 0 3 5 10 90 0 4 5 0 10 90 000 100
安徽 芜湖 2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

010 001 111 输出: (truesure.out) 0.810 提示:对 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”。只要找出哪些方砖上刻的是 回文串,并按动这些方砖,那么将会开启存有宝藏的密室。现在请你帮助小可可 来完成这个艰巨的任务吧。

输入:第一行只有一个正整数 T,表示要判断的字符串的个数.接下来 T 行,每行 一个待判断的用压缩方式表示的字符串,字符串只含有小写英文字母 (‘a’~‘z’)与括号(‘(’, ‘)’),数字(‘0’~‘9’),注意解压缩后的原串只含小写英文 字母,也就是说括号与数字都是压缩产生的。输入数据保证所有数不超过 109.保证输入文件不含多余空格。 输出:共 T 行,如果输入文件中第 i 个串是回文串,则输出”Yes”(不含双引号), 否则输出”No”(不含双引号).

安徽

芜湖

2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

样例: 输入:(plalindrome.in) 5 a((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.out) No Yes Yes Yes No

样例说明: 第二个串展开后为”abbabbabbabbabbbbabbabbabbabba”是回文串 第三个串要注意”(A)0”这种表示方式也是合法的. 第四个串说明在输入串长度允许的范围内,解压缩后的原串可能会很长.

提示:

对 30%的数据,每个输入串解压缩后的长度不超过 200000。 对 100%的数据,T≤20,每个输入串长度不超过 300,所有压缩后紧跟在括号 后的数(也即重复次数)不超过 109,解压缩后串的长度 可能 可能超过长整形 (PASCAL 中 int64,C++中 long long)能表示的最大整数.

4. 法杖还原(restore) 法杖还原( )
小可可解开了最后一个机关后,终于开启了密室。考古队惊奇的发现密室里 面保存了各种各样的稀世珍宝,有好多都是考古史上从来没有发现过的,具有极 高的研究价值。但是由于年代过于久远或者别的原因,有些文物已经损坏。小可 可发现一个盒子里有一些水晶做的棍子, 考古队员告诉他这些棍子是古代宗教活 动中使用的法杖,每个都是一样的长度,非常珍贵。但是这些水晶法杖都已经断 裂,最长的都不超过 50cm 了。小可可想如果能把这些法杖都恢复到原状那有多
安徽 芜湖 2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

好啊!但是由于断裂后的法杖都混在一起,小可可根本就无法知道原来究竟有多 少根法杖及这些法杖原来的长度是多少。为了尽可能简化工作,考古队决定按照 这些法杖原来长度的最小值进行恢复,作为这次考古旅程的最后一项工作,你能 帮助小可可对法杖进行复原吗?

输入:共两行。第一为一个整数 N,表示断裂后法杖的个数,并且这个数字不大 于 64。第二行共 N 个整数,代表断裂后法杖的具体长度。 输出:共一行。表示原来法杖的最小长度。这里假设所有法杖的长度均为大于 0 的整数。 样例: 输入:(restore.in) 9 521521521 输出:(restore.out) 6

我高二。 230*75%+255*25%

最后一名进安徽省队。

去年 NOI 和今年 WC 的所有同伴,除了那名女选手,全军覆没。 我的运气比他们好了一点点,刚好没有成为制度牺牲品。

对于试题我可以讲的详细点。不仅题目悲剧,数据才更“神奇 神奇”,我只能用“神奇”来形容这些 神奇 题目的数据了。

第一题赤裸裸的高精度加法,F[I]=F[I-1]+F[I-2]+F[I-3],N<=1000; 题目已经够简单了,可数据才更让人惊奇,事实证明: 只需要使用 int64 或者 longlong 就可以得到满分,换句话说实际的数据中 N<100。
安徽 芜湖 2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

第二题简单的 SPFA+状态压缩即可。但题意确是如此的含糊不清,直接导致了无数本该满 分的人得了 0 分,其中也包括本人。无疑,此题对于高中和初中的同学们应该会有较好的区 分度,因为去年联赛高中组刚刚考了一道类似的题目。至关重要的一题,就因为题意表达不 清而 pass 了。我相信把这一题的题目意思表达的稍微明确一点,那么省队名单就会有很大 的变动。 又或者这道题是故意忽悠人的?除了“机关是否唯一”这点没有表达清楚外, 其中“第 一行 N,M,K……接下来 M 行,每行 P(实际上是 K)+2 个正整数……”可紧接着里面又出现了 0 ,我不认为这种低级错误该出现在 AHOI 的比赛中。

第三题,压缩字符串,判断回文。此题貌似是这次比赛最难的一题,我知道的只有一人得了 满分(合肥高中组的,本以为他这次稳拿第一了,最后连前九都没有进) 。想到 HASH 了, 这题就不难了,可是…………反正我是没想到。基本没人做出来这题,所以区分度什么的就 不用提了,此题再次 pass。

第四题,数学题?搜索题?裸搜就能过。我 DFS+弱弱的背包剪枝过了。 (我自己测时有数 据过不了的) 真的是够神奇的数据,事实证明: 一个错误的,十来行的贪心算法都能得到满分。

今年安徽团队铁定是没戏了,前五名算团队分数,只有女选手是高中生…… 安徽省选就是一场闹剧。 安徽省选今天结束。我来说说情况 安徽一开始就定了政策,说 NOIP 成绩算省选 25%的分,而 NOIP 初高中试卷不同,初中组 就平均分都比高中组高 100 分,最高分 380,高中组 NOIP 最高才 250 左右。各市领队纷纷 提意见都没用,组委会那些人一直说题难就能拉开初高中差距。后来 NOI 政策下来,说安 徽省队扩名额到 9 人,大家也就作罢。 结果今天考完才明白这安徽省选就跟没选一样。 总共四题: 第一题是弱 DP,放 NOIP 里都算简单题。 第三题是一个判断回文串的题,全场貌似就一人 hash 过了,其他几乎全暴零。
安徽 芜湖 2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

第四题用最朴素的搜索就 80,加点背包优化就 AC。 由此看出,第 1,3,4 完全是无区分度的题,那第二题呢:歧义题。说一个路上有多少概率有 机关什么什么的。题目表述有问题,先说机关是独立的,又给了个莫名其妙的式子,后来才 知道因为机关其实不是独立的那个式子才有意义。 导致安徽的那些高手, 参加过以往的好几 届 NOI, 冬令营, 国家队选拔, 拿过牌等等的选手全暴零, 这题 AC 的人都觉得自己理解错。 搞得往届省队的那些人都去找组委会理论,当然完全没有得到什么满意的回答。 134 完全没区分度,2 歧义,AHOI 这四题就跟没考一样,安徽省队就完全是在按 NOIP 成 绩来选。NOIP 那个难度水平和 NOI 的差距,就不用说了。 。以 NOIP 的难度来选拔,太失 败了。 九人的省队,六人是初中的。高中三人一个是必须的女生,另两人一高一,一高二当然是 NOIP 都考得比较好。安徽省队就去 NOI 丢人现眼吧。 。看那几个只能做 NOIP 难度的初中 生能考出什么好成绩。 估计安徽拿金银铜没希望了,能拿到不少"年龄最小的参赛选手"奖

大家来看看神奇的 AHOI2010(附试题)
这次 AHOI2010 是历届来最神奇的 AHOI 考试由原来的两试,一试 3 题 3 小时改为一试 4 题 4 小时 选拔省队时 noip 成绩占 1/4(noip 成绩*1/4+省赛成绩*3/4) 普及组提高组统一计算(就是说,普及组起始分数会比提高组普遍高)

第一题,递推+高精(裸的) 第二题,状态压缩的 spfa(裸的,听说分层什么的也都能过) 第三题,压缩字符串的回文判定,比较 rp,貌似是两遍 hash,大家普遍暴力 30(wtj 神牛 AC) 第四题,搜索+垃圾剪枝(裸的) 正当大家以为普遍 330 时,下午发下来的成绩是普遍 230。 。
安徽 芜湖 2010.4.27

2010 年安联杯安徽省青少年信息学奥林匹克竞赛

中学组试题

第二题,题目明显是每条路的机关互不相关,但是标程是每条路只可能有一个机关 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 的问题几个月前老师们都提过,一直未果,现在说规则定 了就无法改变,而且说“这是的问题是经验,下次就不会有了” 其余的都不说了,大家自己看看题目吧,看看今年 noi2010 安徽省初中神牛们的神奇表现。

小学组的题目也顺便附上(我还没看。 。不过好像有 4 个满分)

安徽

芜湖

2010.4.27


相关文章:
2010安徽省信息学竞赛(中学组)解题报告.doc
2010安徽省信息学竞赛(中学组)解题报告 - 2010 年安联杯安徽省青少年信
2010安徽省信息学竞赛试题(小学组).doc
2010安徽省信息学竞赛试题(小学组) - 2010 年安联杯安徽省青少年信息学
2011年安庆市信息学(小学组)竞赛解题报告.doc
2011年安庆市信息学(小学组)竞赛解题报告 - 2011 年安庆市青少年信息学奥林匹克竞赛 上机试题 2011 年安庆市青少年信息学奥林匹克竞赛 小学组竞赛题 比赛时间:2011...
AOI-安徽省信息学竞赛试题_小学组_-2014-2013-2011-2010.pdf
AOI-安徽省信息学竞赛试题_小学组_-2014-2013-2011-2010_学科竞赛_小学教育_教育专区。安徽省青少年信息比赛试题汇总;包含近几年的试题。供爱好计算机编程的朋友...
2012年南海区青少年信息学竞赛复赛题(初中组)解题报告.doc
2012年南海区青少年信息学竞赛复赛题(初中组)解题报告_学科竞赛_小学教育_教育...德清县2007年青少年信息... 8页 1下载券 2010安徽省信息学竞赛(中... ...
2010年青少年信息学竞赛阜阳市队选拔赛中学组试题.doc
2010年青少年信息学竞赛阜阳市队选拔赛中学组试题_IT/计算机_专业资料。2010年青少年信息学竞赛阜阳市队选拔赛中学组试题 可以作为练习题 或者考试题目 ...
noip2010提高组解题报告.doc
noip2010提高组解题报告_学科竞赛_高中教育_教育专区。noip2010提高组解题报告 ...全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 3 页共 7 页 【输入输出...
...十八届青少年信息学奥林匹克竞赛(小学组)解题报告.doc
“讯飞杯”合肥市第二十八届青少年信息学奥林匹克竞赛(小学组)解题报告_学科竞赛_小学教育_教育专区。“讯飞杯”合肥市第二十八届信息学奥林匹克竞赛 小学组 “...
2010年青少年信息学竞赛复赛题.doc
2010年青少年信息学竞赛复赛题_学科竞赛_小学教育_教育专区。2010 年 YJOI 小学组 2010 年青少年信息学奥林匹克竞赛试题 注意事项: 1. 本卷全部采用文件进行输入...
信息学奥赛NOIP2012普及组解题报告.doc
信息学奥赛NOIP2012普及组解题报告 - 信息学奥赛 NOIP2012 普及组解题报告 1. 质因数分解(prime.cpp/c/pas) 【问题描述】已知正整数 n 是两个不同的质数的...
2011年北京市海淀区信息学竞赛中学组解题报告.pdf
2011年北京市海淀区信息学竞赛中学组解题报告_学科竞赛_初中教育_教育专区。2011...2010安徽省信息学竞赛(中... 9页 2下载券 2011安徽省信息学竞赛AH... 7...
2012全国信息学联赛复赛普及组解题报告.doc
2012全国信息学联赛复赛普及组解题报告 - 质因数分解 (prime.cpp/
08年信息学竞赛解题报告.doc
NOIP2008 普及组复赛 解题报告 ] NOIP2008 解题报告 张恩权 一、ISBN 号码 ...2010安徽省信息学竞赛(中... 9页 2下载券 2012年南海区青少年信息... ...
2010年阜阳市中学生信息学奥林匹克竞赛试题.doc
2010年阜阳市中学生信息学奥林匹克竞赛试题_调查/报告_表格/模板_实用文档。2010年阜阳市中学生信息学奥林匹克竞赛试题 FYOI2010 中学组 2010 年阜阳市中学生信息学...
2010年青少年信息学竞赛合肥市队选拔赛小学组试题.doc
2010/4/11 合肥 第1页 共 5页 2010 年青少年信息学竞赛合肥市队
信息学王子解题报告.doc
信息学王子解题报告广东省中山纪念中学 陈启峰 原题: 今年刚升上高二的无机盐...2010安徽省信息学竞赛(中... 9页 2下载券 2011年安庆市信息学(小学......
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解.doc
第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告题解_学科竞赛_初中教育_...第十九届全国信息学奥林匹克联赛(NOIP2013)解题报告 (普及组)宁波市镇海蛟川...
2010年第25届宁波市信息学复赛初中组题目.doc
2010年第25届宁波市信息学复赛初中组题目 - 宁波市第 25 届中小学生计算机程序设计竞赛复赛试题(初中组)第 1 页共 7 页 宁波市第25届中小学生计算机程序设计...
2010海淀区信息学奥林匹克竞赛.pdf
2010海淀区信息学奥林匹克竞赛 - 2010 海淀区信息学奥林匹克竞赛 中学组上机试题: (共 400 分) 一、水下机器人 (程序文件名 deep.cpp/c/pas) 潜水机器人...
信息学奥赛试题精选33题(附带题解).doc
信息学奥赛试题精选33题(附带题解)_其它_高等教育_教育专区。这信息学奥赛试题
更多相关标签: