house_cat
house_cat
全部文章
分类
ACM(110)
JAVA(5)
其他(3)
文(1)
算法导论(2)
计算机图形学(4)
面试(2)
题解(2)
归档
标签
去牛客网
登录
/
注册
house_cat
不要忘记努力
全部文章
(共19篇)
[学习笔记]莫队算法
莫队算法 确实是看过的最良心的讲解: https://www.cnblogs.com/CsOH/p/5904430.html 问题:有n个数组成一个序列,有m个形如询问L, R的询问,每次询问需要回答区间内至少出现2次的数有哪些。 朴素的解法需要读取O(nm)次数。如果数据...
学习笔记
莫队
2018-09-24
0
409
缩点
题目描述 给定一个n个点m条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。 输入输出格式 输入格式: 第一行,n,m 第二行,n个整数,依次代表点权 第三至m+2行,每行两...
图论
学习笔记
缩点
2018-10-17
0
441
[学习笔记]点分治
点分治 解决问题 对于某些限定条件的路径静态地进行统计的算法. 基本思路 分治思想 对于某一点P,树上路径可以分为两类,经过点P,包含与点P的某一棵子树上 第二种可以递归处理 第一种通过求P的所有子节点的深度就可以处理 树的重心 如果是一条链的话,那复杂度很大,需要递归N层,...
学习笔记
点分治
2019-07-21
0
682
[一般图最大匹配]Bimatching
10566 Bimatching 题意:一个男生必须跟两个女生匹配,求最大匹配 思路:一般的二分图匹配做不了,网络流也不会建图,这题采用的是一般图匹配 首先在原来二分图的基础上,将一个男生拆成两个点 两个点之间有一条边,这样图至少会有n个匹配 如果想要答案...
图论
学习笔记
一般图匹配
2019-08-25
0
360
[学习笔记]启发式分治
启发式分治 给定n个数,求满足某种条件的点对数目或最大权值,而这个最大权值与点对(a,b)的区间[a,b]的区间最大/最小值有关。 那么这时就可以考虑分治,对于区间[L,R],找到最小/大值所在位置,然后处理横跨最小/大值所在位置的点对,然后递归处理子区间。 HUD-Make Roun...
学习笔记
启发式分治
2019-08-29
0
600
[学习笔记]二项式反演
例题:[King's Colors][https://vjudge.net/problem/Kattis-kingscolors] 题意:n个点的树,用恰好k种颜色染色,并且要求相邻两个点不同。 这题可以发现就是组合数学题,跟树的形状一点关系都没有。求最多用k种颜色染色...
学习笔记
数学
组合数学
2019-09-25
0
728
[学习笔记]AC自动机
目录 概述 回顾KMP 字典树insert() 失配指针fail[] 构建函数build() 多模式匹配query() 模板 Aho-Corasick automaton 本文基本上是oiwiki的复制粘贴:https://...
学习笔记
AC自动机
字符串
2020-01-27
0
662
[学习笔记] 平衡树-Splay
简介 Splay是一种平衡二叉树。它通过不断地将某个节点旋转到根节点,使整棵树仍然满足二叉查找树的性质,并且保持平衡而不至于退化成链。 Splay的时间复杂度是按总复杂度来算的,具体来说,即是: 从空树开始,做插入、删除、访问操作共M次,树中最多同时存在N个点, 则总时间复杂度不超过\(O(Ml...
学习笔记
2020-03-04
0
694
[学习笔记]树套树
引言 树套树,顾名思义,就是要将两种或多种树形数据结构结合起来,解决一些单独无法解决的问题。 如果说要解决区间上的问题,如最大值,区间修改等,肯定会想到线段树。 但是线段树不能查询第k大,不能查询一个数在区间的排名,自然也不能查询前驱和后继。 平衡树可以解决查询排名、前驱、后继等问题,但其不...
线段树
树
查找二叉树
Splay
学习笔记
树套树
2020-03-07
0
537
首页
上一页
1
2
下一页
末页