原图是这样的当我们 输入 4 2 1 时 我们就是要找 从4 到 2 比 1 大的节点数，我们可以转换成这样的树，红色代表我们新加入的节点，显而易见，4号节点比 1大 ， 2号节点比 1大 答案为2 那我们就可以转换为把要查询的路径用这样的方式插入，实力太弱的我还是对数据结构掌握不好。~~我们用f[i][j] 代表当前节点能够买 2^j 个东西的节点是哪个？递推式f[i][j] = f[[f[i][j-1]][j-1] 比如我们从第i个节点买四个东西的话 那么就是 从第i个节点先买2个到达相应的节点再买4个我们首先确定每个节点第一个比他大的节点是哪个？然后根据递推式确定以后的f数组，再利用df...

单调队列问题a[l],a[l + 1],a[l + 2]....a[r-2],a[r-1],a[r],当这个区间往右移动的时候，只会a[l]离开窗口，a[r + 1]进入窗口，那么我们只需比较这个即可典型单调队列题目，我们队列左端存的是当前最优解，当窗口往右移动时，我们看这个队列左端是不是已经不再 k 这个范围内了，如果是的话我们让他出队，然后我们看 a[i] 也就是当前新加的元素 ，如果他比队列中的某些元素小的话，那么他就可能成为后面的最优解，那么我们往前找到一个合适的位置来存储他，也就是他前面的元素都比他小，后面的元素都比他大。 注意队列中存的是他的下标 l = r = 1 开始 ,让第一...

注意点： set集合自动排序 set集合自动排序 set集合自动排序 自己也太弱了吧 以后还是要多多做题啊！！ 原来数学推导真的真重要，在没有思路的情况下从最简单的情况开始推导，逐步发现规律，这真的是太重要了吧。 迭代器 写法 一定要记住啊， 反证法真的太强了吧！ 假设 第 k 条边已经选好，那么与这K个点相邻的点事同进退的原则！选择这个边之后，我们将这个边连接点两点的左右两点都删掉，再加入一条 k - 2 到 k -1 和 k + 1 到 k + 2 的边 !!! 再次惊叹下这个题的巧妙啊！#include<bits/stdc++.h> #define pr printf #...

用到的思想：分组思想 首先考虑只有两个序列的情况 a1 a2 a3 ...... an b1 b2 b3 ...... bn ps : a 数组是提前排序的 从小到大 把所有的情况枚举出来 b1+a1, b1+a2, b1+a3,.... b1 + an b2+a1, b2+a2, b2+a3,.... b2 + an ................................. bn+a1, bn+a2, bn+a3..... bn + an 第一步 选出最小的数 毫无疑问 最小的是在第一列当中，选出来之后，再选第二小将选中的那个数后面的那个数加入到选择方案中 比如 第一步我们选择...

超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品（即当天di<=0 ）不能再卖。 求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。输入格式 输入包含多组测试用例。 每组测试用例，以输入整数N开始，接下里输入N对pi和di ，分别代表第i件商品的利润和过期时间。 在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。输出格式 对于每组产品，输出一个该组的最大收益值。 每个结果占一行。数据范围 0≤N≤10000,1≤pi,di≤10000 输入样例： 4 50 2 10 1 20 2 30 1 7 ...

利用前缀和思想 以及DP首先利用前缀和求出dp数组 dp[i] 代表 i到n 这个区间内 长度为k 的序列的和的最大值 然后再依次枚举 从k 到 n- k 区间内的 长度为 k的区间的最大值 也就是 sum[i]-sum[i-k] 然后再加上 i 到 这个区间内的最大值 每次取最大值主要知识点 前缀和 ： sum[i] = a1+a2+.....+a[i] 求[ l , r ]区间内的和的操作 为 sum[r] - sum [l - 1]推导如下sum[r] = a1 + a2 + a3 + ......+ a[r]sum[l - 1 ] =a1 + a2 + a3 +... a[...