题意：对于一段空白的木板，每次可以选取连续的一段涂上任意中颜色，问将木板涂至给定颜色需要的最少次数。 思路:区间dp。原问题：将木板全部涂色完成需要的最少次数。子问题：将木板的连续某一段涂完需要的最少次数。记：dp[i][j]表示将木板的第i块至第j块涂成指定颜色需要的最少次数。 区间dp考虑先枚举长度；当块的长度为一时，只要涂一次，即dp[i][i]=1；当木板长度大于一时：若端点的两块颜色相同，可认为在涂一端时顺带涂了另一端，所以 dp[i][j]=min(dp[i][j-1],d[i+1][j])；若端点的两块颜色不相同，则可以在端点间枚举端点，即先涂第i块到第k块，再涂第k+1块到第j...

动态规划 一道很正的动态规划题，直接进行分析：原问题：选取所有卡片到最后一个格子是能够得到的最大分数；子问题：四种卡片分别选i,j,k,l张时能得到的最大分数；记dp[i][j][k][l]为四种卡片分别选出了i,j,k,l张时能够取得的最大分数。 有的人可能会按“前i个格子如何选取卡片”类似这样的套路分析，这里要注意的是，当每种卡片的个数确定了以后，走到的格子也是确定的，同时题目还确保了使用所有的卡片可以恰好到达最后一个格子，这就更没有必要讨论“前几个格子了”。 代码： #include <iostream> #include <queue> #include &lt...

单调栈 本题要求找出最大矩形的面积。从基本概念入手，给定长（本题也可以说“高”）和宽便可以确定一个矩形的面积，所以我们的任务便是找到高和宽。 首先，要尝试所有的区间很显然是不可能的；可以发现对于每一段区间，矩形的宽都可以用a数组的前缀和求出来，所以我们的任务重心转移到了矩形的高上。 求高便是求一段区间内h的最小值，这里容易想到单调队列栈。很显然此处不能用单调队列处理，因为并没有指定矩形的宽占多少区间，所以采用单调栈处理。单调栈：求数组某个位置的值在哪个最大区间（相邻）是最值。此时只要找到每个位置的在哪个最大区间是最小值即可，因为一旦超过这个区间，要么是超过了边界，要么是存在一个h[i]小于该高...

前缀和 首先说明一下题目中的要求值的式子的意思：对于所有的区间[l,r]（其中1<=l<=r<=n），求每个区间点对应的数的和（即a[i]的和），将其乘以区间的长度对应的权值（即w[r-l+1]），取和并输出。 理解了上述之后，毫无疑问此题需要用前缀和，解决此题有两种处理途径：枚举点和枚举区间长度。枚举点：通过计算每个点在不同长度的区间中的贡献，进而求得该点在所有长度的区间中的贡献，可求得所有点在其所有出现过的区间中的贡献。枚举区间长度：通过计算在给定长度下的一个区间中其中所有点的贡献，进而求得在给定长度下所有区间中所有点的贡献，可求得在所有长度的区间中所有点的贡献。由于两种...

首先，考虑一下常规思路，每次将操作数和与操作数相连的点的权值都加一，然后计算值。显然这种思路的会TLE。不过我们可以发现，这种思路其实不止适用于树，还适用于图。如此我们便要思考，就本题而言，树与图有什么区别。树型结构为一对多的关系，不像图的多对多，这使得我们可以从树中找到节点的祖宗及后代，因此我们要从这里入手。 先前常规思路的超时，主要原因是在每次操作中，计算了所有与操作数相连的点，时间复杂度为O(n)，我们需要在O(1)的时间复杂度内完成此操作。在树型结构中，一次操作要计算指定点、其父节点和其所有子节点，而一次对指定点的操作会影响到其父节点、子节点和其祖父节点、孙子节点（当计算与其相邻的点权...

递归 数据范围较小，直接递归解决。考虑将当前蛋糕分成left块：当left==1时，返回长与宽的比值；当left>1时，若沿着当前蛋糕的某一条边切割总共有n/2种切割方法（考虑对称性），沿着长和宽总共有(n/2)*2种切割方法；对于当前蛋糕的每一种切割方法，递归考虑其切割后的两个蛋糕，得到二者切割后能够生成的小蛋糕中长宽比值最大者（从一种切割方法生成的n块蛋糕中找到长宽比值最大的一块）；对于当前蛋糕的所有切割方法，从中选出每种比值最大的小蛋糕的最小比值，返回该比值。 值得注意的是，对于递归中生成的所有最小蛋糕，不能一味取其最大比值或最小比值；要分清楚递归过程中，哪些步骤是在选择切分方法（...

数论。 题意：给定一个正整数n，要求找到所有在[0,n)之间的整数x满足：%n=1。 思路：%n=1可以写作=nk+1，即：(x-1)(x+1)=nk。拆分x与k得到：(x-1)(x+1)=(n1k1)(n2k2)，所以有：x-1=n1k1、x+1=n2k2。接下来当n1<=n2时，可以在时间内枚举n1，同时计算出n2并枚举k2，计算出x，判断是否存在整数k1。当n1>n2时同理枚举n2。此时要注意x<n的条件。 最后将两种情况的答案合并排序并去重后输出即可。 代码： #include <iostream> #include <queue> #incl...

