Scorpioch

未归档

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 算法(1) 背包问题(1)

/ 注册

全部文章 / 未归档（共55篇）

【待填坑】sdfzchy的模板库

基础算法 1.三分 2.求逆序对 3.离散化字符串 1.KMP及EX_KMP 2.Manacher 3.Trie树 4.AC自动机 5.Hash 图论一.强连通分量 1.Tarjan 二.最短路 1.dijkstra的优先队列优化 2.SPFA判负权环三.网络流...

2017-06-26

0 379

【HDU3068】【模板】最长回文

Manacher算法的裸题下面简单说一下复杂度为O（n）的马拉车算法首先过程中涉及到的变量有： p[i]表示以t[i]字符为中心的回文子串的半径 id为最大回文子串中心的位置 mx是回文串能延伸到的最右端的位置通过p数组我们就可以找到最长回文子串及其位置，，那么下面我们就来看如何求...

2017-05-28

0 427

【POJ1986】【模板】LCA

LCA 最近公共祖先倍增法 f[i][j]表示i的2^j祖先，f[i][0]即表示i的父亲首先预处理出f数组，一次dfs然后递推即可接下来求LCA，思路就是让两个需要求LCA的点上升到同一层，然后一直向上找到他们LCA的子节点即可详细说明代码里有 #include<iost...

2017-05-28

0 452

【poj1804】【poj2299】【模板】求逆序对

刚写了一发归并排序的逆序对（不会写二分的蒟蒻）那就顺便复习一下树状数组求逆序对吧来道裸题题目:http://poj.org/problem?id=1804 题意:给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列. 归并排序是将数列a[l,h]分成两...

2017-05-13

0 484

【模板】KMP

KMP算法贴个链接：http://blog.csdn.net/v_july_v/article/details/7041827 这个博客讲的蛮不错本人比较懒就不做过多解释了（hhh）只是重申几个比较核心的思想与概念 1.字符串匹配的加速主要在于在匹配过程中失配的情况下，有效地多往后面...

2017-05-02

0 396