-
异或线形基
===Index 简介与模板 线性基模板题 xor异或 异或值第k小 线性基的基底数目简介与模板异或线性基：用于处理多个数中选取一些数的XOR的最大值，最小值，第k大值，并可以查询能否通过集合中任意个数XOR得到，时间复杂度 O(n*log(n))。线性基具有如下性质： 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。 线性基是满足性质 1 的最小的集合。 线性基没有异或和为 0 的子集。 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或...…
-
二分图
===Index 简介 判定定理 二分图判定 染色法 并查集判定 二分图最大匹配 匈牙利算法 Hopcroft–Karp算法 二分图的最大匹配 dinic算法 二分图最大权完美匹配 模板二分图最大权完美匹配 二分图常见模型 dag最小路径覆盖 二分图最小点覆盖 二分图最大独立集 ...…
-
最近公共祖先
===Index 简介 性质 算法 树上倍增 欧拉序列转化为rmq问题 例题 最近公共祖先 树上与u距离为k的节点 连通路径 network-树上差分 简介最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 为了方便，我们记某点集 S=v1,v2,…vn 的最近公共祖...…
-
杂题选讲
===Index daimayuan 子串的最大差 区间中不大于x的数的数目 树上路径异或和 最小或值生成树 统计子数组和模k等于子数组长度的数量 异或后最少逆序对数 方块消失的操作次数 工作安排 树上三角形数 环上分段和的最大公约数 字典序最小 好序列 区间和 最大权值和划分 acwing/牛客 平均值大于k...…
-
区间计数与扫描线
===Index 区间覆盖 会议室2 每个人到达时花的数目 被k个区间覆盖的点的数目 会议室3 二维偏序问题 统计包含每个点的矩形数目 逆序对 区间并集 统计区间中的整数数目 区间覆盖会议室2给你一个会议时间安排的数组 intervals, 每个会议 intervals[i] = [starti, endi] ，表示会议的开始和结束时间，返回所需会议室的最小...…
-
codeforces/atcoder 选题
===Index codeforces 二进制字符串的最小代价 只剩一个星号的最小步数 区间最大值不小于区间和 字典序最小的错位排列 按位与排列 划分两个集合 相等的multiset 获得最多峰值的最小代价 最大最小子数组数目 奇偶序列 取模最大值数对 区间最小值的最大值 和的所有可能取值 差值不超过k的子序列数量 atcode...…
-
字符串算法
===Index 字符串哈希 acwing841 字符串字典树 字典树模板 字符串统计 字符串的前缀分数和 字典树统计前缀 kmp算法 z函数 ac自动机 -简单版 -强化版 manacher算法 最长回文子串 变成回文串最少在前面添加字符数 每个位置开始的回文串数目 前后缀回文串 每个位置的最长回文串长度 回文自...…
-
网络流模版
===Index 网络流 网络流模板 使用方法 飞行员配对问题 最小费用流 最小费用流模板 费用流使用方法 数组的最大与和 网络流网络流24题网络流模板template <class T> struct simple_queue { std::vector<T> payload; int pos = 0; void reserve(int n) {...…
-
高精度运算
===Index 大整数加法 大整数减法 大整数乘法 大整数除法大整数加法求两个不超过200位非负整数的和// s = "123234", t = "32313342";// ans = 32436576string sum(string s, string t) { reverse(s.begin(), s.end()); reverse(t.begin(), t.end()); int n = s.size(), m = t.size(), carry = 0...…
-
python 刷题库函数
===Index sortedcontainers SortedSet SortedList SortedDict collections Counter 示例题目 滑动窗口中位数 sortedcontainerspython 中的 sortedcontainers 模块 封装了对列表、字典、集合的排序等常用操作，在算法比赛中非常有用，很多在c++中实现较为困难的题在sorte...…
-
支持下标的平衡树
===Index 简介 pbds使用 pbds实现multiset 序列顺序查询 滑动窗口中位数 滑动窗口中位数2 滑动窗口最小代价简介c++ 中的set, multiset, map等 都支持 维持容器的有序以及按序遍历，但是却不支持下标访问，对于一些既要有序又要支持下标访问的问题，可以使用c++中的PBDS（Policy-based data structures）或者 python中的SortedListpbds使用#include <bits/stdc++.h&...…
-
搜索剪枝
===Index 子集和问题 部分子集和 分割等和子集 数组分割 子集和优化 送礼物 最接近目标值的子序列和 将数组分成两个数组并最小化数组和的差 子集和问题子集和问题 是从一个集合中选出一部分子集，使得这个子集的和满足一定条件，子集和问题有很多种变种，不同变种和数据范围采用的方法也不尽相同。部分子集和判断能否从数组a中选择一个子集，其和为s.设 sum(a) = n, n <= 1e5时，可以...…
-
机试选题
===Index google oa 二维矩阵中的好路径数 最少操作次数 字典序最大子序列 好路径的数目 最少需要添加元素数 最多出现次数 树上路径的位运算 将数组变为0的最小的k 最多赢的分数 异或三元组之和 部署服务的最小代价 数组最小值的最大值与最小代价 最小初始值 Amazon oa 找出数组第k大和 ...…
-
线段树
===Index 简介 区间修改与懒标记 模板代码 使用方法 单点修改例题 区间取模 区间加求区间GCD 维护区间最值及出现次数 维护区间最大子数组和 第k个1的下标 根据逆序对恢复原始排列 求嵌入区间的数目 求交叉区间的数目 区间交替符号和 区间逆序对 区间非下降子数组数目 区间方差 带懒标记例题 Lazy-区间取max...…
-
ST表
===Index 简介 算法实现 模板代码 例题 奶牛排队 非递减序列的区间众数 简介ST 表是用于解决 可重复贡献问题 的数据结构。可重复贡献问题可重复贡献问题 是指对于运算 opt，满足 x opt x = x，则对应的区间询问就是一个可重复贡献问题。例如：max(x, x) = x, gcd(x, x) = x;所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导...…
-
算法竞赛选手篇
===Index 中国选手 国外选手中国选手…
-
算法竞赛中的结论和公式
记录算法题中能用到的数学公式和结论，遇到新的再补充。===Index 数论 排列组合 蚂蚁掉落问题 区间中异或值最大的两个数 部分结论题 括号序列 下一个平衡括号序列 括号序列的字典序排名 第k个平衡括号序列 平衡括号子串数目 获得平衡括号串的最少交换次数 数列与递推 等差与等比数列 错位排列 第一类stirling数 第二类stirling数 卡塔...…
-
异或与字典树
===Index 模板 最大异或对 树上最大异或值路径 统计异或值在范围内的数对有多少 数对异或和 数对最短距离异或和 查询最大基因差 最大子数组异或和 xor-mst 排列异或和 可持久化01trie 区间最大异或和 查询区间最大异或(模板题) 树上路径最大异或和 模板template <typename T, int bit_len = numeric_limits<make_unsigned_t<...…
-
leetcode会员题
===Index 683.K 个关闭的灯泡 681.最近时刻 1057.校园自行车分配 642. 设计搜索自动补全系统 271. 字符串的编码与解码 723. 粉碎糖果 727. 最小窗口子序列 772. 中缀表达式求值 1153. 字符串转化 361. 轰炸敌人 317. 离建筑物最近的距离 1231. 分享巧克力 774. 最小化去加油站的最大距离k个关闭的灯泡leetcode 683N 个灯泡排成一行，编号从 1 到 N 。最初，所有灯泡都关闭。每天只打开一...…
-
力扣动归选题
===Index 扔鸡蛋 俄罗斯套娃信封问题 石子合并 零钱兑换(最少硬币) 零钱兑换(方案数) 目标和 分割等和子集扔鸡蛋leetcode 887给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <...…
