搜索
送别2014(普及组菜地测试)©柳州高中c天取经小组1送别2014年柳州高中“菜地杯”（普及组）竞赛时间：2014年12月27日上午8:30-11:30试题名称魔族密码核电站问题隐形的翅膀送给圣诞夜的极光试题目录vp1vp2vp3vp4输入文件名vp1.invp2.invp3.invp4.in输出文件名vp1.outvp2.outvp3.outvp4.out试题类型非交互式程序题非交互式程序题非交互式程序题非交互式程序题附加文件无无无无时限1秒1秒1秒1秒关于竞赛中不同语言使用限制的说明一．关于使用Pascal语言与编译结果的说明1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。2．允许使用数学库(usesmath子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。二．关于C++语言中模板使用的限制说明1．允许使用的部分：标准容器中的布尔集合，迭代器，串，流。相关的头文件：bitsetiteratorstringiostream2．禁止使用的部分：序列：vector，list，deque序列适配器：stack,queue,priority_queue关联容器：map,multimap,set,multiset拟容器：valarray散列容器：hash_map,hash_set,hash_multimap,hash_multiset所有的标准库算法相关头文件：vectorlistdequestackmapsetalgorithm送别2014(普及组菜地测试)©柳州高中c天取经小组21.魔族密码（vp1.pas/c/cpp）【问题描述】风之子刚走进他的考场，就……花花：当当当当~~偶是魅力女皇——花花！！^^（华丽出场，礼炮，鲜花）风之子：我呕……（杀死人的眼神）快说题目！否则……-_-###花花：……咦~~好冷~~我们现在要解决的是魔族的密码问题（自我陶醉：搞不好魔族里面还会有人用密码给我和菜虫写情书咧，哦活活，当然是给我的比较多拉*^_^*）。魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表，每个单词至少包含1个字母，至多75个字母。如果在一个由一个词或多个词组成的表中，除了最后一个以外，每个单词都被其后的一个单词所包含，即前一个单词是后一个单词的前缀，则称词表为一个词链。例如下面单词组成了一个词链：iintinteger但下面的单词不组成词链：integerintern现在你要做的就是在一个给定的单词表中取出一些词，组成最长的词链，就是包含单词数最多的词链。将它的单词数统计出来，就得到密码了。风之子：密码就是最长词链所包括的单词数阿……花花：活活活，还有，这些文件的格式是你要提交的文件中只要在第一行输出密码就行啦^^看你长得还不错，给你一个样例吧：【输入文件】vp1.in第一行为单词表中的单词数N（1=N=2000），下面每一行有一个单词，按字典顺序排列，中间也没有重复的单词咧！！【输出文件】vp1.out只包含一个整数，最长词链数。【输入样例】5iintintegerinterninternet【输出样例】4【数据规模】N（1=N=2000）送别2014(普及组菜地测试)©柳州高中c天取经小组32.核电站问题(vp2.pas/c/cpp)【问题描述】一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。现在，请你计算：对于给定的N和M，求不发生爆炸的放置核物质的方案总数。【输入文件】输入文件vp2.in输入文件只有一行，两个正整数N,M。【输出文件】输出文件vp2.out输出文件只有一个正整数，表示方案总数。【样例输入1】43【样例输出1】13【数据规模】全部数据n=50,m=53.隐形的翅膀（vp3.pas/c/cpp）背景小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。（小杉是怎么看到的？……）【问题描述】天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。【输入】输入文件vp3.in每组测试数据的第一行有一个数N(2=N=30000)第二行有N个不超过1e5的正整数，表示N只翅膀的长度。20%的数据N=100【输出】送别2014(普及组菜地测试)©柳州高中c天取经小组4输出文件vp3.out对每组测试数据输出两个整数，表示小杉挑选出来的一对翅膀。注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。【输入输出样例】vp3.invp3.out4234623【限制】每个测试点1s提示你可以认为黄金分割比就是0.61803398874989494.送给圣诞夜的极光（vp4.pas/c/cpp）【问题描述】圣诞老人回到了北极圣诞区，已经快到12点了。也就是说极光表演要开始了。这里的极光不是极地特有的自然极光景象。而是圣诞老人主持的人造极光。轰隆隆……烟花响起（来自中国的浏阳花炮之乡）。接下来就是极光表演了。人造极光其实就是空中的一幅幅n*m的点阵图像。只是因为特别明亮而吸引了很多很多小精灵的目光，也成为了圣诞夜最美丽的一刻。然而在每幅n*m的点阵图像中，每一个点只有发光和不发光两种状态。对于所有的发光的点，在空中就形成了美丽的图画。而这个图画是以若干个（s个）图案组成的。对于图案，圣诞老人有着严格的定义：对于两个发光的点，如果他们的曼哈顿距离（对于A(x1,y1)和B(x2,y2)，A和B之间的曼哈顿距离为|x1-x2|+|y1-y2|）小于等于2。那么这两个点就属于一个图案……小精灵们一边欣赏着极光，一边数着每一幅极光图像中的图案数。伴着歌声和舞蹈，度过了美丽的圣诞之夜。^_^【输入文件】输入文件vp4.in第一行，两个数n和m。接下来一共n行，每行m个字符。对于第i行第j个字符，如果其为“-”，那么表示该点不发光，如果其为“#”，那么表示该点发光。不可能出现其他的字符。送别2014(普及组菜地测试)©柳州高中c天取经小组5【输出文件】输出文件vp4.out一个数s。【样例输入】1948---------------------------------------------------####-----#-----#----------------------####-----######----#-----#---------------------######---########--#-#---#-#####--#-##-##---#--########--###--###--#-#---#-#----#-##-##--#--#--###--###--###--###--#--#-#--######-#--#---#-#---###--###--########--#--#-#--#------#--#----##---########---######---#---#---######-#--#-----#----######-----####----------------------------#-----####-------------------------------------#----------------------------------------------------------------###--#--------#------#-------------------------#---#-#---------------#------------------------#------#-##--#-##--##-###-#-##-###--###-#--##---#------##--#-##-#-#----#--##--#---##---##-#-----#------#---#-#--#--#---#--#---#---##----#--#-----#---#-#---#-#--#---#--#--#---#---##---##---#-----###--#---#-#--#-##---#--#---#---#-###-#-##---------------------------------------------------【样例输出】4【数据规模】1=n,m=100