2016.8.16中山纪念中学信息学普及组模拟比赛题解
这次考试考得棒棒哒，第二次第一,主要是因为很多大神走了,所以我就奋起直追,就360啦,目标直奔c组,打好坚实基础,努力学习,不放弃思考,oh yeah.比赛时一看题目感觉挺水的,一下就carry了第一题和第二题,随后游走gank了第四题,最后与第三题纠结,最后还是carry了,哈哈.附带题目的题解致上.
第1题题目描述
凭着奶牛的聪明，他很快就把语数英X四科赶了上来（听说还是半斤八两），但是，可能由于他太聪明了，导致基础科一直搞不好，所以每次考试，他都想作弊，而且他又找回了一些朋友，于是他就试一下作弊的滋味了。他是怎么作弊的呢？奶牛的朋友太强悍了，他生怕被老师发现，又害怕被其他同学偷去，于是他每次递给奶牛都是一段只含有a,b,c,d的字符串，那么答案是什么呢？“答案就是该字符串内最长的回文串。”哈哈哈，奶牛瞬间就发现了这个秘密，可是，奶牛的朋友是个**狂，他每次递给奶牛的都是一些非常长的字符串，奶牛在短时间内没发找到答案，所以奶牛又找到了你，帮他找出字符串内最大的回文串。
别看题目这么长,其实真的挺简单的,就是求最长回文而已,用常规方法枚举回文中心点,往两边扩展,直到不等于为止,还有一种情况是ABBA这样子的,我们就用两个变量一个为i,另一个为i+1,所以呢我们就每次x(为i的变量)-1,y(另一个)+1,记录一下开头结尾输出就行了.
第二题题目描述
令S为n个元素的集合，则S有2^n-1个子集（除去空集）。现在要你从这2^n-1个子集中选出最多的子集，使这些子集能构成一个杂置。
杂置是指任意两个集合没有包含或被包含的关系。例如对于有3个元素的集合{a,b,c}。
{a,b}，{a,c}，{b,c}可以构成一个杂置，而{a},{b},{a,b}则不能构成一个杂置。
杂置呢,这个东西蛮难理解的,但是，我们并不需要太多的数据来求，前4个就非常能说明问题了
1—1，2—2，3—3，4—6，是什么规律呢，那就是杨辉三角！做之前要把杨辉三角模拟出来，然后输出
a[b[i]+1,(b[i]+1)div 2+1]就可以了。b数组是读入的东西。
第三题题目描述
一天你对着眼前的景物拍了一张照，这个相机很特别，有建筑物的地方显示“X”，没有建筑物的地方显示为“.”,假设每个建筑都是块状的，照片长W(1<=W<=1,000,000),用N(1<=N<=50,000)对平面坐标(x,y)( 1 <= x <= W, 0 <= y <= 500,000)描述照片中建筑物高度发生变化的位置,你的任务是计算出最少需要多少个建筑才能形成该照片。
如下图：
（没有图片啦)-_-
在输入中被描述为: (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1).这幅图片最少需要6个建筑，下面是用6个建筑形成该照片的例子：没有例子啦-_-
然后呢我们把第一个数删除,就是说(1,1)删除第一个1,(2,2)删掉第一个2,然后双重循环判断,如果a[i]
第四题题目描述
一条笔直的路边有N(1 <= N <= 1,000)个草丛，草丛位置互不相同，我们用一个整数表示每个草丛的位置。现在你从某个位置L(1<=L<=1,000^2)出发去除掉所有的草丛，为达到目的你可以来回改变方向去移动，假设你以每秒1个单位距离的速度移动，并且能在到达草丛的瞬间把草除掉。
要求计算草丛被清除的时刻总和的最小值。
这道题贪心是可以60分的,所以,就显得"十分的简单"的样子,事实上,正解是有一定难度的,首先,正解是动态规划,然后,我们还有一个条件才能执行状态转移方程,是什么呢,那就是j>i n>=i>-1 1<=j<=n
方程自己推啦.
希望,自己,奇迹.
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！