7-1 动态区间求和 请编写程序对数组a1,a2,...,a**n进行如下操作 ： 1 i x：给定i,x，将a**i 加上x ； 2 l r：给定l,r，求a**l+a**l+1+...+a**r的值。 输入格式: 第一行包含2个正整数n和q，表示数组长度和查询个数。保证1≤n,q≤106。 第二行n个>整数a1,a2,...,a**n，表示初始数组。保证∣a**i∣≤106。 接下来q行，每行为一个操作。 保证 1≤l≤r≤n,∣x∣≤106。 输出格式: 对于每个 2 l r 操作输出一行，每行有一个整…
7-1 你刚从滑铁卢搬到了一个大城市，这里的人们讲一种难以理解的外语方言。幸运的是，你有一本字典来帮助你理解它们。 输入格式: 输入第一行是正整数N和M,后面是N行字典条目（最多10000条），然后是M行要翻译的外语单词（最多10000个）。每一个字典条目都包含一个英语单词，后面跟着一个空格和一个外语单词。 输入中的每个单词都由最多10个小写字母组成。 输出格式: 输出翻译后的英文单词，每行一个单词。非词典中的外来词汇输出“eh”。 我是fw,我不会map。 7-2 传说二战时X国收到了上帝的一串密码，只有解开密码…
7-1 给定一个字符串 text 和一个模式串 pattern，求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。 KMP（都写在标题里了） 下面两个视频帮助了我很多。 Video1-bilibili Video2-bilibili 7-2 众所周知，互联网时代以来各大公司被“脱裤”的历史是一部五彩缤纷（误）的血泪史，给各大厂商造成了极大的经济损失。更为重要的是，由于有些用户在多个网站使用相同的用户名、密码…
7-1 愿天下有情人都是失散多年的兄妹 这谁出的题啊这么诅咒人/xyx 呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？ 这道题debug了我很久： 有以下误区注意下： 1、父母可以结婚。 2、ID不一定按照顺序。 3、数组开大点。 不要在意奇特的变量名 7-2 X遇到一个关于素数的问题需要你这位大牛帮他解决。素数（prime number）又称质数。一个大于1的自然数，除了1和它本…
7-1 编写一个程序，求出【a,b】范围内的素数。 很明显我们已经不能够再使用暴力一个一个算的低级算法了（除了我这个蒟蒻） 这道题是线性筛的典型题目，每一个数的倍数都不是素书，利用这一点，可以筛掉很多数字来减少运算量。 有种更好的方法在7-3 7-2 你知道吗？有一种编程题需要自己推导公式，得出公式一下子就能解决问题。具体步骤就是自己先按顺序推算几个比较小的情况，看看这几个之间有没有规律，找到规律你就能解决问题了。试着解决下面这个问题吧。有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共…
7-4 人类正在经历一场生化危机，许多城市已经被病毒侵袭，这些城市中的人们为了避免感染病毒，计划开车逃往其他没有被病毒入侵的城市（安全城市）。有些城市之间有公路直达，有些没有。虽然他们知道哪些城市是安全的，但是不知道有没有一条安全路径能够到达安全城市（只有该路径上经过的所有城市都是安全的，该路径才是安全路径）。请你编写一个程序帮助他们判断。 这还是我在没接触过搜索算法的时候写的 这道题我用的是递归写的。 看代码的中午注释（有些英文注释纯属debug发病） 7-2 下图转自“英式没品笑话百科”的新浪微博 —— 所以无…
7-1 最大子段和 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 这里在中间切一刀，使得其变为左右两部分。 利用递归算出左边部分的最小值和右边部分的最小值，返回条件是区间大小为1或0。 算出了左边和右边的所有最小值，接下来应该计算中间那部分被切开来的一段。 中间切开来的一段可以通过计算切开处往两边延伸的最大值，具体来说就是延向左边的最大值+延向…
7-1 汉诺塔问题 给定一个由n个圆盘组成的塔，这些圆盘按照大小递减的方式套在第一根桩柱上。现要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面。 经典递归题目。可以参考：bilibili视频。 7-2 分而治之 不是啊这道题我没用分治啊这 分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。 这道题我一开始用了二维数…
7-1 String 给定一个只含有小写字母的文本串，给定n个模式串，求每个模式串在文本串中的出现次数。 我的做法是比较两个string：str和strr。 str是文本串，而strr是模式串 。以strr的第一个字符作为标志，在str中找到strr的第一个字符，再分别比较str和strr的每一个字母，匹配上即sum++。 7-2 区间 有一个长为n的序列，一个区间的权值定义为这个区间内不同数字的个数，请在这个序列中找出两段不相交的区间使它们的权值的和最大 可以注意到区间越长，权值只增不减，所以应该考虑最长的区间，…