一、题意 某个城市有n个湖，每个湖初始装满水。在接下来的m天，每天要么不下雨，要么会恰好往一个湖里下暴雨。若下暴雨时，该湖已经装满水，则会发生水灾。你是一条神龙，你可以在不下雨的日子里喝光一个湖的水（也可以不喝）。给出接下来m天是否下雨以及会往哪些湖下暴雨，为了不引起水灾，你应该在不下雨的那几天里如何喝水？ 二、解析 先来分析一下，是否会存在下暴雨时湖里正好没水的情形呢？答案是不会，因为n个湖初始都是装满水的，而我们并不会闲着没事干去喝水，因此我们总是在知道有一场暴雨会往一个装满水的湖里下时我们才会去喝干这个湖。 然后，如果一个装满水的湖在某一天被下了暴雨，那么我们必须在这一天之前喝干这个湖，...

一、题意 输入n、m、k，你可以根据m得到一个长度为n的序列a[maxn]（即a[maxn]已知）。现在要你在a[maxn]中找到一个包含 1~k 这k个整数的最短连续子序列。输出符合要求的最短连续子序列的长度。无解时输出无解。 二、解析 看到连续子序列，马上就觉得可以用滑动窗口或者说双指针的方法来做。 同时还需要用一个 cnt[maxk] 来存放当前“窗口”中 1 ~ k 的数字分别有多少个。通过 j 递增来滑动窗口，同时当 i 所指向的值不属于 1 ~ k 或者它所指向的值在窗口中已经有多个时，可以将其弹出窗口（以使得窗口尽可能小）。然后通过对cnt数组中1~k的元素是否有值来判断当前窗口...

一、题意 输入n、q（n、q<=100000），然后输入一个长度为n的递增序列A（有重复元素）。之后是q次询问，每次询问输入两个数l、r，你需要输出在区间 A[l...r] 中出现次数最多的元素的出现次数。 二、解析 为了不超时，每次询问我们需要在O(1)~O(lgn)时间内作出回答。这就让我们想到有一个在O(1)时间内得到区间最值的算法：RMQ算法。 在本题中，就是要在一个cnt数组中得到某个区间中的cnt最大值。 因此我们很自然地需要对原序列进行统计，得到一个“把相同值聚类”后的新数组，为了方便起见，还需要维护每一个值在原数组的左边界和右边界，因此这里我用一个结构体来保存，即代码中的...

一、题意 给你n条线段（线段端点为整数，n<=100000），输入保证线段间没有包含关系，且保证有解。现在要求将每条线段截取长度为1的一小段，使得截取后的所有线段之间的空隙数目最少。输出空隙的最少数目。 二、解析  一开始用了一种比较复杂的方法：将所有线段按右端点排序后，每个线段尽量靠左边选取长度为1的片段，并维护一个remain值，表示该长度为1的片段右侧的空余长度（也就是可以动态右移多少长度）；还要维护一个cur值，表示当前已经选取的1片段的最右端位置。然后每次当发现当前线段与上一线段的1片段（cur值）之间有空隙时，首先检查remain能否填充这个空隙，若能，则将该空隙填充；若不能...

一、题意 输入n条线段，线段之间没有包含关系，要求你把每条线段截成原来的一条子线段，使得改变之后的所有线段长度相等且互不相交（端点可以重合）。求每条线段的最大长度，并用分数表示。 二、解析 刚看到要用分数表示时，我是很懵的，但后来仔细一想，其实这只是出题人的虚晃一枪，我们首先求出小数解，然后再转变为分数即可。 如何求得小数解呢？我们很容易发现，这道题直接求出最大解很难，但是判定某个解是否符合题意是容易的，因此这就很容易让我们想到之前讲过的“二分答案”法。之前的二分答案是二分整数值，这道题只要二分double值即可，这样其实简单的多，不需要许多细节处理，唯一要注意的就是double值之间不能直接...

一、题意 输入1 ~ n 的一个排列（n<=500），每次可以交换两个整数，输出至少要用多少次交换，就可以把排列变成一个1 ~ n 的环状排列。 二、解析 由于n比较小，因此暴力模拟法即可。首先枚举目标排列，总共 2 * n 种（以每一个下标作为开头1、顺时针和逆时针），然后对于每一个目标排列，计算从原始排列a[maxn]到目标排列需要交换的次数。然后取所有次数的最小值即为答案。 为了快速定位原始排列中某些元素的位置，我们可以用一个额外的pos[maxn]来记录元素位置，然后每次模拟交换元素时，同时交换相应的pos数组中的值即可。 三、代码 #include <iostream&g...

一、题意 有n个工作（n<=800000），只能串行进行，已知每个工作的用时need[i]和截止期限ddl[i]，问最多能完成多少个工作？ 二、解析 这个是超典型的工作安排贪心问题。 一个比较简单的版本是给出工作的确切开始时间和结束时间，这种问题就是典型的区间限制问题，我们按照ddl排序，然后先完成ddl早的任务即可。 但是在这道题中，任务的开始时间是可以任意决定的（只要结束时不超过ddl期限），因此我们还应该结合考虑另一种贪心：即让短的任务优先。 也就是说，对于一个给定的时间点之前，我们需要先执行短的任务，这样才能让任务完成数量最大化。这里需要用一个优先队列来存放到当前时间点为止，所有...

