house_cat

ACM

JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章 / ACM （共19篇）

[学习笔记]线段树

线段树基本概念线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉...

学习笔记

2018-07-27

0 442

[学习笔记]搜索

搜索有种算法叫暴力剪枝代码模板添加边 void add(int u,int v) { s[++len].u=u; s[len].v=v; s[len].next=head[u]; head[u]=len; } DFS遍历 ...

学习笔记搜索

2018-07-29

0 562

[学习笔记]树状数组

树状数组要是别人说怀有希望是错误的事，无论多少次我都一定会反驳这句话。基本代码 int lowbit(int t) { return t&(-t); } void add(int x,int y) { for(int i=x; i<=n; i+=lowbi...

学习笔记树状数组

2018-07-29

0 485

[学习笔记]KMP

KMP算法我的腿让我停下，可是心却不允许我那么做。引言字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置. char *str = "bacbababadababacambabacaddababacasdsd&q...

学习笔记 KMP 字符串

2018-07-29

0 402

[学习笔记]字典树

字典树原理字典树的本质是什么？它其实是一棵存储了很多字符串的树，这棵树上的每一条边就是某个或某些字符串中的一个字符，而从根节点到某一个特定节点所经过的一条路径上的所有边组成的就是字典树所保存的某一个字符串。不难看出，字典树就是一颗多叉树，它利用字符串的前缀来建立了这棵树，从而达到了节省存储空...

学习笔记 tire树

2018-08-01

0 542

[学习笔记]网络流

基本概念网络流用来解决流量的问题：所有弧上流量的集合\(f={f(u,v)}\),称为该容量网络的一个网络流带权的有向图\(G=(V,E)\) 满足以下几点，则称为网络流图有一个入度为0的顶点\(s\)，称\(s\)为源点。有一个出度为0的顶点\(t\)，称...

学习笔记图论网络流

2018-08-21

0 573

[学习笔记]ST表

给狂妄自负以适当的绝望，这就是真理基本概念 RMQ问题：给定一个长度为N的区间，M个询问，每次询问Li到Ri这段区间元素的最大值/最小值。如果暴力找最大值，复杂度是\(o(n)\)。但如果查询多次，这个复杂度就很大了。解决这个问题的方法是离线ST表和支持在线修改的线段树。 ...

学习笔记 ST表

2018-09-02

0 420

[学习笔记]连通分量与Tarjan算法

目录强连通分量模板题：信息传递题目描述输入输出样例输入样例输出提示求割点求桥点双连通分量模板题 Go around the Labyrinth 题目描述输...

学习笔记图论连通分量

2018-09-02

0 394

[学习笔记]有上下界的网络流

有上下界的网络流在沈阳的网络赛遇到一道求上下界网络流的模板题，虽然可以用贪心做，但毕竟是模板题，学习一下。原作者：https://www.cnblogs.com/liu-runda/p/6262832.html 引有上下界的网络流的核心是调整,我们通过一个初始的未必可行的流调...

学习笔记图论网络流

2018-09-11

0 564

[学习笔记]set的使用

set默认进行升序排列，通过结构体可以改。维护一个比主人公分数高的set 降序排列，比主人公高就进入set 比主人公低就不进去，或者在删除操作里删掉。然后血的教训 https://blog.csdn.net/yangruibao/article/details/9040045 #include...

学习笔记 STL-set

2018-09-15

0 422