Chrety

算法

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 详尽的思路(1) 题解(1)

/ 注册

全部文章 / 算法（共8篇）

匈牙利算法小结

最近浅学了一下匈牙利算法，略有感触，发文记录一下匈牙利算法是用在二分图匹配中的所以要先知道二分图的几个概念二分图：有这么一个图把一个图的顶点划分为两个不相交的集合 U 和 V ，且使得每一条边都分别连接 U 、V 中的顶点，如果存在这样的划分，则称此图为二分图。简单说，就...

算法

2018-12-23

0 1100

最小表示法

用途给一个首尾相连的字符串，找一个位置，从这个位置往后形成一个字符串，使字符串的字典序最小算法定义三个指针\(i=0\),\(j=1\),\(k=0\)，\(i\)和\(j\)是当前判断的位置，\(k\)是相同的串的长度，表示\(str[i...i+k]\)和\(str[j...j+k]...

算法字符串

2019-02-24

0 566

Manacher算法详解

问题什么是回文串，如果一个字符串正着度读和反着读是一样的，这个字符串就被称为回文串。 such as noon level aaa bbb 既然有了回文，那就要有关于回文的问题，于是就有了—— 最长回文子串：给定一个字符串，求它的最长回文子串长度。暴力找出所有的子串，遍历每...

算法字符串

2019-03-02

0 830

P1494 [国家集训队]小Z的袜子

题目 P1494 [国家集训队]小Z的袜子解析在区间\([l,r]\)内，任选两只袜子，有 \[r-l+1\choose2\] \[=\frac{(r-l+1)!}{2!(r-l-1)!}\] \[=\frac{(r-l+1)(r-l)}{2}\] 种选择。对于一种颜***r...

莫队算法

2019-03-27

0 530

HDU 1757 A Simple Math Problem (矩阵快速幂)

题目 A Simple Math Problem 解析矩阵快速幂模板题构造矩阵 \[\begin{bmatrix}a_0&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\ 1&0&am...

数学矩阵矩阵快速幂算法

2019-04-13

0 639

P4137 Rmq Problem / mex (莫队)

题目 P4137 Rmq Problem / mex 解析莫队算法维护mex，往里添加数的时候，若添加的数等于\(mex\)，\(mex\)就不能等于这个值了，就从这个数开始枚举找\(mex\)；若不等于\(mex\)，没有影响，因为它之前的所有数都出现过了，又出现一次不会怎样，放...

莫队算法

2019-04-16

0 545

P3709 大爷的字符串题 (莫队)

题目 P3709 大爷的字符串题题意：求\([l,r]\)中众数的个数。解析维护两个数组： \(cnt[x]\)，数\(x\)出现的次数。 \(sum[x]\)，出现次数为\(x\)的数的个数。考虑往里添加元素时，直接取\(max\)；删除元素时，如果这个数是众数(...

莫队算法

2019-04-16

0 451

P1462 通往奥格瑞玛的道路 (二分+最短路)

题目 P1462 通往奥格瑞玛的道路给定\(n\)个点\(m\)条边，每个点上都有点权\(f[i]\)，每条边上有边权，找一条道路，使边权和小于给定的数\(b\)，并使最大点权最小。解析二分一下钱，然后跑最短路，判断一下如果只有这么多钱的话能不能到终点（最短路边权和是不是不超过\(b\)...

二分最短路算法

2019-04-27

0 752