house_cat

ACM

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

/ 注册

全部文章 / ACM （共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