洛谷：P3386 题目背景 二分图 题目描述 给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数 输入输出格式 输入格式： 第一行，n,m,e 第二至e+1行，每行两个正整数u,v，表示u,v有一条连边 输出格式： 共一行，二分图最大匹配 输入输出样例 输入样例#1： 1 1 1 1 1 输出样例#1： 1 邻接矩阵（老码风） #include <cstdio> #include <iostream> #include <algorithm> #include &…
简介 有时我们会遇到一些VIP动漫（特别是某奇艺），或是画质无法忍受....但是如果我们去Nyaa动漫花园下种子观看的话，就没有在某站上看弹幕的乐趣，这个开源程序就解决了这个问题。（甚至包含了Aria2下种子/磁链功能/可配置自己的tracker） 支持多个网站的网络弹幕：包括Bilibili，Acfun，Tucao，5dm，弹弹，巴哈姆特动画疯 当然也支持本地弹幕 下载 Github源码：https://github.com/Protostars/KikoPlay KikoPlay基于以下项目： Qt 5.10.…
数据结构 树状数组，堆 线段树 单点，区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n)，按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较难写， noip 也不会考这么高级的东西 只能说 (开了 O2 的)set 秒杀一切 dfs 序与树链剖分 非传统方法 点事件 分块 cdq 分治 树状数组 具体思想就是要维护一个序列 a 的前缀和，我们可以维护一个辅助序列 s，使得 si = ∑j2(i-lowbit(i);i] aj，然后我们发…
模板 #define lowbit(x) x & -x //1D void add(int x,int t) { while(x <= n) { v[x] += t; x += lowbit(x); } } int query(int x) { int res = 0; while(x) { res += v[x]; x -= lowbit(x); } return res; } //2D n * m void add(int x,int y,int t) { while(x <= n) { f…
搜索问题 搜索是玄学，最稳定的应用是写暴力 or 骗分。 一个搜索问题的基本模型有以下几个要素： 状态：表示当前搜索到的局面。一般用x,y,z表示。一开始我们处于初始状态。 代价：表示对当前状态好坏的一个衡量。一般用f(x),g(x)表示，指代状态代价。 扩展（转移）：表示从当前状态出发，我们再进行一步搜索的过程。在扩展过程结束以后，我们可能会转移到若干个新的状态。一步转移也会带来代价，称为转移代价。 搜索问题可以分为两类：可行性搜索与最优性搜索。 在可行性搜索问题当中，目标是搜索到某些给定状态，问是否能够从初始状…
简介 ST表用于区间RMQ问题，它可以做到O(nlogn)预处理，O(1)查询最值。相比线段树，更加有利于静态数据的最值问题。主要是利用倍增的思想。 洛谷：P3865 模板 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #include <vector>…
裴蜀定理 在数论中，裴蜀等式是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a,b和m，关于未知数 x和y的线性丢番图方程（称为裴蜀等式）：ax+by=m 有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 x、y都称为裴蜀数，可用扩展欧几里得算法求得。 就是关于 x, y 的不定方程 ax + by =c 有整数解的充要条件是 gcd(a,b)∣c 。 题目见洛谷:P4549 模板 #include <cstdi…
简介 Hash算法类似于给字符串进行加密的方式，方便判断重复 那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。 进制哈希是最常见（NOIP）的哈希方式 它的主要思路是选取恰当的进制，可以把字符串中的字符看成一个大数字中的每一位数字，不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是O(n) 评测：洛谷P3370 模板 #include <cstdio> #include <cstdlib> #include <…
逆元 a * b = 1 (mod p) 则a,b互为逆元 费马小定理 a ^(p-1) = 1 (mod p) p 为质数 -> a * a ^(p-2) = 1 (mod p) 于是 a和a ^(p-2) 互为逆元 欧拉函数 定义：φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) p(1),p(2)…p(n)为x的所有质因数 表示 小于x的数中与x互质的数的数目 欧拉公式：a ^ φ(p) =1 (mod p) -&…
