Renatus

分类

---------DP---------(3) --------图论--------(2) --------数学--------(1) -------字符串-------(5) ------实用工具------(1) ------数据结构------(1) Codeforces(1) DFS(1) FFT(1) Kruskal(1) 主席树(1) 史诗级题目表(1) 程序语言C++(4) 题目合集(1)

/ 注册

全部文章（共24篇）

网络流详解

网络流详解 hehe，说是详解，实际上只是一个知识点的不完整的小汇总，可能日后有所补充首先介绍三个基本的网络流问题：最大流问题问题介绍这是网络流问题的一种，也是最基本的一种，题意是让你求出一个网络流中从源点到汇点所能存在的最大流量。这个问题有许多的算法，下面来简单地谈一谈： ...

2017-03-11

0 414

基础数论算法详解

基础数论算法首先，它们这些算法十分基础，基础到并不包含莫比乌斯反演什么的，所以仅仅当做娱乐性质的文章内容一览由于数论中的算法较多，下面先进行一个小汇总素数的筛法最大公约数求法扩展 GCD 算法质因数分解法乘法逆元求法...

2017-03-07

0 505

树链剖分详解

树链剖分发现最近几天可以出专题了。。。近几天搞板子题真的是逼着我写一些东西。。。那么我们来搞一搞树链剖分原理树链剖分，实际上就是一种把树结构映射到一颗线段树结构上的算法，常用于搞各种树上的两点路径查询及修改的问题，但树的形态不能改变，否则要改用LCT，然而我还不会hehe 我们记录...

数据结构树链剖分

2017-03-07

0 369

AC自动机详解

AC自动机最近真是太颓了，做了一堆板子题，现在对一些知识点顺便来个总结记录原理大家应该都知道KMP和Trie树吧，不懂的可以看我博客或到网上自己动手寻找资料。AC自动机是一个很好的东西，这是因为它的名字很好它能够在有多个模式串的时候进行全文匹配，这十分方便地扩展了KMP的功能，实际上...

2017-03-07

0 488

BZOJ 2565 最长双回文串 Manacher

BZOJ 2565 最长双回文串 Manacher 题目顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和...

2017-03-03

0 367

Manacher算法详解

Manacher算法详解 RT，Manacher算法今天第一次写，有不少细节，也容易写错，下面进行一个小小的总结原理首先，我们应该已经看到过很多有关回文串的题目了，当我们不会Manacher的时候，我们往往是用回文自动机后缀数组代替的，这时候我们会发现有些题它并不能卡过，因为后缀数组是...

2017-03-03

0 388

图论2-SAT算法详解

图论2-SAT算法详解今天我们来介绍一个我个人认为最难的算法，这是为什么呢？肯定会有许多dalao说，不就一个2-SAT，我两分钟就A掉了。然而2-SAT的细节非常的多，稍不注意就会写错，而且测试困难，造数据后手算实在麻烦，综合上述内容，这个算法非常困难原理主要是这样的，这个算法是为...

2017-03-03

0 771

多字符串存储的Trie树详解

多字符串存储的Trie树详解 RT，最近刷了一波水题，同时复习了一下Trie树结构，下面进行一个小详解原理我们把字符串的一端对齐。然后按照字符位进行树上的更新与插入，目的就是使为了从每个单词节点出发，到根节点结束所形成的一条路径表示原来插入的字符串，鉴于它十分简单，网上资料也很多，这里...

2017-03-02

0 375

字符串匹配算法KMP详解

字符串匹配算法KMP详解 RT，今日十分地无聊，刷了一波水题，在刷水题的过程中也发现了不少问题，下面顺便对KMP进行一个小讲解原理首先，KMP是一个字符串匹配算法，这个应该周所周知。它的思路大概是对模式串构造一个类似于状态机一样的东西，构造出它的失配函数以及失配边，然后在字符串匹配的时...

2017-03-02

0 372

斜率优化DP学习笔记

斜率优化DP学习笔记 RT，最近练习一些斜率优化的DP，也发现了不少的问题，下面进行一下小小的记录与知识的回顾与理解介绍首先，斜率优化是一种对DP进行优化的好东西，大多数的时候，它的使用可以把 O(n2) 的复杂度降低到 O(nlogn) 甚至是 ...

2017-03-01

0 448