win_the_medal

分类

Codeforces(14) Codeforces (Div.3)(6) kuangbin带你飞——搜索专题(9) STL(4) UVA(2) 动态规划--01背包(1) 动态规划--最长上升子序列(1) 动态规划--最长公共上升子序列(1) 动态规划--最长公共子序列(1) 动态规划--简单DP(4) 图论--SPFA(3) 图论--二分图(1) 图论--差分约束(3) 图论--最小生成树(3) 图论--最短路(10) 字符串--AC自动机(4) 字符串--hash(7) 字符串--KMP(4) 字符串--Manacher(3) 字符串--后缀数组(13) 技巧--二分查找(5) 技巧--前缀和(5) 技巧--大数运算(6) 技巧--尺取法(5) 技巧--拓扑排序(2) 技巧--数据离散化(1) 搜索--BFS(3) 搜索--DFS(20) 数学--gcd和lcm(1) 数学--中国剩余定理(2) 数学--博弈论(2) 数学--快速幂(1) 数学--拓展欧几里得(1) 数学--欧拉函数(1) 数学--矩阵快速幂(1) 数学--素数筛(5) 数学--逆元(1) 数据结构--fhq Treap(2) 数据结构--LCA(1) 数据结构--ST表(2) 数据结构--主席树(1) 数据结构--划分树(1) 数据结构--单调栈与单调队列(4) 数据结构--字典树(5) 数据结构--并查集(4) 数据结构--替罪羊树(1) 数据结构--树状数组(4) 数据结构--树链剖分(8) 数据结构--线段树(15) 牛客(1) 算法--BFPRT(1) 算法--枚举(1) 算法--模拟(7) 算法--贪心(2)

/ 注册

全部文章（共216篇）

扩展KMP

https://blog.csdn.net/dyx404514/article/details/41831947 拓展kmp是对KMP算法的扩展，它解决如下问题：定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[...

2019-08-02

0 541

二分图的定义及判断

二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B)，则称图G为一个二分图。二分图的另一种等价的说法是，可以把每个节...

2019-08-02

0 396

BFPRT算法O(n)解决第k小的数

链接：https://www.jianshu.com/p/a43b0e1712d1 第k小算法我们通常会简单地进行一个快速排序后，得到第k个位置上的数字即可。我们都知道的是快速排序是个不稳定的排序，它的排序过程简单的理解主要是两个概念Partion,pivot(基准数) 一趟快速排序...

2019-08-02

0 729

Manacher练习

K：题意：求回文串。思路：Manacher算法模版题 1 #include <stdio.h> 2 #include <algorithm> 3 #include <iostream> 4 #include <stdb...

2019-08-02

0 436

KMP全家桶练习

A：题意：给出一个主序列，和一个匹配序列，如果能够匹配，则输出匹配序列第一个数在主序列中的位置. 思路：KMP的模版题不多说 1 #include <stdio.h> 2 #include <algorithm> 3 #include &l...

2019-08-01

0 349

Codeforces Round #552 (Div. 3)

B. Make Them Equal Description 给定一个长度为 nn 的序列，请你选择一个非负整数 DD，然后将序列中的所有元素要么加上 DD，要么减去 DD，要么不做改变，使得修改后的序列所有元素都相等。最小化 DD Input 第一行是一个整数 nn 第二行 nn 个...

2019-07-31

0 342

Manacher's Algorithm

Manacher's 马拉车算法其实就是用来解决最长回文字符串的问题的。回文串就是正反读起来就是一样的，如“abba”。如果暴力去解决这个问题的话，它的时间复杂度是O(n^3) 当然我们还可以优化一下采用中心检测法，这样可以使算法的复杂度降为O(n^2) + O(1) 现...

2019-07-31

0 414

poj 2559 (单调栈)

Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may h...

2019-07-31

0 376

单调队列

单调队列性质单调队列和单调栈很像，就是一个维护了单调性的队列数据结构，可以是单调递增的，也可以是单调递减的。模型下图是一个单调递增的单调队列模型。其中元素也是从小到大排列。和单调栈的操作一样，如果加入一个满足单调性的元素，例如5，那么就直接加入。那么如果加入一个...

2019-07-31

0 462

单调栈

单调栈性质单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性，可能为单调递增，也可能为单调递减。模型例如下图就是一个单调递增的单调栈。其中的元素从小到大排列。那么，如果我们要加入一个新的元素5，5>4，符合要求，就可以直接加入。那么如...

2019-07-31

0 720