这一块的问题大多都具有单调性，大部分有单调性的问题都能用二分来解决，主要的解题方法是二分 + 验证（计算，求和，01），但主要的难点在验证，需要多练习，多思考。  跳石头（noip2015）  题目描述：一年一度的“跳石头”比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终...

二分模板  注意事项： 1.要注意左右边界都在要查找的区间的旁边（例如区间从1 - n，二分的区间就应该从 0 - n + 1，因为我这种写法就是用l + 1和r进行判断的，所以如果不这样做的话边界会被忽略掉）；2. 查找的序列必须是有序的  找 <= x 的第一个数 int find1(int x) { int l = 0,r = n + 1; while(l + 1 < r) { int mid = (l + r) >> 1; if(a[mid] <= x) l = mid; else r = mid; } return l; }  找 >= x的第一个...

石子合并 题目描述：  将n堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。 请编写一个程序，读入堆数n及每堆的石子数，并进行如下计算： 选择一种合并石子的方案，使得做n-1次合并得分总和最大。 选择一种合并石子的方案，使得做n-1次合并得分总和最小。  整体思路：（假设是求最大值）我们去枚举每个小区间的分隔点k，f[i][j]表示的是从第i个数到第j个数合并能够获得的最大值，f[i][j] = max(f[i][j],f[i][k] + f[k+1][j] + sum[j] - sum[i - 1]),f[i]...

分组背包问题 题目描述： 有 N 组物品和一个容量是 V 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij ，价值是 wij ，其中 i 是组号，j 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。 整体思路 由于每组至多选择1个物品，假设这组有n个物品，那么就有n + 1种选法。假设假设f[i][j]表示的是前i组物品，在j的体积下最多能装下多少的价值。故f[i][j] = max(f[i][j],f[i][j - v1] + w1,.......,f[i][j - vs] + ws;实质上还是一个01背包...

滑动窗口（单调队列） 整体思想：用一个q数组存储下标，当队尾元素下标减去对头元素下标已经大于整体的容量的时候，对头出队。若准备加进来的元素比队尾元素大（假设该队列大的在前面）就让队尾元素出队。 题目描述：  给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。  CODE: #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 6; int a[N]; int q[N]; int main() { in...

01背包 题目描述： 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i件物品的体积是 vi，价值是 wi 。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。 整体描述 背包只有两种状态，放和不放。 所以定义一个数组f[i][j]来表示前i个物品在j的体积下最多能装上多少的价值。 具体实现步骤 首先枚举i和j，若枚举的j大于当前物品的体积，那就取max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]) 如果这个物品塞不下，就只好取f[i][j] = f[i - 1][j] 朴素二维数组代码 ">usin...

优先队列/堆 优先队列又名二叉堆，是特殊的二叉树，二叉堆有两种，大根堆和小根堆。 两种操作： 插入某一个元素：先将该元素插在数的最底部，其结构始终满足完全二叉树，然后根据完全二叉树的结构去调整插入元素的位置 删除堆顶元素：先将最后一个元素插到堆顶，然后根据完全二叉树的性质将堆顶元素不断调整。 priority_queue 默认是大根堆 小根堆：priority_queue <int,vector,greater > q; 大根堆：priority_queue <int,vector,less >q; 手动实现：以《合并果子》为例 ">using namesp...

------------------------------------------------------------------------------------------------Description-------------------------------------------------------------------------           ------------------------------------------------------------------------------------------------Solution-----...

#给牛客的问题反馈和建议#

----------------------------------------------------------------------找>=x的第一个位置-----------------------------------------------------------------------------------------------    while(l < r) { mid = (l + r) / 2; if(a[mid] >= x) r ...

-----------------------------------------------------------------------------先序遍历-------------------------------------------------------------------------------------------------   题目大意：         整体思路：分析不同遍历方式的序列的时候要时刻想着遍历的顺序，先：根左右，中：左根右，后：左右根   因为是求先序遍历，所以去找后序遍历里面的最后一个元素先输出，因为最后一个元素就是根。   然后递归在中序遍历和...

题目整体描述：            -------------------------------------------------------------------------------贪心策略--------------------------------------------------------------------------------------------------   我们需要达到的目的：假设用sum[i]表示序列的前缀和，那就需要找到两个点i和j使得sum[j] - sum[i]的值最大；   于是就联想到之前做过的一个题目：         对于图片中的这...

永远只考虑当前这一层的情况      #include<bits/stdc++.h> using namespace std; void solve(int n,char start,char towards,char zhong) { if(n == 0) return; solve(n - 1,start,zhong,towards); printf("move NO.%d from %c to %c\n",n...

--------------------------------------------------------------------------归并排序--------------------------------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; int a[10000],b[10000]; void hebin(int l,int mid...