#include<bits/stdc++.h>
using namespace std;
int main(){
}
提高组算法模板大全
代码中大部分使用的 int 类型，需要按照事实修改成 long long 。
基本
万能头文件版本：
不含万能头版本
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<array>
#include<random>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int main(){
}
加速读入：
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
快读快写：
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
常用基本代码：
#include<bits/stdc++.h>
using namespace std;
// Main Definition
int main(){
freopen(".in","r",stdin);
freopen(".out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// Main Code
}
基础算法
前缀和/差分
for(int i=1;i<=n;i++){
sum[i] = sum[i-1]+a[i];
} // Find(l,r): sum[r]-sum[l-1];
for(int i=1;i<=n;i++){
dif[i] += dif[i-1];
} // Change(x,to): dif[x]=to;
二分
int l=-INF,r=INF;
while(l<r){
int mid = (l+r>>1);
if(check(mid)){
l = mid+1;
}else{
r = mid;
}
}
STL 速查
常用函数
set
用于维护一个有唯一元素的集合。
insert(元素): 插入一个元素。
erase(元素): 删除一个元素。
find(元素): 查找一个元素。（如果等于.end()则没有此元素）
size(): 返回容器中元素的数量。
empty(): 检查容器是否为空。
multiset
与set相似，维护一个可以相同的元素集合。
queue
先进先出。
empty(): 检查队列是否为空。
size(): 返回队列中的元素数量。
front(): 返回队首元素的引用。
back(): 返回队尾元素的引用。
push(): 在队尾添加一个元素。
pop(): 移除队首元素。
deque
双端队列。
front()：返回第一个元素。
back()：返回最后一个元素。
begin()：返回第一个元素的迭代器。
end()：返回最后一个元素的迭代器。
empty(): 检查队列是否为空。
size(): 返回队列中的元素数量。
clear()：清空。
insert(iterator pos,value) ：在pos位置插入value元素。
push_back(value)：在队尾添加value。
push_front(value)：在队头添加value。
pop_back()：删除队尾元素.
pop_front()：删除队头元素
priority_queue
优先队列。
priority_queue<int> pq;
priority_queue<int,vector<int> > pq; // 大根堆
priority_queue<int,vector<int>,greater<int>> pq; // 小根堆
empty(): 检查队列是否为空。
size(): 返回队列中的元素数量。
top(): 返回队列顶部的元素（不删除它）。
push(): 向队列添加一个元素。
pop(): 移除队列顶部的元素。
map
字典，用于存储键值对。
map<key_type, value_type> mp;
mp[key]=value：赋值
mp[key]：查看元素
empty(): 检查是否为空。
size(): 返回元素数量。
clear()：清空map。
multimap
与map相似，可存储相同键值对。
bitset
优化bool数组使用。
bitset<N> b;
b[i]获取i位bool值。
count()：返回 1 的个数。
size()：返回位数。
test(pos)：检查某一位是否为 1。
all()：检查是否所有位都为 1。
any()：检查是否有任何一位为 1。
none()：检查是否所有位都为 0。
&：按位与
|：按位或
^：按位异或
~：按位取反
图论
概念
顶点：图上的每一个点。
无向图：边没有方向。
有向图：边有方向。
边：顶点与顶点之间的连线。
权：边的数值。
无向完全图：在无向图中，边数达到$n(n-1)/2$的图。
有向完全图：在有向图中，边数达到$n(n-1)$的图。
稀疏图：在$n$个顶点，$e$条边的图中，满足$e<n\log_2n$的图。
稠密图：在$n$个顶点，$e$条边的图中，满足$e\geq n\log_2n$的图。
子图：假设$G=(V,{E}),G_2=(V_2,{E_2})$，如果$V_2\subseteq V \text{且} E_2\subseteq E$，则$G_2$为$G$的子图。
领接点：两个顶点之间有一条边则为领接点。
出度、入度。
连通图：无向图中，任意两个顶点之间有路径，则为连通图。
连通分量：无向图中，极大连通子图称为连通分量。
强连通图：有向图中，任意两点连通。
强连通分量：有向图中，极大连通子图。
生成树：包含全部$n$个顶点并有$n-1$条边的连通树。
生成森林：非连通图中所有生成树组成的非连通图。
邻接表存储（常用）：
创建：
vector<pair<int,int> > g[N];
void add(int u,int v,int w=1){
g[u].push_back({v,w});
g[v].push_back({u,w});
}
查询：
for(int i=0;i<g[Now].size();i++){
int Next = g[Now][i];
// Main Code
}
链式前向星
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {
nxt[++cnt] = head[u]; // 当前边的后继
head[u] = cnt; // 起点 u 的第一条边
to[cnt] = v; // 当前边的终点
}
// 遍历 u 的出边
for (int i = head[u]; ~i; i = nxt[i]) { // ~i 表示 i != -1
int v = to[i];
}
// From OI Wiki
单源最短路 Dijkstra
特点：速度快。
const int M = 100010;
const int INF=1234567890;
int n,m,Start,u,v,w,dis[M];
bool vis[M];
vector<pair<int,int> > G[M];
void RunDijkstra(){
for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
priority_queue<pair<int,int> > Queue;
Queue.push({0,Start});
dis[Start] = 0;
while(!Queue.empty()){
int Now = Queue.top().second;
Queue.pop();
if(vis[Now])continue;
vis[Now] = 1;
for(int i=0;i<G[Now].size();i++){
int Next = G[Now][i].first;
int Weight = G[Now][i].second;
if(vis[Weight])continue;
if(dis[Weight]>dis[Now]+Next){
dis[Weight] = dis[Now]+Next;
Queue.push({-dis[Weight],Weight});
}
}
}
}
时间复杂度 $O(n \log{n})$ ;
单源最短路 Bellman-Ford
特点：可判负环、负边权。
const int N = 100010;
const int INF = 1234567890;
int n,m,Start,u,v,w;
struct edge{
int u,v,w;
};
vector<edge> Edge;
int dis[N];
bool Bellman_Ford(int Start){
for(int i=1;i<=n;i++)dis[i] = INF;
dis[Start] = 0;
bool isUpdate=0;
for(int j=0;j<=n;j++){
isUpdate = 0;
for(int i=0;i<Edge.size();i++){
u = Edge[i].u,v=Edge[i].v,w=Edge[i].w;
if(dis[u]==INF)continue;
if(dis[u]+w<dis[v]){
isUpdate = 1;
dis[v] = dis[u]+w;
}
}
if(!isUpdate){
return 0;
}
}
return isUpdate;
} // true:有负环 false:没有
时间复杂度 $O(nm)$
多源最短路 Floyd
特点：代码短。
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
时间复杂度 $O(n^3)$ ;
拓扑排序
每次访问入度为0的节点产生的顺序。
int n,m,x,y,in[N];
vector<int> g[N];
queue<int> q;
bool vis[N];
int ans[N],top=0;
void init(){
for(int i=1;i<=m;i++){
cin >> x >> y;
g[x].push_back(y);
in[y]++,out[x]++;
}
}
void getsorting(){
init();
queue<int> q;
for(int i=1;i<=n;i++){
if(in[i]==0)q.push(i);
}
while(!q.empty()){
int Now = q.front();q.pop();
if(vis[Now])continue;
vis[Now] = 1;
ans[++top] = Now;
for(int i=0;i<g[Now].size();i++){
int Next = g[Now][i];
in[Next]--;
if(in[Next]<=0)q.push(Next);
}
}
}
时间复杂度 $O(n+m)$ ;
最小生成树 Kruskal
以边大小排序，优先选择边最小的。使用并查集记录连通块。
int n,m,x,y,z,fa[N],ans=0;
struct edge{
int u,v,w;
bool operator <(edge y) const{
return w<y.w;
}
}Edge[M];int top=0;
void init(){
for(int i=1;i<n;i++)fa[i] = i;
}
int Find(int x){
if(fa[x]==x)return x;
return fa[x] = Find(fa[x]);
}
void Union(int x,int y){
fa[Find(x)] = Find(y);
}
int main(){
cin >> n >> m;
init();
for(int i=1;i<=m;i++){
cin >> x >> y >> z;
Edge[++top] = {x,y,z};
}
sort(Edge+1,Edge+1+top);
for(int i=1;i<=top;i++){
x = Edge[i].u, y = Edge[i].v, z = Edge[i].w;
if(Find(x)==Find(y))continue;
ans+=z;
Union(x,y);
}
for(int i=2;i<=n;i++){
if(Find(i)!=Find(i-1)){
cout << "-1" << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}
时间复杂度 $O(m\log{m})$ ;
最小生成树 Prim
排序最近的点。
int n,m,x,y,z,ans=0,cnt;
bool vis[N];
vector<int> g[N],w[N];
struct node{
int Weight,Next;
bool operator <(node y) const{ // min
return Weight>y.Weight;
}
};
priority_queue<node> q;
void Prim(){
q.push({0,1});
while(!q.empty()){
int Now = q.top().Next,W = q.top().Weight;
q.pop();
if(vis[Now])continue;
vis[Now] = 1;cnt++;ans+=W;
for(int i=0;i<g[Now].size();i++){
int Next = g[Now][i],Weight = w[Now][i];
if(vis[Next])continue;
q.push({Weight,Next});
}
}
}
// cnt<n 则图不连通
时间复杂度 $O(n\log{n}+m)$ ;
树论
概念
空树：没有节点的树。
节点的度：一个节点还有的子树的个数。
树的度：一棵树中，最大节点的度。
叶节点：度为0的节点。
父节点、子节点、兄弟节点
二叉树：树的度为二的树
完全二叉树：除了最下层，其余饱满
满二叉树：每层都饱满
性质
二叉树第$i$层节点数最多：$2^{n-1}$ $(i\geq1)$
深度为$k$的二叉树最多有$2^k-1$个节点$(k\geq1)$
满二叉树节点数：$2^k-1$ $(k\geq1)$
最近公共祖先（倍增）
使用倍增做法求lca。
int n,m,x,y,z,Start,fa[N][50],Deep[N],M;
vector<int> g[N];
bool vis[N];
void NewTreeDfs(int Now){
for(int i=0;i<g[Now].size();i++){
int Next = g[Now][i];
if(vis[Next])continue;
vis[Next] = 1;
Deep[Next] = Deep[Now]+1;
fa[Next][0]=Now;
NewTreeDfs(Next);
}
}
void Init(){
Deep[Start] = 1;vis[Start]=1;
NewTreeDfs(Start);
for(int j=1;j<=M;j++){
for(int i=1;i<=n;i++){
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
}
int Lca(int x,int y){
if(Deep[x]<Deep[y])swap(x,y);
for(int i=M;i>=0;i--){
if(Deep[x]-(1<<i)>=Deep[y])x = fa[x][i];
}
if(x==y)return x;
for(int i=M;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
时间复杂度 $O(n\log{n})$ ;
树的重心
使用重心性质1：当树以结点 $v$ 为根时，任一真子树的大小均不超过原树结点数的一半。
int n,x,y,cnt[N];
vector<int> g[N];
bool vis[N],ans[N];
void dfs(int Now){
if(vis[Now])return ;
vis[Now] = 1;
cnt[Now] = 1;
ans[Now] = 1;
for(int i=0;i<g[Now].size();i++){
int Next = g[Now][i];
if(vis[Next])continue;
dfs(Next);
cnt[Now] += cnt[Next];
if(cnt[Next]>n/2)ans[Now]=0;
}
if(n-cnt[Now]>n/2)ans[Now] = 0;
} // ans 为最终答案
时间复杂度 $O(n)$ ;
树链剖分
树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
数据结构
栈
int stack[N],top=0;
void push(int num){
stack[++top] = num;
}
void pop(){
top--;
}
// size: top
队列
int queue[N],l=1,r=0;
void push(int num){
queue[++r] = num;
}
void pop(){
l++;
}
// size: r-l+1
链表
struct Node{
int value;
Node *next;
};
void InsertNode(int i, Node *p) {
Node *node = new Node;
node->value = i;
node->next = p->next;
p->next = node;
}
并查集
快速查询两个点是否在同一个集合中。
int n,fa[N];
void init(){
for(int i=1;i<n;i++)fa[i] = i;
}
int Find(int x){
if(fa[x]==x)return x;
return fa[x] = Find(fa[x]);
}
void Union(int x,int y){
fa[Find(x)] = Find(y);
}
时间复杂度 $O(1)$ ;
单调队列
求最大值使用单调降队列，求最小值使用升队列。
void monotone_max(){
int head=1,tail=0;
for(int i=1;i<=n;++i){
while(head<=tail and q[tail]<=a[i])
tail--;
q[++tail]=a[i];
p[tail]=i;
while(p[head]<=i-k)
head++;
if(i>=k)cout << q[head] << endl;
}
}
堆
优先队列 std::priority_queue 使用方法：
创建：
priority_queue<int> myQueue;
添加：
myQueue.push(Num);
获取：
myQueue.top()
删除:
myQueue.pop();
判断是否为空
myQueue.empty()
获取长度
myQueue.size()
堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
int n,m,Tree[N],top=0;
void push(int num){
Tree[++top] = num;
int rt = top;
while(rt>1 and Tree[(rt>>1)]<Tree[rt]){
swap(Tree[(rt>>1)],Tree[rt]);
rt = rt>>1;
}
}
int front(){return Tree[1];}
void pop(){
swap(Tree[1],Tree[top--]);
int rt = 1;
while(rt<=top){
int left = rt<<1;
int right= left+1;
if(left<=top and Tree[left]>Tree[rt] and Tree[left]>=Tree[right]){
swap(Tree[left],Tree[rt]);
rt=left;
continue;
}
if(right<=top and Tree[right]>Tree[rt]){
swap(Tree[right],Tree[rt]);
rt=right;
continue;
}
return ;
}
}
线段树
以下线段树支持区间修改区间查询。
ll n,m,op,x,y,z,a[N];
ll Tree[4*N],Lazy[4*N];
void update(ll rt){
Tree[rt] = Tree[rt<<1]+Tree[(rt<<1)+1];
}
void updatelazy(ll rt,ll l,ll r,ll mid){
Tree[rt<<1] += Lazy[rt]*(mid-l+1);
Tree[(rt<<1)+1] += Lazy[rt]*(r-mid);
Lazy[rt<<1] += Lazy[rt];
Lazy[(rt<<1)+1] += Lazy[rt];
Lazy[rt] = 0;
}
void Init(ll l=1,ll r=n,ll rt=1){
if(l==r){
Tree[rt] = a[l];
Lazy[rt] = 0;
return ;
}
ll mid = l+r>>1;
Init(l,mid,rt<<1);
Init(mid+1,r,(rt<<1)+1);
update(rt);
}
void Change(ll x,ll y,ll z,ll l=1,ll r=n,ll rt=1){
if(x<=l and r<=y){
Tree[rt] += (r-l+1)*z;
Lazy[rt] += z;
return ;
}
ll mid = l+r>>1;
updatelazy(rt,l,r,mid);update(rt);
if(x<=mid) Change(x,y,z,l,mid,rt<<1);
if(y>mid) Change(x,y,z,mid+1,r,(rt<<1)+1);
update(rt);
}
ll Get(ll x,ll y,ll l=1,ll r=n,ll rt=1){
if(x<=l and r<=y){
return Tree[rt];
}
ll mid = l+r>>1,ans=0;
updatelazy(rt,l,r,mid); update(rt);
if(x<=mid) ans+=Get(x,y,l,mid,rt<<1);
if(y>mid) ans+=Get(x,y,mid+1,r,(rt<<1)+1);
return ans;
}
时间复杂度 $O(\log{n})$ ;
树状数组
注意 lowbit 函数计算。
int lowbit(int x){return x&-x;}
int n,m,op,x,y,a[N],sum[N];
void add(int x,int y){
int tmp = x;
while(tmp<=n){
sum[tmp] += y;
tmp += lowbit(tmp);
}
}
int get(int x){
int tmp = x,ans=0;
while(tmp>0){
ans+=sum[tmp];
tmp-= lowbit(tmp);
}
return ans;
}
void init(){
for(int i=1;i<=n;i++){
add(i,a[i]);
}
}
时间复杂度 $O(n \log{n})$ ;
二叉搜索树
集合 set 使用方法：
创建：
std::set<int> mySet;
插入元素
mySet.insert(Num);
遍历元素
for (int num : mySet) {
// num -> ans
}
查找元素
(mySet.find(20) != mySet.end())
删除元素
mySet.erase(Num);
检测集合是否为空
mySet.empty()
获取集合长度
mySet.size()
数学
高精度
__int128 使用方法：支持高精度运算。
输出输出：
inline void read(int &n){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
n=x*f;
}
inline void print(int n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10);
putchar(n % 10 + '0');
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
struct jclong{
short a[N];
int it;
bool is_negative;
void init(){
for(int i=0;i<N;i++) a[i]=0;
it=0;
is_negative = false;
}
void trim() {
while(it > 0 && a[it] == 0) {
it--;
}
if(it == 0) {
is_negative = false;
}
}
void str_to(string s){
init();
int start = 0;
if(s[0] == '-') {
is_negative = true;
start = 1;
}
for(int i = s.size() - 1; i >= start; i--){
a[++it] = (s[i] - '0');
}
trim();
}
string to_str(){
if(it == 0) return "0";
string s = "";
if(is_negative) s += '-';
for(int i = it; i > 0; i--){
s += char(a[i] + '0');
}
return s;
}
void int_to(int s){
init();
if(s < 0) {
is_negative = true;
s = -s;
}
while(s > 0){
a[++it] = s % 10;
s /= 10;
}
}
int to_int(int Mod = 100000007){
if(it == 0) return 0;
long long s = 0, x = 1;
for(int i = 1; i <= it; i++){
s = (s + a[i] * x) % Mod;
x = (x * 10) % Mod;
}
if(is_negative) {
s = (Mod - s) % Mod;
}
return (int)s;
}
void read(){
string s;
cin >> s;
str_to(s);
}
void write(){
cout << to_str();
}
bool abs_greater(const jclong& b) const {
if(it != b.it) return it > b.it;
for(int i = it; i >= 1; i--){
if(a[i] != b.a[i]) return a[i] > b.a[i];
}
return false;
}
bool operator<(const jclong& b) const {
if(is_negative != b.is_negative) {
return is_negative;
}
if(is_negative) {
return abs_greater(b);
} else {
if(it != b.it) return it < b.it;
for(int i = it; i >= 1; i--){
if(a[i] != b.a[i]) return a[i] < b.a[i];
}
return false;
}
}
bool operator>(const jclong& b) const {
return b < *this;
}
bool operator==(const jclong& b) const {
if(it != b.it || is_negative != b.is_negative) return false;
for(int i = 1; i <= it; i++){
if(a[i] != b.a[i]) return false;
}
return true;
}
jclong operator+(const jclong& b) const {
jclong c;
c.init();
if(is_negative != b.is_negative) {
jclong temp = b;
temp.is_negative = !temp.is_negative;
return *this - temp;
}
c.is_negative = is_negative;
int x = 0;
for(int i = 1; i <= it || i <= b.it || x > 0; i++){
x += a[i] + b.a[i];
c.a[++c.it] = x % 10;
x /= 10;
}
c.trim();
return c;
}
jclong operator-(const jclong& b) const {
jclong c;
c.init();
if(b.is_negative) {
jclong temp = b;
temp.is_negative = false;
return *this + temp;
}
if(is_negative) {
jclong temp = b;
temp.is_negative = true;
return *this + temp;
}
if(abs_greater(b)) {
int x = 0;
for(int i = 1; i <= it || i <= b.it; i++){
x = a[i] - b.a[i] - x;
if(x < 0) {
c.a[++c.it] = x + 10;
x = 1;
} else {
c.a[++c.it] = x;
x = 0;
}
}
c.trim();
} else {
c.is_negative = true;
int x = 0;
for(int i = 1; i <= it || i <= b.it; i++){
x = b.a[i] - a[i] - x;
if(x < 0) {
c.a[++c.it] = x + 10;
x = 1;
} else {
c.a[++c.it] = x;
x = 0;
}
}
c.trim();
}
return c;
}
jclong operator*(const int b) const {
jclong c;
c.init();
if(b == 0) return c;
c.is_negative = is_negative ^ (b < 0);
int abs_b = abs(b);
int x = 0;
for(int i = 1; i <= it || x > 0; i++){
x += a[i] * abs_b;
c.a[++c.it] = x % 10;
x /= 10;
}
c.trim();
return c;
}
jclong operator*(const jclong& b) const {
jclong c;
c.init();
if(it == 0 || b.it == 0) return c;
c.is_negative = is_negative ^ b.is_negative;
for(int i = 1; i <= it; i++){
int x = 0;
for(int j = 1; j <= b.it || x > 0; j++){
x += c.a[i + j - 1] + a[i] * b.a[j];
c.a[i + j - 1] = x % 10;
x /= 10;
}
if(i + b.it - 1 > c.it) {
c.it = i + b.it - 1;
}
}
c.trim();
return c;
}
jclong operator/(const jclong& b) const {
jclong quotient;
quotient.init();
if(b.it == 0) {
cerr << "Error" << endl;
exit(1);
}
if(b.it == 1 && b.a[1] == 1 && !b.is_negative) {
quotient = *this;
return quotient;
}
quotient.is_negative = is_negative ^ b.is_negative;
jclong dividend = *this;
jclong divisor = b;
dividend.is_negative = false;
divisor.is_negative = false;
if(dividend < divisor) {
return quotient;
}
jclong temp;
temp.init();
int index = dividend.it;
for(; index > 0; index--) {
temp = temp * 10;
temp.a[1] = dividend.a[index];
temp.it = max(temp.it, 1);
temp.trim();
int count = 0;
while(!(temp < divisor)) {
temp = temp - divisor;
count++;
}
if(quotient.it > 0 || count > 0) {
quotient.a[++quotient.it] = count;
}
}
reverse(quotient.a + 1, quotient.a + quotient.it + 1);
quotient.trim();
return quotient;
}
jclong operator%(const jclong& b) const {
jclong remainder;
remainder.init();
if(b.it == 0) {
cerr << "Error" << endl;
exit(1);
}
// 取绝对值进行计算
jclong dividend = *this;
jclong divisor = b;
dividend.is_negative = false;
divisor.is_negative = false;
if(dividend < divisor) {
remainder = dividend;
remainder.is_negative = is_negative;
return remainder;
}
jclong temp;
temp.init();
int index = dividend.it;
// 试商法计算余数
for(; index > 0; index--) {
temp = temp * 10;
temp.a[1] = dividend.a[index];
temp.it = max(temp.it, 1);
temp.trim();
while(!(temp < divisor)) {
temp = temp - divisor;
}
}
remainder = temp;
remainder.is_negative = is_negative;
return remainder;
}
};
快速幂
ll pow(ll x,ll y,ll Mod){
if(y==0)return 1;
ll res = pow(x,y/2,Mod)%Mod;
if(y%2==0) return res*res%Mod;
return res*res%Mod*x%Mod;
}
线性质数筛
int f[N];
void init(int n){
for(int i=2;i<=n;i++) f[i] = 0;
for(int i=2;i<=n;i++){
if(f[i])continue;
for(int j=i+i;j<=n;j+=i){
f[j] = 1;
}
}
}
最大公约数
int gcd(int a, int b) {
if(b==0)return a;
return gcd(b,a%b);
}
排列组合
$$ A(n, k) = \frac{n!}{(n - k)!} $$
$$ C(n, k) = \frac{n!}{k! \cdot (n - k)!} $$
字符串
字符串哈希
直接判断hash值是否相等即可。
const int Smax = 26,Smin = 'a';
int gethash(string s,int Mod){
int ans=0;
for(int i=0;i<s.size();i++){
ans = ans*Smax+(s[i]-Smin);
ans %= Mod;
}
return ans;
}
字典树
struct node{
int Next[128];
int Value;
} Trie[N];int top=0;
void init(int n){
for(int j=0;j<128;j++)Trie[n].Next[j] = 0;
Trie[n].Value = 0;
}
void push(string s,int i=0,int rt=1){
Trie[rt].Value ++;
if(i>=s.size()) return ;
if(Trie[rt].Next[s[i]]==0){
init(++top);
Trie[rt].Next[s[i]] = top;
}
push(s,i+1,Trie[rt].Next[s[i]]);
}
int get(string s,int i=0,int rt=1){
if(i>=s.size())return Trie[rt].Value;
if(Trie[rt].Next[s[i]]==0)return 0;
return get(s,i+1,Trie[rt].Next[s[i]]);
}
KMP
string a,b; // a,b 下标 1~n,1~m
int Next[N],n,m;
void InitNext(string b){
Next[1] = 0;
int j = 0;
for(int i=2;i<=m;i++){
while(j>0 and b[i]!=b[j+1]){
j = Next[j];
}
if(b[i]==b[j+1]){
j++;
}
Next[i] = j;
}
}
void RunKMP(string a,string b){
int j=0;
for(int i=1;i<=n;i++){
while(j>0 and a[i]!=b[j+1]){
j = Next[j];
}
if(a[i]==b[j+1]){
j++;
}
if(j>=m){
cout << ( i - j + 1 ) << endl; // ans
j = Next[j];
}
}
}
时间复杂度 $O(n)$ ;
AC自动机
字典树 + KMP
struct node{
int Next[26];
int Value,Back,Left;
int cnt;
} AC[N];int top=0;
void init(int n,int lft,int v){
for(int i=0;i<26;i++)AC[n].Next[i] = 0;
AC[n].Value= v;
AC[n].Back = 0;
AC[n].Left = lft;
AC[n].cnt = 0;
}
void TrieAdd(string s){
int rt=1;
for(int i=0;i<s.size();i++){
if(AC[rt].Next[s[i]-'a']==0){
init(++top,rt,s[i]-'a');
AC[rt].Next[s[i]-'a'] = top;
}
rt = AC[rt].Next[s[i]-'a'];
}
AC[rt].cnt ++ ;
}
void ACinit(){
queue<int> q;
AC[1].Back = 0;
for(int i=0;i<26;i++){
if(AC[1].Next[i]==0)continue;
AC[AC[1].Next[i]].Back = 1;
q.push(AC[1].Next[i]);
}
while(!q.empty()){
int rt = q.front();q.pop();
int j = AC[AC[rt].Left].Back;
while(j>0 and AC[j].Next[AC[rt].Value]==0){
j = AC[j].Back;
}
if(j!=0){
j = AC[j].Next[AC[rt].Value];
}else j = 1;
AC[rt].Back = j;
for(int i=0;i<26;i++){
if(AC[rt].Next[i]!=0){
q.push(AC[rt].Next[i]);
}
}
}
}
int RunKMP(string a){
int j=1,ans=0;
for(int i=0;i<a.size();i++){
while(j>0 and AC[j].Next[a[i]-'a']==0){
j = AC[j].Back;
}
if(AC[j].Next[a[i]-'a']!=0){
j = AC[j].Next[a[i]-'a'];
}else j=1;
ans+=AC[j].cnt;
AC[j].cnt = 0;
}
return ans;
}
Manacher
int n,a[N],Len[N];
void InitStrToInt(string s){
n=1;a[n]=28;a[++n]=28;
for(int i=0;i<int(s.size());i++){
a[++n]=int(s[i]-'a'+1);
a[++n]=28; // add a wall
}
}
int Manacher_GetMaxhw(){
int j=0,ans=0; // j : max len effect
for(int i=1;i<=n;i++){
int NowAns=1;
if(Len[j]+j>i)
NowAns = min(Len[j-(i-j)],Len[j]+j-i);
while(a[i-NowAns]==a[i+NowAns]
and (NowAns+i<=n and i-NowAns>0)){
NowAns++;
}
Len[i]=NowAns;
if(Len[j]+j<i+Len[i]){
j = i;
}
ans = max(ans,Len[i]);
}
return ans-1;
}
时间复杂度 $O(n^2)$ ;