The__Flash

-------...

2018 - 2019 寒假训练(29) POJ(2) SDNU ACM-ICPC 2019 Training We(1) UVA(3) ZOJ(3) 博弈(3) 容斥原理(3) 未归档(135) 模拟(3) 牛客(1) 算法竞赛入门经典(7) 莫队算法(2) 贪心(3) 题解(4)

/ 注册

全部文章 / -------------各大OJ------------- （共54篇）

最大子序和（算法竞赛进阶指南 P53，单调队列）

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

2019-08-05

0 449

Team Queue （POJ - 2259 ，队列模拟）

一.题目链接： POJ-2259 二.题目大意：有 t 个小组排队，每个小组有若干人. 当一个人入队时，如果队伍中已有与他同一队伍的人，那么这个人就插到同一队伍人的最后，否则插到队伍最后. 先给出若***队和出队指令，要求输出出队顺序. 三.分析：易得：在队伍中，组号相同的人肯定是...

2019-08-03

0 473

Editor （HDU - 4699，对顶栈模拟数据结构）

一.题目链接： HDU-4699 二.题目大意：模拟实现以下操作： I x：在光标后插入数 x，并将光标移到 x 后面. D：删除光标的前一个数. L：将光标左移. R：将光标右移. Q x：求 1 ~ x 中前缀和的最大值. 三.分析：与对顶堆类似，这里用对顶栈实现. 即...

2019-08-02

0 459

Task （HDU - 4864，贪心）

一.题目链接： HDU-4864 二.题目大意：有 n 个机器，每个机器有 x，y. 有 m 个任务，每个任务有 x，y. 当且仅当机器的 x，y 均大于任务的 x，y 时，该任务才可被完成，并获得金额 500x + 2y. 每个机器最多可处理一个任务. 求最多能处理的任...

2019-08-02

0 748

generator 1（2019牛客暑期多校训练营（第五场）B，十进制矩阵倍增乘法）

一.题目链接： generator 1 二.题目大意：给出有递推式：求第 n 项. （）三.分析：这题如果直接用二进制倍增的话会 TLE. （要将 n 转换为 2 进制）但如果十进制倍增的话，总共需要操作次. （貌似还不错的样子）又学会了一个新知识点（从来没听说...

2019-08-02

0 714

SOLDIERS（ POJ - 1723，中位数 + 构造）

一.题目链接： POJ-1723 二.题目大意：有 n 个士兵，每人可向上下左右移动问使士兵移到同一行，且相邻的最小步数. 三.分析：先分析 y：易得移动到中位数的步数最小当加入变量 x 后，由于 y 的改变不会影响 x 的移动步数. 所以，先保证 y 的移动最小，在此情况下...

2019-08-01

0 986

Fractal （POJ - 2083 ，递归画图）

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

2019-07-31

0 825

Find the answer （HDU - 6609，权值线段树）

一.题目链接： HDU-6609 二.题目大意：有 n 个数，到第 i 个数时，如果 sum > m，要求在 [1, i - 1] 中删除一些数，使得 sum ≤ m. 求最少删除数的个数. 三.分析：首先，删除的话肯定是要从最大数开始删. 即：将数组顺序排列，从大往小删除....

2019-07-31

0 479

国王游戏（算法竞赛进阶指南 P40，贪心 + 大数乘除）

一.题目链接：国王游戏二.题目大意：国王和大臣排队，国王始终排在最前面. 每个人的左右手里各有一个数 a，b. 每 i 位大臣获得钱数为现在对大臣重新排队，求最小化最大大臣金额. 三.分析：按照大臣的 a * b 排序，得到的最大大臣金额是最小的. 证明：这里选用...

2019-07-30

0 1312

Radar Installation（POJ - 1328，贪心）

一.题目链接： POJ-1328 二.题目大意：给 n 个点（均在 y 轴上方），每个点都有一个坐标. 现在 x 轴上建立雷达，每个雷达可以扫描半径为 d 的区域. 求最少需要建立的雷达数，使得每个点都被覆盖. 三.分析：先计算出每个点在 x 轴上对应的范围 [l, r]. 对区...

2019-07-30

0 539