原题链接：https://www.luogu.com.cn/problem/P6648题意解读：在一个n行的数字三角形中，求所有边长为k的正三角形最大值之和。解题思路：1、枚举法枚举每一个边长为k的三角形，在其中求max，然后累加，n最多3000，时间复杂度是n^4，显然超时。2、倍增和ST思想此题非常类似于RMQ问题，也就是求区

原题链接：https://www.luogu.com.cn/problem/P4155题意解读：在m个点的环上，有n个区间，且各个区间之间没有包含关系，计算从每个区间开始，最少要多少个区间能覆盖环上所有m个点。解题思路：本质上是一个区间覆盖问题！1、破环成链由于题目中是一个环，对于环的问题，在区间DP中介绍过，经典处理

原题链接：https://www.luogu.com.cn/problem/P3517题意解读：有n个连续的点p1,p2,...,pn，将这n个点分成不超过m堆，每堆点连续，每一堆都缩成一个点qi，要使得原来的点p1~ps距离qi的最大值最小（最相似），求这个相似度，并计算一共分成几堆，以及每堆缩到的点qi的坐标。解题思路：要使得若干点缩到一

原题链接：https://www.luogu.com.cn/problem/P3509题意解读：n个点，每个点上有一只青蛙每次跳到距离自己第k近的点，m次之后跳到哪个点。解题思路：1、计算距离每个点第k近的点，存入ne[N]给定一个点i，距离i第k近的点一定在长度为k+1个点的窗口内，窗口包括i并且，第k近的点只能是左端点或者

原题链接：https://www.luogu.com.cn/problem/P2345题意解读：有n头牛，每头牛都有听力v、坐标x两个属性，要计算每两头牛的max{vi​,vj​}×∣xi​−xj​∣之和。解题思路：首先想到的肯定是枚举法，需要O(n^2)的复杂度有没有优化的方法？可以采用分治法！由于是计算两头牛之间的max{vi​,

原题链接：https://www.luogu.com.cn/problem/P2415题意解读：计算集合所有子集中元素之和。解题思路：集合的特性：互异性，元素各不相同来看样例：23，可以组成的子集有空23232和3都出现2次再比如：123，可以组成的子集有空12312 13231231,2,3各出现4次由于在集合中

原题链接：https://www.luogu.com.cn/problem/P7167题意解读：从喷泉任意一个圆盘倒水，水流经的圆盘直径必须递增，水最后流到哪个圆盘。解题思路：1、枚举法有30%的数据范围在N<=1000,Q<=1000，因此枚举也可以得到30分。可以通过单调栈预计算每个圆盘后面第一个直径更大的圆盘位置Next[

原题链接：https://www.luogu.com.cn/problem/P1226题意解读：快速幂模版题。解题思路：1、分治法要计算a^b，可以对b分情况讨论：如果b是偶数，即b=2t，a^b=a^t*a^t如果b是奇数，即b=2t+1，a^b=a*a^t*a^t很容易用递归实现100分代码：#include<bits/stdc++.h>usingnamespa

原题链接：https://www.luogu.com.cn/problem/P1966题意解读：计算两个序列∑(ai​−bi​)^2的最小值，对10^8-3取模。解题思路：1、贪心思路要使得两个序列对应位置元素之差的平方和最小，必须满足两个序列相对排序是一致的，什么意思？设a序列有两个元素：a1，a2，b序列有两个元素b1，b2当a1<a2，b

原题链接：https://www.luogu.com.cn/problem/P1908题意解读：求序列逆序对数。解题思路：1、暴力法对于每一个数，寻找后面有多少数比其小，或者采用冒泡排序，交换的次数即逆序对的个数，复杂度为O(n^2)2、归并排序法在归并排序过程中，会进行有序序列的合并，设两部分连续的有序序列为a[s1,

原题链接：https://www.luogu.com.cn/problem/P1177题意解读：归并排序模版题。解题思路：第一步：确定分界点。mid=(l+r)/2第二步：排序。对左右两边递归排序第三步：归并。合并左右两边排序好的内容关键在第三步：通过双指针对两个有序数组进行合并100分代码：#include<bits/std

原题链接：https://www.luogu.com.cn/problem/P1714题意解读：求长度不超过m的最大子段和解题思路：1、暴力法设a[N]表示原数组，s[N]是a[N]的前缀和，对于每一个元素s[i]，计算其与前m个元素之差，取差值最大值，用代码表示：for(inti=1;i<=n;i++){for(intj=i-1;j>=i-m

