Daowuu

分类

动态规划(1) 博弈论(1) 图论(9) 字符串(5) 数学(10) 数据结构(3) 未归档(1) 计算几何(8) 题解(2) 高精度(1)

/ 注册

TA的专栏 37篇文章 0人订阅

14篇文章 1388人学习

8篇文章 1010人学习

10篇文章 1691人学习

5篇文章 935人学习

全部文章（共41篇）

二分图来自专栏

二分图匹配二分图：把无向图 G = （V，E）分为两个集合 V1，V2，所有的边都在 V1 和 V2 之间，而 V1 或 V2 的内部没有边。V1 中的一个点与 V2 中的一个点关联，称为匹配。染色法：一个图是否为二分图，一般用“染色法”进行判断。用两种颜色对所有顶点进行染色，要求一条边所连接的两...

图论

2020-08-16

0 772

高精度压位（亿进制）来自专栏

#pragma GCC optimize(3, "Ofast", "inline") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loo...

高精度

2020-08-15

0 620

状压DP

状态压缩dp的概念状压 dp 是动态规划的一种，通过将状态压缩为二进制数来处理复杂的集合问题。方案数例题：农夫有一块长方形土地，化成 n 行 m 列的方格。他准备种玉米，养牛（在一个格子内），不过有些格子很贫瘠，不适合种玉米。还有，牛不喜欢在一起吃，所以牛不能放在相邻的格子里，给出这块地的...

动态规划

2020-08-14

0 559

逆元来自专栏

逆元方程的一个解 x ，称 x 为 a 模 M 的逆。扩展欧几里得求解逆元注：a 和 M 需要互质，速度比费马小定理快一点 void exgcd(int a, int b, int &x, int &y) { // ax + by = gcd(a,b) if (...

数学

2020-08-06

1 680

数字之美来自专栏

数的各位数之和一个数 x 在（x*i+1）进制下，对于任意一个能被 x 整除的数，它的各位之和也能被 x 整除。例如：十进制下的 3。数的拆分数 x 拆成 n 个相等的数，使 n 个数之积最大。（n 为个数限制）例如：数 x 拆成 3 和 2，使拆分出的数之积最大。（个数没有限制...

数学

2020-08-06

0 956

SG函数来自专栏

SG函数对于任意状态 x ，定义 SG(x) = mex(S),其中 S 是 x 后继状态的 SG 函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么 SG(x)=mex{SG(a),SG(b),SG(c)}。这样集合 S 的终态必然是空集，所以SG函数的终态...

博弈论

2020-08-05

1 1388

快速幂来自专栏

乘法快速幂 int fpow(int a, int n) { int res = 1; for(; n; n>>=1, a*=a) if(n&1) res*=a; return res; }矩阵快速幂 struct matrix { int m...

数学

2020-08-04

0 433

字典树来自专栏

字典树（前缀树）具体来说，Trie一般支持两个操作： insert(S)：插入操作，就是将一个字符串 S 加入到集合中。 search(S)：查询操作，就是查询一个字符串 S 是不是在集合中。 int trie[maxn][26], tot; // 字典树 & 前缀树 int ex...

字符串数据结构

2020-08-01

0 803

Manacher 来自专栏

manacher（马拉车）算法时间复杂度求解一个字符串的最长回文子串长度的问题。注：先插入 n+1 个 # ，再设置一个 po，维护已知区域 (po-Next[po]，po+Next[po])，即维护 po。 char s[maxn], t[maxn<<1]; // s 为文本串...

manacher 字符串

2020-08-01

0 556

KMP 来自专栏

KMP KMP 是单模匹配算法，即在一个长度为 n 的文本串中查找一个长度为 m 的模式串。 KMP 算法的基础时间复杂度在用 KMP 算法时，指向 s 的 i 指针不会回溯，而是一直往下走到底。那么 KMP 是如何让 i 不回溯，只回溯 j 的呢？这就是 KMP 的核心———fail[]数组...

kmp

2020-07-29

0 918