动态规划。 根据题意直接构造出树比较难，所以采用动态规划的方法。 记ans[i]表示当树有i个结点时所求花费的最大值。假设在考虑有i个结点时，我们已经知道了结点数小于i时的ans，则可以通过ans[i]=max(ans[i],ans[j]+???)得到答案，其中j为结点数为i时所有可能的重儿子，也就是题目中所说的“官员的心腹”。现在只需将“???”求出来。 理解“???”是什么意思，不妨先看看转移方程中缺什么。在选定了重儿子的同时其贡献也求了出来，即ans[j]，现在需要安排轻儿子：求出轻儿子的贡献同时确保其小于重儿子。这就要求将除重儿子以外的结点分成若干组，每组结点数不能大于j。因此，我们再...

区间dp。 首先，由题意，每行取数独立，因此可以分别分析每一行的情况。 其次，基础的区间dp。原问题：从序列第1个数到第m个数取出后的答案子问题：从序列第i个数到第j个数取出后的答案记dp[i][j]表示从序列中第i个数到第j个数取出后的答案，得到转移方程：dp[i][j]=max(dp[i+1][j]+ar[i]* ,dp[i][j-1]+ar[j]* )，其中len为区间的长度。简单说明一下为什么这里是而不是 。当区间长度为1时，意味着我们只取一个数，但是它是数列中最后取走的数，因为区间dp是从短到长考虑的，直接考虑完整的区间就不是dp了；当考虑区间长度为2时，新添加的数是倒数第二个被取走...

递推 要求所有高度为n的平衡树中不平衡度的最大值，没必要考虑所有的树，只要想办法构造出一棵不平衡度最大的树即可。要想不平衡度最大，只要根节点的左右子树节点数差值最大即可。若不选取根节点，则高度上限会减少，得到的树不平衡度不是最大。而要使左右子树节点数差值最大，只要使左子树节点数最大、右子树节点数尽可能小即可。 左子树节点数最大即排满，为 -1。考虑右子树，即考虑在n和d的限制下节点数最少的平衡树，这里采用递推的方法。记f[n]为高度为n的节点数最少的平衡树，其左右子树高度差不超过d。要构造高度为n的树，可以进行如下操作：新建一个节点，其左子树为高度为n-1的平衡树，其右子树为高度为n-1-d的...

dfs优化 题意：给定一个n个点、m条边的无向图，要找出图中大小为s的完全图的个数。 思路：先看一个常规思路，不过会TLE：从所有节点开始都进行一次dfs，将不在集合中并且能与集合中的点形成完全图的点加入集合，集合大小等于s时ans加一，逐层返回。为什么所有节点都要进行一次dfs？因为题目没说图一定是连通图。不过此算法要进行多次去重，例如当s=2时，1->2和2->1的两次dfs中得到的集合可能相同。所以鉴于上述考虑，我们只选择1->2这一次得到的集合而放弃2->1得到的集合，而如何实现已经暗示得很明显了，就是要从较小点走向较大点。将原来的无向图改为有向图，从较小的点指...

矩阵快速幂。 题意：一组数的递推公式如下：F(1)=a,F(2)=b,F(n)=F(n-1)+2* F(n-2)+ (n>2)。现要求出该序列中的第n个数。 思路：由于n的值太大，直接递推不行，这里采用构造系数矩阵的方法。本人目前的理解：当以递归得到数的效率太低时，可以研究递归过程，拆分或者合并公式中的数，研究两个过程的数之间的关系并建立一个矩阵，建立系数矩阵以系数矩阵的幂代替递归。诸如此类的还有求第n个斐波那契数。观察发现递推过程中的数有：F(n),F(n-1),，而下一个递推过程中的数有：F(n+1),F(n), ，我们要想办法通过第一个过程得到第二个过程。发现第二个过程需要 ，因此...

数学+前缀和。 对于序列中的每一个数，采用二进制表示，以此判断X在每一位的值。 先考虑区间[1,n]，假设这n个数有t个数的第j位为1，则有(n-t)个数的为0。接下来判断X在第j位应该是0还是1。已知异或的运算规则：相同为0，不同为1。如果要使求和得到的值尽可能大，那么X与每一个数的第j位异或运算后得到的1应该尽可能多。所以比较t与n-t的大小关系即可，若t>n-t，则1较多，X的第j位应该为0；反之则为1。有一点需要注意，题目要求在求和值尽可能大的同时，X的值要尽可能小，所以当0与1一样多时，X的第j位应为0。其它位以此规则可算出，最后累加即可。 当考虑区间[l,r]时，采用同样思路...

离散化 + 树状数组 先看一下一般求逆序数的思路：设置vis数组，表示数字在前面遍历过程中出现的次数；遍历数组，vis[ar[i]]加一，然后求出大于ar[i]的数在前面出现的次数并加入到ans中。当序列数字过大是可以采用离散化处理，因为只需要知道大小关系即可，不必知道到底大了多少；对于求大于ar[i]的数出现的次数，可以采用树状数组求和：sum(vis[maxx]-vis[ar[i]])。 再回到本题，要求出所有区间的逆序数的总和，换一句话说就是求出所有逆序对所在区间数的总和。当(i,j)为逆序对时，其对ans的贡献为i* (n-j+1)（考虑到树状数组，下标从1开始）。当(i_1,j)(i...