原题链接：https://www.luogu.com.cn/problem/P2880题意解读：在若干个不定长区间里，求区间最大值与最小值之差解题思路：对于区间求最值，通常有几种方式：1、暴力法，通过枚举所有的区间来计算区间最值2、单调队列，针对区间长度固定的情况3、ST表，针对区间长度不固定且元素不会发生改变的

原题链接：https://www.luogu.com.cn/problem/P1886题意解读：单调队列模版题。解题思路：采用双端队列维护单调的序列，单调队列三部曲：1、去头，当窗口内元素个数超过k，队头出队2、去尾，当要加入的元素会破坏单调性，队尾出队3、入队，将元素的下标存入队列每一次入队后，队头元素即为窗口最

原题链接：https://www.luogu.com.cn/problem/P3467题意解读：用长方形的海报覆盖建筑的侧面，最少需要的海报数如上图，左边最少需要3张，右边最少需要4张解题思路：可以看出，需要海报数与建筑宽度无关，只与高度有关。当建筑高度与之前不同时，肯定需要增加一张海报；当建筑高度与之前有相同

原题链接：https://www.luogu.com.cn/problem/P3143题意解读：找到两个不相交的最长连续序列，使得序列最大值和最小值差不超过k，求两个最长的序列长度和。解题思路：先将所有数从小到大排序，记为a[]要找到两个不相交的最长连续序列，可以采用下面技巧：设b[i]表示i之前“差值在k之内的连续

原题链接：https://www.luogu.com.cn/problem/P4653题意解读：选中的灯泡中，某一类较少的总权值减去灯泡数量所得到的收益最大值。解题思路：注意，此题关键是：要使得较少的收益最大化1、要最大化，意味着每次应该选择尽可能大权值的灯泡2、要使A、B类中较少的收益最大化，意味着每次应该优

原题链接：https://www.luogu.com.cn/problem/UVA11572题意解读：本质上是要计算最长连续不重复子序列的长度，典型的双指针应用。解题思路：通过双指针来枚举子序列，右指针指向的元素每次记录元素出现的次数，可以借助hash数组h[]如果枚举到的元素出现次数超过1，则表示左、右指针之间的子

原题链接：https://www.luogu.com.cn/problem/P2216题意解读：在矩阵中找n*n正方形里最大值和最小值差值的最小值。解题思路：1、枚举法直接枚举所有n*n的正方形的位置，然后在遍历求最大值、最小值，复杂度为O(n^4)，显然不能通过。2、二维单调队列既然是求正方形范围内的最值，看起来是

原题链接：https://www.luogu.com.cn/problem/P2032题意解读：求滑动窗口内的最大值，典型的单调队列应用。解题思路：单调队列的三部曲：1、去头。已存入的元素个数超过k，则去头。注意队列里存的是元素下标，只需要用当前下标减去队头元素来判断即可。2、去尾。根据单调队列的单调性，如果

原题链接：https://www.luogu.com.cn/problem/P1950题意解读：在一张n*m个格子的纸上，从没有画过的格子中剪出长方形的方案数。解题思路：1、暴力做法枚举所有的子矩阵O(n^4)，然后用二维前缀和计算子矩阵的和，通过和来判断子矩阵是否全部是'.'。2、优化做法针对每一行进行处理，计算包

原题链接：https://www.luogu.com.cn/problem/P2866题意解读：每个牛能看到的右边比他矮的牛，直到有比他高的挡住为止，因此只用找每个牛右边第一个比他高的牛的位置即可计算中间比他矮的有多少。解题思路：典型的单调栈应用，注意，常规的单调栈可以用来：1、找每个数左边第一个比他小的数的

原题链接：https://www.luogu.com.cn/problem/P4147题意解读：找到一个只包含'F'的最大的子矩形。解题思路：方法1：设R为0，F为1，先计算二维前缀和，再枚举所有子矩形左上角(x1,y1)、右下角(x2,y2)，计算子矩形的区间和，更新最大值，只能得到部分分。方法2：对于二维矩阵每个点，定义三个属性：h[][]

原题链接：https://www.luogu.com.cn/problem/P1115题意解读：最大连续子序列的和。解题思路：DP的做法可参考：https://www.cnblogs.com/jcwy/p/18144124也可以采用双指针来枚举：i从1开始，j=i用j来枚举连续序列，如果已有序列和+下一个a[j]>=下一个a[j]，那个j一直++，累加序列和如果出

原题链接：https://www.luogu.com.cn/problem/P1638题意解读：在n个数中，选出a、b两个端点，使得a~b之间不同的数字为m，且b-a最小。解题思路：要寻找最小的包括所有数字的区间，可以采用双指针算法1、设i，j分别是左右指针2、如果当前区间内不同数字个数不到m，j往后移3、记录数字个数到m时