编程竞赛题(超牛题目,留下做研究).doc

AACMer不得不知道的事儿(二)Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 作为一个入门的ACMer，在参加比赛之前，你势必要了解算法的一些基本概念，比如复杂度。 ACM的题目，只要不是a+b级别的，总会需要一定的算法来解决，即使是枚举， 也是叫做穷举算法。 一个算法的好坏，由它的复杂度来衡量，复杂度越高，算法越低效。 复杂度包括不限于时间复杂度、空间复杂度和编码复杂度，即其花费的时间、空间（即内存使用等）还有实现的难度。第三个在做研究的时候不一定会考虑，但ACM赛制是5个小时内决胜负，编码复杂度也是至关重要的一个因素。 一、时间复杂度 通俗讲时间复杂度就是用来衡量算法执行的时间的，它和问题的规模(通常用n表示，如果问题规模和不止一个变量有关，那用n,m,k等等表示)有关，规模越大，所花费的时间越长。越高效的算法，在n增长的时候，执行时间增加的越少。例如求1.n的和，下面有三种写法：普通写法是：int sum=0,i;for(i=1;i=n;i+)sum+=i; 我们说它的时间复杂度是O(n)。因为运行一次，必须执行一次n长度的循环，n越大时间越大。对于每次循环，它需要执行一次i+，一次sum+=i，一次判断是否i=n，可以说复杂度是O(3n)，但是通常常数不被计入到复杂度的计算中，所以简化为O(n)。文艺写法：int sum=n*(n+1)/2;复杂度O(1)，很明显运行一次只需要执行一次运算操作。2B写法：int sum=0,i,j;for(i=1;i=n;i+)for(j=1;j=i;j+)sum+; 嗯，很暴力很2B的O(n2)复杂度，你懂的。 说到这里相信你已经对时间复杂度有了一定的了解了。二、空间复杂度 所谓空间复杂度就是你用的内存的大小，简单说就是你用了多少变量开了多大的数组，malloc了多少内存，综合起来就是了，这点比较简单，就不一一赘述。三、编码复杂度 编码复杂度和你实现算法所需要的时间有关，而且有时候和时间复杂度也有一定关系，但不是越高级的算法越难实现，像刚才的例子就是时间复杂度高了，编码复杂度也跟着高了。 当你对算法有了一定了解，在ACM上收获了不少知识之后，你甚至能在一些场合很轻松地解决掉一些问题，并BS一些动手能力不强的人。 就好比某个牛津计算机系从本科读到博士还经常考第一的人，可以花15分钟的时间写出类似这样的代码，来求一个数组里面，有多少数比它左边的数都要大：cnt=0;for(i=0;in;i+) for(j=0;ji;j+) if(aiaj) break; if(j=i) bi=1; else bi=0;for(i=0;in;i+) if(bi=1) cnt+;printf(%dn,cnt); 这样写法的复杂度相信大家可以估算的出来，那么，我要你写出一个比这个的时间复杂度、代码复杂度都要低的代码来，另外，我还要你求出有多少个数比它右边都要小，同时，从小到大输出他们的下标（从0开始）。输入格式第一行，是一个数T(T=500)，表示有多少组测试数据。第二行乃至结束，是T组数据，对于每组数据：第一行是一个数n(1=n=100000)，表示这个数组的长度。第二行是n个整数，有空格分隔。输出格式对于每组数据，输出四行：第一行，一个数A，表示有多少个数比它左边都大第二行，A个整数，表示比它左边都大的数的下标第三行，一个数B，表示有多少个数比它右边都小第四行，B个整数，表示比它右边都小的数的下标输入样例241 3 1 451 2 3 2 1输出样例30 1 322 330 1 214Hint数组太大要开成全局变量，即放在函数体外，因为定义在函数体内部是占用函数栈的空间的，而函数栈空间比较小，放里面很容易造成爆栈然后得到“运行时错误”的结果。另外，输入流和输出流是分开的，就是说，处理完一组数据，输出答案，再处理第二组数据，再输出第二组数据的答案，再处理第三组.，这样和处理完所有数据，再一次性输出，是完全等价的。并且，系统评判的题目都是这样，不需要保存所有答案一并输出。之所以这题是(二)滴原因是去年有道一的了喲，看看有助于解决题目哟亲BXYM-入门之道Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 在华农的ACM界中，也有一对闻名古今的双胖师徒组合XYM和BM. BM师父有一个特殊的癖好，BM肚子很大，因为他很喜欢吃西瓜，但是BM的嘴很小，一次只能吃下大小不超过K的西瓜。刚进门的XYM为了能拜入BM大神的门下，他买来一个大小为N的巨型西瓜请BM大神吃。但这个西瓜太大了，BM是不可能一次就吃完的，于是他让XYM将西瓜切开。为了简化问题，每切一刀，大小为N的西瓜就为分成大小分别为N/2的两块小西瓜，如果N为奇数，则被分为一块大小为N/2，一块大小为（N/2 + 1）的西瓜。（此处 “/” 为整除） BM为了考验下XYM是否有资格成为他的徒弟，于是他就问XYM，这个大小为N的西瓜他一共要吃多少次才能全部吃完？ 可是XYM要忙着切西瓜，于是他决定向你求助，你能帮他回答这个问题吗？输入格式 第一行只有一个正整数T，表示题目共有T组数据 接下来一共有T行， 每行有两个正整数n, k，分别代表XYM买来的西瓜的大小和BM一次能吃下最大的西瓜的大小。 （输入数据保证n, k全部为正整数， 2= n =100000, 1= k = n-1）输出格式 对于每组数据每行输出一个整数，代表BM一共要吃多少次才把整个西瓜全部吃完。输入样例314 315 11024 5输出样例615256Hint对于第一组数据：第一次切开后西瓜被分成两块大小为7的西瓜，对于每块大小为7的西瓜再切一刀就变成了一个大小为3和一块大小为4的西瓜，大小为3的BM就能直接吃掉了，然后对于大小为4的西瓜再切一刀，就变成两块大小为2的西瓜。这时一共有6块西瓜，他们的大小分别为2，2，2，2，3，3，所以BM一共要吃6次才能把西瓜全部吃完。CPKKJ的生日礼物Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 写下这题目的时间是11.24，美国时间也是11.24，以此题祝远在美帝的PKKJ彭教主生日快乐。 生日嘛，自然少不了生日礼物的啦。这天彭教主收到来自中国的一份神秘的生日礼物（传说中是个漂亮的MM o(_)o 哈哈）。可是礼物却被一个密码锁锁了起来（pkkj大叫一声：坑爹啊，哪个家伙这么缺德-_-b）。在礼物箱上还附着一张纸条：嘿嘿想知道密码吗？那就把下面的题目解出来，答案就是密码啦！ 对于一个字符串，定义它的前缀就是指字符串的任意首部。例如字符串abc的前缀有空串，a，ab，abc。 对于一个字符串集合，如果集合中任一个元素都不是其他元素的前缀的话，我们称之为完美非前缀集合。举个例子：”happy”, “birthday”, “to”, “pkkj”就是一个完美非前缀集合，而“happy”, “hat”, “h”就不是完美非前缀集合。 现在问题来了，给你一个字符串集合，你要找出一个该集合的子集，使得该子集是一个完美非前缀集合，且包含最多的元素。问你这个完美非前缀子集最多包含多少个元素？ 由于彭教主一心只想着礼物里面的神秘MM，正所谓一心不能二用，所以他想让你帮他来解决这个难题。输入格式 第一行只有一个正整数T，表示题目共有T组数据 对于每组数据，输入一个整数n （ 0 n = 50 ）， 接下来有n行，每行输入一个字符串，字符串由小写字母（az）组成，且长度不超过50输出格式 对于每组数据每行输出一个整数，代表一个完美非前缀子集最多包含多少个元素。输入样例24happybirthdaytopkkj4happyhathha输出样例42Hint对于第一组数据：该集合本身就是一个完美非前缀集合，所以包含最多元素的完美非前缀子集就是它本身，一共有4个元素对于第二组数据，”happy”,”hat”是其中一个的包含最多元素的完美非前缀子集，其元素个数为2DXYM-AC之路Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 在华农的众ACMers中，有着一位家喻户晓、人称一鸣惊人的DP神牛XYM。由于XYM太出名了，他的仰慕者决定给XYM写一部个人传奇以传承他光辉的AC之路。为了使故事更加真实，特派记者Y决定去采访XYM教主。由于XYM太出名了，而且时间很忙，他对于每个问题只会回答Yes或No。由于这是记者Y第一次跟XYM教主面对面访谈，他十分紧张，所以他可能会重复问同一个问题，但对于相同的问题XYM都会是相同的回答。记者Y有个特殊的癖好，每问完一个问题，他都会把这个问题和XYM教主的回答分开记下来。 然而，不幸的是，Y在回去的路上不小心把记有XYM的回答的纸条弄丢了，只剩下一些问题。可怜的记者Y决定将XYM教主所有可能的回答的组合全部写出来。这样，他就有可能认出那个才是XYM的回答。 不过Y不知道一共要写多少才行，所以他想向聪明的你求救，一共有多少组可能的回答组合他需要写出来的？输入格式第一行只有一个正整数T，表示题目共有T组数据 接下来是T组数据。 每组数据第一行输入一个整数n（1= n = 50）, 接下来有n行，每行输入一个问题quei,表示Y第i个问的问题是什么。 每个问题最多由50个字符组成，每个问题只包含小写字母 (a-z),大写字母 (A-Z), 问号 (?) 或者下划线 (_).两个问题问题被认为相同当且仅当组成问题的所有字符一一对应 相同。输出格式 对于每组数据输出一个整数，表示所有可能的回答的组合的方案数。输入样例33How_are_you_doing?How_do_you_like_our_country?How_are_you_doing?1 Whazzup?4Do_you_like_my_story?Do_you_like_my_storyDO_YOU_LIKE_MY_STORY?Do_you_like_my_story?输出样例4216Hint对于第一组数据，一个有四种可能的回答组合Yes, Yes, Yes;Yes, No, Yes;No, Yes, No;No, No, No.E我们仍未知道那天所看见的花的名字Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 芽间、仁太、波波、安鸣、雪集、鹤见是昔日孩童时期总是一起结伴同玩的6位好朋友。自从小时候的一次意外后，大家的关系渐行渐远。随着时间的流逝，大家都为了自己的生活和理想各奔东西。 某天，芽间要离开大家了，她给大家各留下了一封电子邮件。这时候，在名牌高中读书的雪集，仗着自己的电脑知识，把给仁太电子邮件内容（一句话）加密了。然后他留下了一段加密程序，因为他想看看读普通学校的仁太能不能解密出来的。 但事实证明，学校的名牌与否不是最重要的，重要的是自己个人的努力。为了看到芽间给自己的信，仁太专门去学了C语言，然后把那句话解密出来了。你也能做到吗？输入格式以下是雪集的加密代码：void Encrypt(char msg)char key = sleepiforest;int msgLen = strlen(msg);int keyLen = strlen(key);int offset;for(offset=0;offsetmsgLen;+offset)msgoffset = keyoffset%keyLen; / 是异或运算for(offset=0;offsetmsgLen;+offset)printf(%02x ,msgoffset); /%x是十六进制芽间的邮件里的内容msg传入上面的函数后，得到以下的输出。53 30 39 59 0e 48 18 4f 34 0a 01 13 16 18 48 28 15 44 28 00 06 45 0d 55 0d 52 4a 4a 50你能把msg的原文输出解密出来吗？输出格式根据加密程序，把这句话解密，然后输出出来即可。例如：假设解密出来的这句话是“WELCOME TO THE TEAM OF SCAU_ACM”。那么你只需要把这句话输出就可以了。提供一个模板:#include int main()char msg = WELCOME TO THE TEAM OF SCAU_ACM;puts(msg);return 0;只需要把msg里的内容换成你解密出来的内容，提交即可通过。输入样例无输出样例根据题目要求输出Hint一个字符也不能漏，不能错哦所以呢最好还是在解密程序里把解密后的串输出吧提供一个录入数据的代码：char bin = 53 30 39 59 0e 48 18 4f 34 0a 01 13 16 18 48 28 15 44 28 00 06 45 0d 55 0d 52 4a 4a 50;char msg50;int len = (strlen(bin)+1)/3;for(int i=0;ilen;+i)这里可以用sscanf把bin内的数据录入到msg具体用法大家查资料吧F俄罗斯方块Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 某个ACMer很喜欢玩游戏。这天，他在一个网站上看到一个关于俄罗斯方块能否无限玩下去的帖子，于是很感兴趣的把这问题转述给了其余的ACMer，结果无人问津 这时恰好新生赛也到了，这个ACMer于是灵机一动，想出一个俄罗斯系列题目！但是被强大的lyd鄙视了一把，认为这样出的题目难度会很大，于是某人就一再保证，该题目一定会很简单很简单的！所以，就有了这样的一个很简单的问题：有一个A*B大小的框，往里面放入N条1*M的长条，能否放入？ 怎么样，这问题很简单吧？输入格式第一行输入T作为case数，第二行到第T+1行分别输入整数A，B，N，M作为框的长宽和长条的数目和长度。(0A,B,N,M1000000)输出格式对每个case输出一行，能放入输出YES，不能放入输出NO。输入样例21 1 2 33 3 2 2输出样例NOYESGDeathGod不知道的事情Time Limit:1000MS Memory Limit:65535K题型: 编程题语言: 无限制描述 蚂蚁是很强大的动物，除了DeathGod知道的事情外还有很多不知道的！例如 根据某种理论，时间方向上有无数个平行世界，有的世界蚂蚁很多，有的世界蚂蚁很少，有的世界蚂蚁会繁殖，有的世界蚂蚁不会繁殖。 DeathGod没有时空穿梭的能力，因此他无法知道所有的蚂蚁加起来到底有多少。但他知道未来的ACMer非常厉害，可以暂时抛弃肉体，以思维进行时空旅行。因此他留下一段话给未来的ACMer，让他们帮他数一数，所有的平行世界总共有几只蚂蚁。 由于时间旅行是不可逆的，因此DeathGod只能让ACMer逆向推算出在DeathGod的那个时间点上所有的平行世界总共有多少只蚂蚁。 此时，未来的ACMer，就是你，已经在无数个平行世界中搜索过了（只用了一瞬间），在你所处的时间点上，第0，1，2，3N-1个平行世界上的蚂蚁数目分别为A0,A1,A2,A3.AN-1，为了简化计算，所以每个平行世界上的蚂蚁数目都是当作整数计算。而已知每两只蚂蚁每过时间t，就会生出一只蚂蚁。如果有八只蚂蚁，那么过了时间t后就会变成十二只蚂蚁，再过时间t就会变成十八只蚂蚁。如果蚂蚁数目是单数，比如有七只蚂蚁，那么过了时间t后就会变成十只蚂蚁。再过时间t就会变成十五只蚂蚁。有的世界里面的蚂蚁是不会繁衍的，因此蚂蚁的个数就不会变化，不会遵从这个定律。假设所有的蚂蚁不会死亡。那么你应该可以计算出在DeathGod所在的时间点上，最少可能存在几只蚂蚁（如果只有一只蚂蚁，是不会繁衍的，如果蚂蚁会繁衍，那么一定遵从上面的定律。如果不遵从上面定律的，那么一定不会繁衍。且蚂蚁只能跟和自己同一个世界里的蚂蚁交配。） 不过，最囧的事情就是，即使你算出来了，由于信息无法逆时间方向传递，因此DeathGod还是无法知道。不过为了培养未来的ACMer的耐心和毅力，以及面对恶心模拟题时不至于双眼发昏脑袋发胀