题目描述：给定一个长度为n的非负整数序列A，求一个平均数最大的，长度不小于L的子段 。 输入描述：第一行用空格分隔的两个整数n和L；第二行为n个用空格隔开的非负整数，表示Ai。 输出描述:输出一个整数，表示答案的1000倍。不用四舍五入，直接输出。 二分查找：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 思路：可以先用二分查找到一个平均值avg来进行判定，能否成立一个子段大于等于F且大于等于这个平均值avg。对于一段序列，每个数减去我们所算的平均数，如果大于0 那么他本身就大于平均数...

题目描述Farmer John's farm consists of a long row of N (1≤N≤100,000)fields. Each field contains a certain number of cows,1≤ncows≤2000.FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at...

题目描述数轴上有n条线段，选取其中k条线段使得这k条线段两两没有重合部分，问k最大为多少。 输入描述:第一行为一个正整数n；在接下来的n行中，每行有2个数ai，bi描述每条线段。 输出描述:输出一个整数，为k的最大值。 思路：这道题也算是常见的贪心中的区间问题了，我存区间中的起点与终点是喜欢使用pair关键字来存，当然也可以自己写一个类型，只是用pair类型可以直接用sort()来排序。 代码步骤：1.输入并排序。2.用两个变量（ans和k）都初始为0（ans是存答案，k是为了后面进行比较），在循环n遍中，如果第i个线段的起点大于或等于k，k就等于第i个线段的终点，ans++； 完整C++版A...

题目描述从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 n > 0, 0 ≤ m ≤ n, n + ( n − m ) ≤ 25。 输入描述:两个整数n，m。 输出描述:按照从小到大的顺序输出所有方案，每行1个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 9 12排在1 3 10 11前面）。 思路：这道题与 递归实现组合型枚举 这道题完全一致，只是使用递归与不使用的区别，然而这两题使用不使用都能AC，建议参考我写的 递归实现组合型枚举--题解 这道题的代码是可以依据递归的深...

题目描述从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。n > 0, 0 ≤ m ≤ n, n + ( n - m ) ≤ 25。 输入描述:两个整数n，m。 输出描述:按照从小到大的顺序输出所有方案，每行1个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 9 12排在1 3 10 11前面）。 思路：这道题跟“递归实现指数型枚举”这道题是有点类似的，只是加入了数字限制。所以这道题也可以用状态压缩来解。 状态压缩的特性：可以枚举所有选与不选的情况。 完整C++版AC代码： #in...

题目描述把 1∼n 这 n(n<10)个整数排成一行后随机打乱顺序，输出所有可能的次序。 输入描述:一个整数n。 输出描述:按照从小到大的顺序输出所有方案，每行1个。 首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。 思路：因为这题是按照字典序，所以优先考虑来发深搜。还需判断这个数字是否被使用过，用深搜常见的vis数组，还可以用bool值来判断，也可以用一个整数来判断。一个整数来代替vis数组，可以大大减少空间复杂度。 C++完整AC代码： #include <iostream> #include <vector...

题目描述从 1\sim n1∼n这 n (n \leq 16)(n≤16) 个整数中随机选取任意多个，输出所有可能的选择方案。 输入描述:一个整数n。 输出描述:每行一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。 这道题有多种解法，这里只介绍状态压缩版： 状态压缩的特性：可以枚举所有选与不选的情况。 实例：不难发现题目输出的结果都为2^n：当n为2时输出：000->/n001->1010->2011->1 2当n为3时输出：000->/n001-&g...

题目描述To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunbur...

题目描述给出三个整数a,b,m，求a^b mod m的值 输入描述:一行三个整数a,b,m。 输出描述:一个整数，表示a^b mod m的值。 实例：输入： 2 100 1007输出： 169 思路：这道题是要先算出a的b次幂再对其结果进行求模（取余），因为b最大可为1e+9，按普通做法来做时间复杂度就太大了，显然这样过不了题，能快速算a的b次幂，就能减小时间复杂度，快速幂就是一种不错的方法。 什么是快速幂：快速幂是一种简化运算底数的n次幂的算法，理论上其时间复杂度为 O(log₂N)，而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取了指数中的2的n次幂，将其转换为时间复...

题目描述：求 a 乘 b 对 p 取模的值，其中 1 <= a,b,p <= 10^18 输入描述:第一行a，第二行b，第三行p。 输出描述:一个整数，表示a * b mod p的值。 实例：输入： 2 3 9输出： 6 思想：这道题是要先算出a*b再对其结果进行求模（取余），因为a和b的最大值为1e+18，我们知道乘法有的时候会溢出，即使是 longlong 也可能在乘法时爆掉。所以我们寻找一种能高效完成乘法操作并且不会爆 longlong 的算法，也就是快速乘。 代码原理可以把 a * b这样算：a * b = a + a + a + ...+ a而a * 1 = aa * 2...

题目描述求 a 的 b 次方对 p 取模的值，其中 0 <= a,b,p <= 10^9 输入描述:三个用空格隔开的整数a,b和p。 输出描述:一个整数，表示a^b mod p的值。 实例：输入： 2 3 9输出： 8 思路：这道题是要先算出a的b次幂再对其结果进行求模（取余），因为b最大可为1e+9，按普通做法来做时间复杂度就太大了，显然这样过不了题，能快速算a的b次幂，就能减小时间复杂度，快速幂就是一种不错的方法。 什么是快速幂：快速幂是一种简化运算底数的n次幂的算法，理论上其时间复杂度为 O(log₂N)，而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取...