一、题意 给出一个n个点m条边的连通图，每个点的度数不超过k（k为一个奇数），要求给每个点进行1...k的染色，使得相邻点颜色不同。 二、解析 首先按照题目的意思求出k，并且题目已经告诉我们k染色一定有解，因此接下来就是放心的dfs染色即可。需要维护一个col[maxn]数组，0表示没有染色。这个col数组除了存放每个点的颜色，还充当了vis的角色。dfs的出口就是检查是否和周围已经染色的点重色了，没有则进行递归染色即可。 三、代码 #include <iostream> #include <vector> using namespace std; const int ...

一、题意 输入n、d（d<n<100000）。然后输入一个n位的数字，要求你从中删去d个，使得剩下的数字最大。 二、解析 先给出我一开始想的一种错误的思路：即每次都删去最小的、位置靠前的数字。这个乍看一下很有道理，但实际上是错误的，因为这个没有从全局考虑。比如一个231这个3位数字，只能删去一个，则显然我们要删除的是2而不是1。 通过上面这个例子我们也能发现，实际上真正的贪心思路应该是反过来想的，即每次从开头找一个最大的数字进行保留。这样对于231，由于我们最终要保留2个数字，因此我们逐个挑选，先选出最大的3，然后再选择1。 于是我们就可以用O(n)时间从头到尾扫一遍，每次在一个区...

一、题意 输入两个等长的字符串S、T，你的任务是用最少的操作步数把S变成T。S由0、1、?构成，T由0、1构成。可用的操作有：  把一个0变成1 把一个?变成0或1 交换两个字符的位置输出最少步数。若没有办法则输出-1.  二、解析 这里的操作最关键的就是1如何变成0。我们用 x->y 表示x需要变成y。实际上只可能通过交换 1->0 和一个 0->1 得到。因为交换 1->0 和 0->0 就会使得被交换得数对变成 1->0 这相当于没有解决问题。 因此我们统计 1->0 和 0->1 得个数，分别记为one2zero、zero2one。 若z...

一、题意 给n个字符串（n<=1000，n为偶数），要你找一个最短的字符串S，使得恰好有一半的串小于等于S，另一半大于S。如有多解，输出字典序最小的解。 二、解析 第一步操作是显然的：排序这n个字符串，然后取出最中间的两个，假设为a，b。下面就是要少一个字符串res使得res>=a，res<b。 网上有许多做法是通过各种if语句进行判断，由于细节很多容易出错，我这里介绍另一种稍微暴力一些的方法。 即逐位增加res串，然后维护res串使其不断向<=a和>b的结果上靠拢。最终就能得到答案串。具体见代码。 三、代码 #include <iostream> #...

一、题意 给定n个物品的大小a[maxn]，每个背包的容量M，并且每个背包最多只能装2个物品。输出装下所有物品至少需要的背包数目。 二、解析 一看就是典型的乘船问题（贪心问题中的一种）。 由于只能装2个物品，因此我们首先将物品按大小排序，然后通过双指针指向一头一尾。头指针指向的是当前最小的物品，我们总是贪心地希望它和尽量大地物品装一起，也就是尾指针指向的物品。若这两个物品加起来可以装进背包，则就这么装（因为这是最赚的装法），然后指针分别都向中间移动，ans++；若装不下，则对于大的那个物品来说，连最小的都不能和它一起装下，那么它必然只能自己一个人装一个背包，所以尾指针向前移动，头指针不动，an...

一、题意 输入一个n*m的矩阵，'.'表示空地，'#'表示障碍物，要求你对于每一个空地，求出以它为右下角的空矩形的最大周长。然后统计每个周长出现了多少次。 二、解析 看到题意，应该就能回想到一些之前做过的题目：找最大空矩形面积。而这道题要找的是最大周长。其实是异曲同工的，也就是先将原图转化为n个直方图，然后对每个直方图通过单调栈就最大面积的矩形。这样的方法总用时O(n*m)，不会超时。 而在本题中就是要用单调栈求最大周长，并且是要对每一个空地都求一个最大周长的空矩形。在直方图中从左向右遍历时，设当前列为i，对应的矩形右下角即为(i, 0)，我们要找的就是矩形的左上角（c, h）使得周长 2*（...

一、题意 每组数据中输入一个宽度为n的平面直方图。要求你输出直方图中面积最大的矩形的面积。 二、解析 超经典的直方图中求最大矩形问题。从0开始从左向右遍历直方图，并维护一个单调栈。单调栈里存放到当前位置为止的一个单调递增的直方图高度，栈里实际存放的是下标。这样就可以在O(1)时间获取离当前位置最近的一个比当前值小的值的下标位置。通过下标只差可以算出当前左侧最大矩形的宽度，高度则就是栈顶元素值。这样就可以求出当前矩形的面积，然后维护面积的最大值到ans即可。 单调栈的维护方法：  先用while语句弹出栈顶中比当前遍历到的值还大的元素。 将当前遍历到的值压入栈中。  三、代码 #include ...