题目难度：三星 考察点：动态规划、滚动数组 方法1：动态规划 1. 分析： 这个题的本质就是就一个最大的m段字段和，本质还是动态规划。设一个dp[i][j] 表示以第j个数字结尾的前面j个数字取i段的最大和。那么对于第j个数字来说就有两种选择： (1). 第j个数字属于最后一段，即dp[i][j] = dp[i][j-1] + a[j] (2). 第j个数字不属于最后一段，自己是一个新段，即dp[i][j] = max{dp[i-1][k]} + a[j] 其中i-1<=k<j。 对于dp的状态转移方程就很好写了,就是(1)(2)两种选择的最大值而已，最后输出max{...

题目难度：二星 考察点：动态规划、预处理 方法1：暴力、动态规划 分析： 这个题很像之前的跳台阶：一共有n个台阶，青蛙只能跳1阶或者是2阶，问有多少种跳法？ 跳台阶思路如下: 假设青蛙跳n个台阶的跳法为f(n)那么： 如果第一次跳的是1阶，那么剩下的n-1个台阶，跳法是f(n-1) 如果第一次跳的是2阶，那么剩下的n-2个台阶，跳法是f(n-2) 由此可得：f(n) = f(n-1) + f(n-2) 当n=1时，f(1) = 1 当n=2时，f(2) = 2 至此，跳台阶问题已经解决。 对于这道题来说的话，我们可以借助之前的想法，假设月神有f(n)种方法...

题目难度：三星考察点：排序、最长不下降子序列（O(nlogn)） 方法1：排序、动态规划 分析：根据题意，我们可以首先按照长度（或者是宽度）其中之一进行排序，那么我们接下来就只需要想办法将宽度搭积木的层数变得最多就可以了，将其转化为了最长不下降子序列（因为序列中是可以有相等的情况）的问题，我们就可以运用动态规划的思想进行操作。令dp[i]表示以a[i]结尾的最长不下降子序列长度。那么对于第i个来说就有两种可能：(1). 如果存在a[i]之前的元素a[j]，使得a[i] >= a[j]，那么就把a[i]放在以a[j]结尾的序列后面，找到了一条更长的不下降子序列，此时dp[i] = max...

题目难度：二星考察点：双指针 方法1：暴力、前缀和 分析：我们按照题意进行计算，枚举第一刀下标i和第二刀的下标j即可，然后判断区间[1, i]和区间[j,n]的和是不是相等，如果相等记录答案，取最大值即可。在计算区间和的时候要注意的是需要提前预处理一下前缀和，要不然直接计算区间和的话会使得时间复杂度变高。 算法实现：(1). 首先用一个数组sum计算前缀和。(2). 枚举切两刀的两个下标i和j，计算区间[1,i]和[j,n]的值，那么区间[1,i]的和显然等于sum[i]，区间[j,n]的和则等于sum[n]-sum[j-1]，我们只需要判断这两个是否相等即可，相等则记录答案。(3). 输...

题目难度：二星考察点：贪心、模拟 方法：贪心、模拟 分析：我们分析一下题意，如果想尽可能的让塔的不稳定性小的话，那么就需要让最高塔高度与最低塔高度的差尽可能低，也就是让最高塔的高度尽可能低，最低塔的高度尽可能高。那么我们每次进行操作的时候就是首先将整个高度数组按照从小到大进行排序，然后高度最大值-1，高度最小值+1。一直循环k次， 在每次进行操作的时候分别记录最大值和最小值即可。还需要注意的一点是如果高度最大值-高度最小值<=1的时候，此时就不需要进行操作了，因为此时操作是完全多余的，而题目让我们求的是最少操作次数。举个例子：就拿样例来说，我们可以进行两次操作：第一次操作：我们首先将高...

题目难度：一星考察点：枚举 方法1：枚举 分析：我们将所有的可能情况列举出来然后取得最大值，一共有如下6种情况:(1). ans = a + b + c;(2). ans = a + b * c;(3). ans = a * b + c;(4). ans = a * b * c;(5). ans = a * (b + c);(6). ans = (a + b) * c;输出最大的ans即可。需要注意的一点是：不用进行排序，然后判断最小值，因为给定的a,b,c顺序是一定的！！！举个反例:1, 3, 1如果以最小值判断的话，那么此时表达式的最大值为(1+1)*3，这样是不对的，因为这样改变了数据...

题目难度：三星考察点：计算几何 方法：计算几何、枚举 分析：对于这道题来说我们有如下需要考虑的地方：(1). 一个点A(x1,y1)围绕一个点B(x2,y2)逆时针旋转90°一次，对应坐标A的变化？旋转多次呢？我们都知道如果B是原点的话，那么逆时针旋转90°一次之后坐标A(x1,y1)将变为C(y1, x1)，那么如果B不是原点呢？我们将整个坐标系进行移动，将B移动到原点，那么A的坐标就会变为(x1-x2,y1-y2)，那么此时进行逆时针旋转90°，A的坐标就会变为C(y1-y2,x1-x2)。注意，此时C的坐标是相对于B点来说的，如果相对于原点来说的话，就变成D(y1-y2+x2,x1-x...

题目难度：二星考察点：前缀和、二分 方法1：暴力算法 分析：对于的每个询问x，我们从1到n遍历整个数组，期间计算加和sum，直到在第i堆苹果满足x>=sum的时候,此时x属于第i堆苹果，输出即可。 算法实现：(0). 输入每堆对应的苹果数，用数组记录一下。(1). 对于查询的x，从第1堆开始遍历，sum表示前i堆的苹果数之和，如果sum>=x,就输出i（属于第i堆） 复杂度分析：时间复杂度：O(n^2)空间复杂度：O(n) 代码： #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5...

题目难度：二星考察点：贪心、前缀和 方法1：暴力算法 分析：我们首先可以通过一次遍历获取小易醒着时所获得的知识点分值，即时所获得的分值，由于题目要求我们只需要进行一次叫醒活动，那么我们就选择当前小易是睡着即的时刻进行往后k个枚举，循环n次即可，然后每次枚举判断其是否为知识点分的最大值。 算法实现：(0). 首先计算小易清醒时所能获得的知识点分值，记作tot。c(1). 然后从i到n进行遍历，当小易睡着时即b[i]=0时，j从i时刻一直枚举到i+k-1时刻，如果中间还有b[j]=0的情况，那么就记录加和知识点，即将时刻区间[i,i+k-1]种b[i]=0的知识点相加，然后在加上之前的清醒时的...

题目难度：一星考察点：模拟、计数 方法：模拟、计数 分析：由于整个屏幕有n列，那么如果想要得分的话就要从第1列到第n列都要有值才能得分，那么我们只需要对每个方块落在第几列进行计数，然后从第1列一直循环到第n列，判断哪列的计数值最小，最小值就是答案，输出即可。举个例子:3 61 2 3 1 1 2上例表示一共有三列，6个1*1的方块，那么我们统计一下每一列的方块数：第一列：有3个（数字1有三个）第二列：有2个（数字2有二个）第三列：有1个（数字3有一个）所以以每列的个数最小值为最终答案，即小易能够得1分。 算法实现：(0). 输入x，用一个数组用来计数a[x]++(1). 从第1列遍历到第n...

题目难度：三星考察点：二进制枚举、中途相遇法 方法1：暴力二进制枚举 分析：每个零食有放和不放两种情况，那么对于n个零食来说就有2^n种情况，我们对于这2^n种情况挨个判断每种情况的体积数是否超过背包容量w，如果没有超过背包容量就记录答案。Tips：注意结果用long long 算法实现：(0). 首先计算全部的状态all=(1<<n)。(1). 遍历这all种状态(2). 对于每种状态计算当前的体积值，如果体积值<=w，记录结果ans++(3). 输出结果 复杂度分析：时间复杂度：O(n*2^n)空间复杂度：O(n) 代码： #include <bits/st...

题目难度：二星考察点：模拟 方法：模拟 分析：按照题意模拟，然后将出现的时间全部转化为数字，上课时间-路上耽误的时间=最晚起床时间，然后根据闹钟的时间早晚找到最晚起床时间，如果将闹钟时间转化为分钟数的值小于等于最晚起床时间转化为的分钟数，那么此时这个闹钟就可以作为起床时间可用，然后找到最晚的闹钟时间。 算法实现：(0). 对于题目中所出现的时间概念，全部转化为分钟表示的数字，数字越小代表的时间越早，数字越大表示时间越晚，例如：A时B分可以转化为data = A*60+B。(1). 那么我们就可以遍历闹钟序列，然后判断是否满足如果从当前闹钟开始需要x分钟到达教室不迟到的条件(2). 如果满足...

题目难度：三星考察点：枚举、几何 方法：枚举 分析：注意一点题目要求的是平面内重叠矩形数量最多的地方,有多少个矩形相互重叠？那么对于这个题目来说，正常的循环遍历方法是无法轻易解决的，那么我们换种方法，我们想办法将这n个矩形所包含的点全部枚举出来，然后在检查看有多少个矩形包含这个点，输出包含点最多的矩形个数值即可。举个例子:现在有两个矩形，第一个矩形的左下角坐标为(0,0)右上角坐标为(6,6)，第二个矩形的左下角坐标为(5,5)右上角坐标为(10,10)，那么我们将这两个矩形所包含的点列举出来：{(0,0),(0,5),(0,6),(0,10),(5,0),(5,5),(5,6),(5,10...

题目难度：三星考察点：数学、枚举 方法1：暴力算法 分析：从1-n挨个枚举x,y，对于每个数对(x,y)判断是否x%y>=k，如果满足条件结果ans++，最后输出ans即可。 复杂度分析：时间复杂度：O(n^2)空间复杂度：O(1) 代码：#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { int n, k; cin>>n>>k; int ans = 0; for(int x=1; x<=n; x++) { for(in...