安徽省青少年信息学奥林匹克竞赛中学组试题.docx
- 文档编号:8968836
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:11
- 大小:25.14KB
安徽省青少年信息学奥林匹克竞赛中学组试题.docx
《安徽省青少年信息学奥林匹克竞赛中学组试题.docx》由会员分享,可在线阅读,更多相关《安徽省青少年信息学奥林匹克竞赛中学组试题.docx(11页珍藏版)》请在冰点文库上搜索。
安徽省青少年信息学奥林匹克竞赛中学组试题
⏹
更多企业学院:
《中小企业经管全能版》
183套讲座+89700份资料
《总经理、高层经管》
49套讲座+16388份资料
《中层经管学院》
46套讲座+6020份资料
《国学智慧、易经》
46套讲座
《人力资源学院》
56套讲座+27123份资料
《各阶段员工培训学院》
77套讲座+324份资料
《员工经管企业学院》
67套讲座+8720份资料
《工厂生产经管学院》
52套讲座+13920份资料
《财务经管学院》
53套讲座+17945份资料
《销售经理学院》
56套讲座+14350份资料
《销售人员培训学院》
72套讲座+4879份资料
2010年安联杯安徽省青少年信息学奥林匹克竞赛
中学组试卷
AOI2010
比赛时间:
2010年4月27日8:
00至12:
00
题目名称
搬砖头
寻宝
回文串
法杖还原
源文件名
rock.pas/c/cpp
truesure.pas/c/cpp
plalindrome.pas/c/cpp
restore.pas/c/cpp
输入文件名
rock.in
truesure.in
plalindrome.in
restore.in
输出文件名
rock.out
truesure.out
plalindrome.out
restore.out
试卷类型
传统型
传统型
传统型
传统型
满分
100
100
100
100
是否有部分分
否
否
否
否
时限
1秒
1秒
1秒
1秒
注意事项
1.务必看清题目,严格按照所要求的格式输入、输出。
2.在调试程序时请先使用题目中的示例数据,然后再自行设计多组测试数据进行调试。
3.测试有严格的时间限制,请尽可能优化算法。
4.命名规则:
(1)每题都规定了该题的英文名称。
(2)程序文件和数据文件的主文件名都是该题的英文名字。
(3)程序文件扩展名采用语言环境的默认扩展名。
(4)数据文件都是文本文件,输入和输出文件的扩展名分别是.in和.out。
5.程序应从输入文件读取数据,并严格地按照规定的输出格式将结果输出到输出文件中。
输入数据文件和输出数据文件都与程序在同一个目录中,由于程序所在目录是不确定的,因此不允许在程序中含有盘符信息和任何形式的路径信息。
6.选手在竞赛结束时应在D盘根目录下建立以参赛号命名的文件夹,并将所完成各题的源程序文件放到该文件夹中。
测试以评测系统编译的可执行文件为准,测试系统使用的是规范的编译指令处理源程序,没有附加任何编译选项,请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。
题目
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)
经过辛勤的工作,墓道终于清理干净,小可可随考古队进入了墓室,在墓室的入口处,小可可发现了一张古代的壁画,这幅壁画清楚的描绘了古墓的平面布局,原来这个古墓有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
121000
130200
140030
2590100
3510900
4501090
000
100
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”(不含双引号).
样例:
输入:
(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++中longlong)能表示的最大整数.
4.法杖还原(restore)
小可可解开了最后一个机关后,终于开启了密室。
考古队惊奇的发现密室里面保存了各种各样的稀世珍宝,有好多都是考古史上从来没有发现过的,具有极高的研究价值。
但是由于年代过于久远或者别的原因,有些文物已经损坏。
小可可发现一个盒子里有一些水晶做的棍子,考古队员告诉他这些棍子是古代宗教活动中使用的法杖,每个都是一样的长度,非常珍贵。
但是这些水晶法杖都已经断裂,最长的都不超过50cm了。
小可可想如果能把这些法杖都恢复到原状那有多好啊!
但是由于断裂后的法杖都混在一起,小可可根本就无法知道原来究竟有多少根法杖及这些法杖原来的长度是多少。
为了尽可能简化工作,考古队决定按照这些法杖原来长度的最小值进行恢复,作为这次考古旅程的最后一项工作,你能帮助小可可对法杖进行复原吗?
输入:
共两行。
第一为一个整数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。
第二题简单的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过了,其他几乎全暴零。
第四题用最朴素的搜索就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。
。
第二题,题目明显是每条路的机关互不相关,但是标程是每条路只可能有一个机关
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个满分)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 安徽省 青少年 信息学 奥林匹克 竞赛 中学 试题