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篇）

D-query （SPOJ - DQUERY，单点修改主席树）

一.题目链接： SPOJ-DQUERY 二.题目大意：求区间 [l, r] 中不同元素的个数. 三.分析：先考虑区间右端点 r 的情形. 设有 5 个元素{1,2,2,3,5}，每个元素最后出现的位置为{1,0,1,1,1}. 那么，区间[1,5]中不同元素的个数为 sum[5] ...

2019-07-29

0 505

K-th Number （POJ - 2104，可持久化线段树模板）

一.题目链接： POJ-2104 二.题目大意：求区间第 k 大值. 三.分析：因上午迟到，被队长强迫学习主席树..... 今天心血来潮，想学习一下主席树！！！因为这题是模板，具体的内容这里不再详谈，只写一些自己对主席树的理解. 主席树的建树过程插入两个节点：1，2 （n ...

2019-07-29

0 448

黑匣子（落谷P1801，对顶堆动态维护动态第 k 小值）

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

2019-07-26

0 597

Running Median（ POJ - 3784，对顶堆动态维护中位数）

一.题目链接： POJ-3784 二.题目大意：给你 n 个数，当 i 为奇数时，输出中位数. 三.分析：对顶堆维护即可. 另外不要 PE. 对顶堆学习四.代码实现： #include <set> #include <map> #include &l...

2019-07-26

0 554

Cinema （CodeForces - 670C ，离散化入门）

一.题目链接： CodeForces-670C 二.题目大意：有 n 个人，每人会且仅会一种语言. （n ≤ 2e5）语言有各自的编号（≤ 1e9）这些人去看电影，一共有 m 种电影. （m ≤ 2e5）每个电影的声音与字幕语言都不一样. 若有人的语言与声音语言一样，则称这个...

2019-07-26

0 828

序列变换（HDU - 5256，Lis 应用）

一.题目链接： HDU-5256 二.题目大意： n 个数，问至少需要修改几个数，使得序列严格递增. ps：所有的数均为整数. 三.分析：注意：是修改！！！（不是删除）.因为这个WA到怀疑人生因为要求序列严格递增可得：立即推：移项可得：于是，构造新数列 {b}，使得...

2019-07-25

0 730

Queue （HDU - 5493，树状数组 + 二分 || 线段树）

一.题目链接： HDU-5493 二.题目大意：有 n 个人排队，身高各不相同. 给出每个人的身高，以及队中他前面比他高或者后面比他高的人数. 若此队伍存在，则输出最小字典序的队伍排列. 否则，输出 "impossible". 三.分析：因为是求最小字典序，所...

2019-07-24

0 534

MAZE（2019牛客暑期多校训练营（第二场）E，线段树 + 矩阵乘法）

一.题目链接： MAZE 二.题目大意：给一个 n × m 大小由{0,1}构成的矩形，Q 次询问. 0 可以走，1 不可以走. 每次走只能向下，左，右方向，且不能走重复的位置. 每次询问有三个整数：q，a，b. 当 q 为 1 时，将点（a，b）取反. 当 q 为 2 时，求出从...

2019-07-23

0 949

Flyer （HDU - 4768，二分答案 + 思维）

一.题目链接： HDU-4768 二.题目大意：有 n 个社团拉人. 从编号为 a 的学生开始，到编号为 b 的学生结束，每隔 c 个人拉一个. 保证学生被拉选奇数次的个数至多为一. 若不存在被拉选奇数次的学生，则输出 "DC Qiang is unhappy." ...

2019-07-20

0 538

Matrix （POJ - 3685，二分答案 + 二分）

一.题目链接： POJ-3685 二.题目大意：给 n 和 m. 表示有一个 n × n 的矩阵，求第 m 小的元素的值. 矩阵元素的计算公式：三.分析：易得矩阵的元素在同一列上单增. 第一层二分答案. 因为是求第 m 小的数，所以必有 m 个数 ≤ 答案（数有重复）. c...

2019-07-19

0 651