一.题目链接： 最大子序和 二.题目大意： 给出长度为 n 的序列，求长度不超过 m 的最大子序和. 三.分析： 单调队列模板题 ps：这里 q[] 存的是开区间左端点 大佬的博客：单调队列学习 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #i...

一.题目链接： Upgrading Technology 二.题目大意： 有 n 件物品，每个物品都有 m 个等级. 当物品 i 从等级 j - 1 升级到时 j 时，需花费 c[i][j]. 当所有物品都超过 j 级时，将会获得 d[j]. 三.分析： 枚举最低等级，根据贪心的原则，第 i 件物品应取大于等于 j 等级的最大收益. 但由于最低等级为 j，所以应该减去最低的收益. ps：不要忘记最低等级为 0 的情况. 四.代码实现： #include <set> #include <map> #include <ctime> #...

一.题目链接： POJ-2259 二.题目大意： 有 t 个小组排队，每个小组有若干人. 当一个人入队时，如果队伍中已有与他同一队伍的人，那么这个人就插到同一队伍人的最后，否则插到队伍最后. 先给出若***队和出队指令，要求输出出队顺序. 三.分析： 易得：在队伍中，组号相同的人肯定是排在一起的. 也就是说队伍是由组号以及该组的人数确定的. 那不妨，设置 q[0] 为该队伍的组号排列. 对每个小组 i ，再设置一个队列 q[i] 来存储组号为 i 中的元素排列. 每当一个元素 (组号为 i ) 入队时，若 q[i] 为空，说明 q[0] 中无第 i  组成员，那么该元素入...

一.题目链接： HDU-4699 二.题目大意： 模拟实现以下操作： I x：在光标后插入数 x，并将光标移到 x 后面. D：删除光标的前一个数. L：将光标左移. R：将光标右移. Q x：求 1 ~ x 中前缀和的最大值. 三.分析： 与对顶堆类似，这里用对顶栈实现. 即准备两个栈，光标前面的为 s1，光标后面的为 s2. 同时开两个数组，一个存前缀和，一个存前缀和的最大值. 详见代码. 四.代码实现： #include <set> #include <map> #include <ctime> #include &lt...

一.题目链接： HDU-4864 二.题目大意： 有 n 个机器，每个机器有 x，y.    有 m 个任务，每个任务有 x，y.   当且仅当机器的 x，y 均大于 任务的 x，y 时，该任务才可被完成，并获得金额 500x + 2y. 每个机器最多可处理一个任务. 求最多能处理的任务数，在此条件下，求出最大金额. 三.分析： 一个任务的 x 造成的最小收益为 500，y 造成的最大收益为 200. 因此，应尽可能使 x 大的任务被完成，在此情况下，使 y 尽可能大的任务被完成. 对机器和任务排序（ x 从大到小，x 相同时，y 从大到小） 对于任务 i，如果机器 j...

一.题目链接： generator 1 二.题目大意： 给出  有递推式： 求第 n 项. （） 三.分析： 这题如果直接用二进制倍增的话会 TLE. （要将 n 转换为 2 进制） 但如果十进制倍增的话，总共需要操作  次. （貌似还不错的样子） 又学会了一个新知识点（从来没听说过。。。） 出题人：这题我小时候做过（orzzzzzzzz） 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath&...

一.题目链接： POJ-1723 二.题目大意： 有 n 个士兵，每人可向上下左右移动 问使士兵移到同一行，且相邻的最小步数. 三.分析： 先分析 y：易得移动到中位数的步数最小 当加入变量 x 后，由于 y 的改变不会影响 x 的移动步数. 所以，先保证 y 的移动最小，在此情况下，使 x 的移动步最小. 对 x 排序后 假设最终的 x 起点为 s 则： x[0] 要到达 s x[1] 要到达 s + 1 ........................... x[n - 1] 要到达 s + n - 1 所花费的步数为： x[0] - 0 x[1] - ...

一.题目链接： POJ-2083 二.题目大意： 输出 ♂x. 三.分析： 没想到还可以先递归建图，最后再输出. 题目并不难，这里积累一个方法. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #include <cstdio> #inc...

一.题目链接： HDU-6609 二.题目大意： 有 n 个数，到第 i 个数时，如果 sum > m，要求在 [1, i - 1] 中删除一些数，使得 sum ≤ m. 求最少删除数的个数. 三.分析： 首先，删除的话肯定是要从最大数开始删. 即：将数组顺序排列，从大往小删除. 离散化后的权值线段树则可以实现这一点. 即：查询从数组 [1, i - 1]中，在满足 sum < m 的情况下，最多选几个数. 注意：数有重复！！！ ps：这题貌似要用错误的格式才能 A 掉，不然 PE. 四.代码实现： #include <set> #inclu...

一.题目链接： 国王游戏 二.题目大意： 国王和大臣排队，国王始终排在最前面. 每个人的左右手里各有一个数 a，b. 每 i 位大臣获得钱数为   现在对大臣重新排队，求最小化最大大臣金额. 三.分析： 按照大臣的 a * b 排序，得到的最大大臣金额是最小的. 证明： 这里选用临项交换的方法. 设第 i 位大臣的 a 为 a[i], b 为 b[i] 第 i + 1 位大臣的 a 为 a[i + 1], b 为 b[i + 1] 则，交换前两位大臣的金额分别为  和  交换后的金额分别为  和  提出公因项    得： 和   和  现在来比较交换前后最大...

一.题目链接： POJ-1328 二.题目大意： 给 n 个点（均在 y 轴上方），每个点都有一个坐标. 现在 x 轴上建立雷达，每个雷达可以扫描半径为 d 的区域. 求最少需要建立的雷达数，使得每个点都被覆盖. 三.分析： 先计算出每个点在 x 轴上对应的范围 [l, r]. 对区间按照 l 值排序. 现考虑何时加雷达以及雷达位置如何更新. 对于第 i 个点来说，雷达的位置应放在 s[i].r. 更新的话，由于前面的都覆盖了，只需要在保证在此条件下，多覆盖一个点. 即：pos = min(pos, s[i].r). 四.代码实现： #include <se...

一.题目链接： SPOJ-DQUERY 二.题目大意： 求区间 [l, r] 中不同元素的个数. 三.分析： 先考虑区间右端点 r 的情形. 设有 5 个元素{1,2,2,3,5}，每个元素最后出现的位置为{1,0,1,1,1}. 那么，区间[1,5]中不同元素的个数为 sum[5] - sum[0]. 区间[1,4]中不同元素的个数为 sum[5] - sum[1]. 其他区间同理. 现在再来考虑区间右端点变化的情形. 我们只需对每个右端点建立一颗线段树（区间求和）即可. 当然了，这里肯定要建主席树的. 详见代码. 四.代码实现： #include <s...

一.题目链接： POJ-2104 二.题目大意： 求区间第 k 大值. 三.分析： 因上午迟到，被队长强迫学习主席树..... 今天心血来潮，想学习一下主席树！！！ 因为这题是模板，具体的内容这里不再详谈，只写一些自己对主席树的理解. 主席树的建树过程 插入两个节点：1，2 （n == 4） 起初是一颗空树 然后插入第一个节点 然后第 2 个节点 可以看到每插入一个节点，就会多出一条树链. 并且，这条树链仅与前一条树链（如果存在的话）有关. ps：主席树的互异叶子结点个数为len，而不是 n. 四.代码实现： #include <set>...

一.题目链接： P1801 二.题目大意： 中文题不解释. 三.分析： 没什么可分析的，就是想存个板子. 四.代码实现： #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <bitset> #include <vector> #include <cstdio> #include <sstream> ...