吴国庆

算法学习

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 题解(38)

/ 注册

全部文章 / 算法学习（共6篇）

主席树

HDU6704 补 2019山东省赛 E 补 // 区间操作灵活应用静态区间第k小普通权值线段树可以查询整体的第k小问题而主席树就是利用这一点保存每个时刻的权值线段树，这样当查询区间第k值时就能通过相减得到这个区间的权值线段树就相当于这个区间求整体第k值故主席树能查询区间第k值(__...

2020-05-04

0 629

莫队

bzoj2038莫队入门题目目前没有理解的几点就是当前区间L R的初始化问题，为什么要L=1，R=0? 还有在更新过程中出现了cnt《0的情况？ hdu6483莫队求区间不同数字种类数当题目要求的区间操作满足以下条件时可以应用莫队 1）已知L，R区间答案可以O1求出【L-1，R】【L，R-1】...

2020-05-04

0 625

AC自动机

洛谷P5357模板题 CodeForces 727E Games on a CD补 HDU – 2243 poj2778 nefuoj2027 在写AC自动机相关题目时要注意一下几点避免浪费时间 1）使用邻接矩阵建图时要注意将head 清空为-1 2）解决计数问题时mod运算比较费时，少用 3...

2020-05-04

0 700

树链剖分入门

例题 POJ 3237（） BZOJ 3083 BZOJ 3531 BZOJ 3589 BZOJ 3626 将树上问题通过dfs序的性质转换为区间问题，从而对树上修改时就可转化为相应的区间修改。再通过引入重儿子，重链一系列概念将时间复杂度也变成了可以接受的层次通过两次dfs求出树上一系列的信息 ...

2020-05-04

0 552

二分图

总结二分图的最大匹配：匈牙利算法二分图的最小点覆盖数 = 二分图最大匹配数二分图最大独立集 = 总点数 - 二分图最大匹配数（有向无环图）不可重叠最少路径覆盖数=原图点数 - 二分图的最大匹配二分图多重匹配就是在匈牙利算法上加上一维 limit 的维度（可以引入源点和汇点进而转化成最...

2020-05-04

0 731

整除分块证明

2020-05-04

0 492