TobinMEng的代码模板大合集

代码模板。

巨长的代码模板。

拿来了高中的代码模板然后持续更新。

图论

图

图的储存和插入

int head[maxn], ver[maxm], Next[maxm], edge[maxm], tot;
inline void adde(int x, int y, int v) {
	Next[++tot] = head[x]; head[x] = tot;
	ver[tot] = y; edge[tot] = v;
} 

连通块的划分（图的染色）

void dfs(int x) {
    color[x] = cnt;
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (color[y]) continue;
        dfs(y);
    }
}
for (int i=1;i<=n;++i) {
    if (!color[i]) {
        cnt++;
        dfs(i);
    }
}

BFS遍历一个树/图

void bfs() {
    queue<int> q;
    memset(d, 0, sizeof(d));//如果搜索的是一棵树的话， 那么d数组指的是节点x在树中的深度。如果是一张图的话， d数组指的是x的层次， （从起点1走到x所要经历的最少点数）。
    q.push(1); d[1] = 1;
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}//bfs有两个重要的性质， 1.在访问过所有的第i层节点之后，才会开始访问i+1层节点2.任意时刻，队列里只会出现i层的节点和i+1层的节点，并且所有的第i层节点都在第i+1层节点之前。（简单来说就是满足“两端性”和“单调性”）
//并且dfs的时间复杂度和bfs的时间复杂度是相同的， 都为O(n+e)的时间复杂度，只不过限制两个算法的一个是堆栈大小， 一个是队列的大小

Dijkstra

简单的正确性证明

void Dijkstra(int x) {
    priority_queue<pair<ll ll> > q;
    for (int i=1;i<=n;++i)	dis[i] = INF, vis[i] = false;
    dis[x] = 0;
    q.push(make_pair(0, x));
    while(q.size()) {
        int x = q.top().second;	q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i], w = edge[i];
            if (dis[y] > dis[x] + w) {//由于是拿出现在堆中最小的点x来更新其相邻的点， 所以写的顺序需要注意
                dis[y] = dis[x] + w;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
}//适用于有向图和无向图中，只适用于边长不为负的图。时间复杂度为O((n+m)log(n));

SPFA

void SPFA(int x) {
	queue<int> q;
	for (int i=1;i<=n;++i)	dis[i] = INT, vis[i] = false;
	dis[x] = 0; q.push(x); vis[x] = true;
	while (q.size()) {
		int x = q.front();
		q.pop(); vis[x] = false;//vis表示该点是否在队列中
		for (int i=head[x];i;i=Next[i]) {
			int y = ver[i], w = edge[i];
			if (dis[y] > dis[x] + w) {
				dis[y] = dis[x] + w;
				if (vis[y] == false) {
					vis[y] = true;
					q.push(y);
				}
			}
		}
	}
}//适用于有向图和无向图中，可以计算负权图，可以用来判断负环。时间复杂度为O(nm);

Floyed

void Floyed() {
    for (int k=1;k<=n;++k) 
        for (int i=1;i<=n;++i) 
            for (int j=1;j<=n;++j) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}//多源最短路，可以有负权边。适用于大部分的情况。但是时间复杂度高达O(n³)。

Kruskal

struct node {
	ll x, y, v;
	friend bool operator < (const node&a, const node&b) {
		return a.v < b.v;
	}
}e[maxm];
void Kruskal() {
	for (int i=1;i<=n;++i)	f[i] = i;
    int cnt = 0;
    sort(e+1, e+1+m);
    for (int i=1;i<=m;++i) {
        int a = find(e[i].x), b = find(e[i].y);
        if (a == b)	continue;
        else {
            ans += e[i].v;
            f[b] = a;
            ++cnt;
        }
        if (cnt == n - 1)	break;
    }
}//这个是求出最小生成树的所有边的权值和， 其实可以可以在计算所有边的权值和的同时从新建一棵最小生成树

并查集

void init() {
    for (int i=1;i<=n;++i) f[i] = i;
}//使用并查集的初始化
int find(int x) {
    return (f[x] == x) ? x : f[x] = find(f[x]);
}//进行路径压缩的并查集
void un(int x, int y) {
    int a = getf(x), b = getf(y);
    if (a == b) return;
    else f[b] = a;
}

拓扑排序

void Topsort() {
    queue<int> q;
    for (int i=1;i<=n;++i) {
        if (du[i] == 0) {
            q.push(i);
        }
    }//找到入度为0的点， 入队
    while(q.size()) {
        int x = q.front(); q.pop();
        a[++tot] = x;
        for (int i=head[x]; i; i=Next[i]) {
            if (--du[ver[i]] == 0) {
                a[++tot] = ver[i];
                q.push(ver[i]);
            }
        }
    }
}//有向图中使用，记清楚！必须是有向图。显然的是，在进行完成拓扑排序之后，图中还留下来的东西就是一些环。即tot != n;
//算法的应用：1.有向图找环（无向图是不能使用拓扑排序的）

二分图最大匹配

bool find(int x) {
    for (int i=1;i<=m;++i) {  
        if (Link[x][i] && !used[i]) {
            used[i] = true;
            if (girl[i] == 0 || find(girl[i])) {
                girl[i] = x;
             	return true;   
            }
        }
    }
    return false;
}//其实就是在寻找增广路的过程
int Maxmatch() {
    int ans = 0;
    for (int i=1;i<=n;++i) {
        memset(used, 0, sizeof(used));
        if (find(i)) ++ans;
    }
    return ans;
}//匈牙利算法如果使用邻接矩阵的话可以在O(n³)的时间内找到一个二分图的最大匹配数。空间复杂度是一个邻接矩阵(n²)。

Tarjan求强联通分量

void Tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    Stack[++top] = x;
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }else if (vis[ver[i]]) {
            low[x] = min(low[x], dfn[ver[i]]);
        }
    }
    if (dfn[x] == low[x]) {
		int temp = 0;
		++cnt;//一个新的强联通块
		do{
			temp = Stack[--top];
			color[temp] = cnt;//color里存的是第i个点属于第几个联通块
			vis[temp] = false;
		}while(x != temp);
	}
}
int main() {
    for (int i=1;i<=n;++i) {
        if (!vis[i])
            tarjan(i);//因为这张图可能不连通
    }
}

缩点

void Tarjan() {
    dfn[x] = low[x] = ++tim;
    Stack[++top] = x;
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (!dfn[ver[i]]) {
            Tarjan(ver[i]);
            low[x] = min(low[x], low[ver[i]]);
        }else if (vis[ver[i]]) {
            low[x] = min(low[x], dfn[ver[i]]);
        }
    }
    if (low[x] == dfn[x]) {
        int temp;
        ++cnt;
        do {
            temp = Stack[top--];
            color[temp] = cnt;
            vis[y] = false;
        }while(x != temp)
    }
}
/*缩点，其实就是拿着邻接表，和强连通分量们来建一张新的图，在新的图中，点就是原来的强连通分量，边的具体操作有点复杂，现在具体说一说，大致意思就是：既然点都变成了强连通分量，那么边就应该在他们当中去连接不是吗?那什么和什么连？似乎可以看到，连接同一个强连通分量里的点是没有任何意义的，所以就好办了，跑一遍原邻接表，如果一条边（u，v,w）的u和v不在同一个强连通分量中，那么就在新图中连这条边，就这样点就缩好了。听起来也许有些玄幻，但是它就真真切切的完成了？！*/
for (int i=1;i<=m;++i) {//一共m条边
    if (color[a[i]] != color[b[i]]) {//如果两条边的两个端点不在一个强连通分量里面， 那么我们在这两个点之间连一条边
        adde(color[a[i]], color[b[i]], z[i]);
    }
}
//等于用剩下的信息建了一张新图

树

LCA

树上倍增

void bfs() {
    t = log(n)/log(2);
    queue<int> q;
    d[s] = 1;
    q.push(s);
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x]; i; i=Next[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x]　＋ 1;
            f[y][0] = x;
            for (int j=1;j<=t;++j) {
                f[y][j] = f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}
int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i=t;i>=0;--i) {
        if (d[f[y][i]] >= d[x])	y = f[y][i];
    }
    if (x == y) return x;
    for (int i=t;i>=0;--i) {
        if (f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

Tarjan算法离线求LCA

void init() {
    int a, b;
    for (int i=1;i<n;++i) {
        a = Read(); b = Read();
        adde(a, b); 
        adde(b, a);
    }//一棵树n-1条边
    for (int i=1;i<=k;++i) {
        a = Read(); b = Read();
        qadde(a, b);
        qadde(b, a);
    }//k个询问
    for (int i=1;i<=n;++i) f[i] = i;
}
void Tarjan(int x) {
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i]) {
        if (vis[ver[i]])  continue;
        tarjan(ver[i]);
        f[ver[i]] = x;
    }
    for (int i=qhead[x]; i; i=Next[i]) {
        if (vis[qver[i]]) 
            ans[edge[i]] = getf(qver[i]);
    }
}

树的直径

void dp(int x) {
    vis[x] = true;
    for(int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);//d数组的含义是从x节点出发走向x的子树， 所能到达的最远距离。
        //那么树上最长链的距离即为从x到x的子节点yi的距离加上x到x的子节点yj的距离加上d[yi]再加上d[yj]即可
        //d[x]中存的是从x走向他的前i个子节点最长的路径， 再加上当前的点到它子节点最长的路径即可得到x所在链的长度， 取一下max即为最长链的长度， 即为树的直径
    }
}

树的重心

void dfs(int x) {//树的重心的定义就是将该点删去之后所形成的最大的子树最小的那个点
    vis[x] = true;
    size[x] = 1;//子树x的大小
    int max_part = 0;//删掉子树x后分成的最大子树的大小
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y])	continue;
        dfs(y);
        size[x] += size[y];//从子节点向上更新
        max_part = max(maxn_part, size[y]);//x的子节点中最大的那个节点的size
    }
    	max_part = max(maxn_part, n - size[x]);//现在max_part中储存的是该节点删去之后形成的若干个子树最大的那个的大小 
    //n - max_part里存的是x向上连接他的父亲节点的那一棵子树的大小。
    if (max_part < ans) {
        ans = max_part;
        pos = x;
    }
}

树的各点子树的大小

void dfs(int x) {
    vis[x] = true;
    size[x] = 1;
    for (int i=head[x]; i; i=Next[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
        size[x] += size[y];
    }
}

树的各点的深度

void dfs(int x) {
    vis[x] = true;
    for (int i=head[x]; i; i=Next[i) {
        int y = ver[i];
        if (vis[y])	continue;
        d[y] = d[x] + 1;
        dfs(y);
    }
}
void bfs(int x) {
    memset(d, 0, sizeof(d));
	queue<int> q;
    d[x] = 1; q.push(x);
    while(q.size()) {
        int x = q.front(); q.pop();
        for (int i=head[x];i;i=Next[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}

数论

基础数论

求一个数二进制的每个1的位置

int H[37];
void bit(int n) {
	for (int i = 0;i < 36; ++i) H[(1ll << i) % 37] = i;
	while(n > 0) {
		cout << H[(n & -n) % 37] << ' ';
		n -= n & -n;
	}
	cout << endl;
}
bit(9) // 0 3

Gcd 和 Lcm

int gcd(int a, int b) {
    return b? gcd(b, a%b) : a;
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

线性筛求素数

ll prime[maxn], Size = 0;
bool vis[maxn]; 
inline void init() {
    memset(vis, true, sizeof(vis));
    memset(prime, 0, sizeof(prime));
    vis[1] = false;
    for (int i=2;i<=n;++i) {
        if (vis[i]) prime[++Size] = i;
        for (int j=1;j<=Size&&i*prime[j]<=n;++j) {
            vis[i*prime[j]] = false;
            if (i % prime[j] == 0)	break;
        }
    }
}//时间复杂度O(n)

素数判断

bool is_prime(ll x) {
	if (x == 2) return true; 
	for(int i=2;i<=sqrt(p);++i) if(x % i == 0) return false;
	return true;
}

EXGCD

void ex_gcd(int a, int b, int &x, int &y, int &d){
      if (!b) {d = a, x = 1, y = 0;}
      else{
          ex_gcd(b, a % b, y, x, d);
          y -= x * (a / b);
      }
  }

求逆元

//如果p是素数那么可以使用小费马定理
int inv(int a, int p) {
	return power(a, p - 2, p);    
}
//如果p不是素数那么可以使用EXgcd
int inv(int t, int p){//如果不存在，返回-1 
    int d, x, y;
    ex_gcd(t, p, x, y, d);
    return d == 1 ? (x % p + p) % p : -1;
 }//如果返回-1则这个数没有逆元
//如果要求出n以内所有在膜p情况下的的逆元,可以线性递推
void inv(int n, int p) {
    inv[1] = 1;
    for (int i=2;i<=n;++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

快速幂

int power(int a, int b, int p) {
    int res = 1 % p;
    for(; b; b >>= 1) {
        if (b & 1) res = (long long)res * a % p;
        a =(long long)a * a % p;
    }
    return res;
}

龟速乘

ll Mul(ll a, ll b, ll p) {
    ll res = 0;
    for(; b; b >>= 1) {
        if (b & 1) res = (res % p + a % p) % p;
        a = (a << 1) % p;
    }
    return res;
}//可以防止两数相乘过大炸掉long long

组合数学

void init() {
    memset(c, 0, sizeof(c));
    c[1][0] = c[1][1] = 1;
    for (int i=2;i<=maxn;++i) {
        c[i][0] = c[i][i] = 1;
        for (int j=1;j<i;++j) {
            c[i][j] =(c[i-1][j] % mod + c[i-1][j-1] % mod)% mod;
        }
    }
}

矩阵乘法

struct Mat {
    a[maxn][maxn];
}A, e;
Mat Mul(Mat x, Mat y) {
    Mat c;
    for (int i=1;i<=n;++i)
    for (int j=1;j<=n;++j)
        c.a[i][j] = 0;
   	for (int k=1;k<=n;++k)
	for (int i=1;i<=n;++i)	
	for (int j=1;j<=n;++j)
        c.a[i][j] = c.a[i][j] % mod + (x.a[i][k] * y.a[k][j] % mod) % mod;
    return c;
}
Mat power(Mat x, int p) {
    Mat ans = e;
    for (; b; b>>=1) {
        if (b & 1) ans = Mul(ans, a);
        a = Mul(a, a);
    }
    return ans;
}

博弈论

巴什博奕

/*
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。
结论：
	n % (m + 1) == 0 后手必胜
	n % (m + 1) != 0 先手必胜
*/
/*
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得输。
结论：
	n % (m + 1) == 1 后手必胜
	n % (m + 1) != 1 先手必胜
*/

威佐夫博奕

/*
有两堆各若干个物品为x,y，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。
*/
inline bool check(int x, int y) {
	int a = min(x, y), b = max(x, y);
	double c = (double)abs(b - a);
	double r = (sqrt(5.0) + 1) / 2;//1.618
	int tmp = int(c * r);
	if (a == tmp) return 0; //后手必胜 
	else return 1; //先手必胜 
}

尼姆博奕

/*
有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。
结论：
	n个数字进行异或，如果结果 = 0，后手必胜。如果结果 != 0，先手必胜。
*/

斐波那契博弈

/*
有一堆个数为n的石子，游戏双方轮流取石子，满足：
	（1）先手不能在第一次把所有的石子取完；
	（2）之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。 约定取走最后一个石子的人为赢家。
结论：
	当n为Fibonacci数时，先手必败。即存在先手的必败态当且仅当石头个数为Fibonacci数。 
*/

数据结构

基本数据结构

链表

inline void init() {
    a[1].pre = 0;
    a[1].next = -1;
    a[0].next = 1;
    a[0].pre = -1;
}
inline void insert(int x, int k, int p) {
    if (p == 1) {
        a[x].pre = k;
        a[x].next = a[k].next;
        a[a[k].next].pre = x;
        a[k].pre = x;
    }else {
        k = a[k].pre;
        a[x].pre = k;
        a[x].next = a[k].next;
        a[a[k].next].pre = x;
        a[k].next = x;
    }
    return;
}//在k的前或者后面插入一个值为x的点
//p == 1 时表示在k的后面插入了x
//p == 0 时表示在k的前面插入了x
inline void del(int x) {
    if (a[x].pre != -1) {
        a[a[x].pre].next = a[x].next;
        a[a[x].next].pre = a[x].pre;
        a[x].pre = -1;
    }
}
//一个数的pre为-1表示这个点已经被删除
for (int i=a[0].next;i!=-1;i=a[i].next) {
    //一个链表的遍历
}

队列

//STL
queue<int> q;

q.push(x);
q.pop();
int x = q.front();
int size = q.size();
bool is_empty = q.empty();

//手写一个队列
inline void init(){
    head = 0; tail = 0;
	memset(q, 0, sizeof(q));
}
inline void push(int x) {q[++tail] = x;}
inline void pop()		{head++;}
inline int  front()		{return q[tail];}
inline bool empty()		{return head >= tail;}
inline int 	size()		{return tail - head;}

优先队列

//STL
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int> > q;

q.push(x);
q.pop();
int x = q.top();
int size = q.size();
bool is_empty = q.empty();
//不会手写

栈

stack<int> s;
s.push(x);
s.pop();
int x = s.top();
bool is_empty = s.empty();

单调队列

单调栈

ST表

inline int lowbit(int x) {return x & (-x);}
inline int query(int l, int r) {
	int t = log(abs(r - l + 1)) / log(2);
	return max(f[l][t], f[r - (1 << t) + 1][t]);
}
void ST_init(int t = log(n) / log(2) + 1) {
	rep(i, 1, n) f[i][0] = a[i];
	rep(j, 1, t - 1) {
		rep(i, 1, n - (1 << j) + 1) {
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
	}
}//RMQ的离线算法，O(nlogn)的预处理，O(1)的查询。

树状数组

inline void add(int x, int v) {
    for (; x <= n; x += x & (-x))	c[x] += v;
}
inline int ask(int x) {
    int res = 0;
    for (; x; x -= x & (-x))	res += c[x];
    return x;
}
inline void init() {
    for (int i=1;i<=n;++i)	add(i, a[i]);
}
inline int sum(int x, int y) {
    return ask(y) - ask(x - 1);
}
add(x, v);//单点修改x加上v
int sum = sum(a, b)//区间求和， 从a到b的区间
//区间修改，区间求和
inline void change(int l, int r, ll d) {
	    
}

线段树

struct Segment {
    int l, r;
    ll dat, add;
    #define l(x)	tree[x].l
    #define r(x)	tree[x].r
    #define dat(x)	tree[x].dat
    #define add(x)	tree[x].add
}tree[maxn << 2];
int a[maxn];

inline void update(int p) {
    dat(p) = dat(p<<1) + dat(p<<1|1);
}
void build(int p, int l, int r) {
    l(p) = l; r(p) = r;
    if (l == r) {dat(p) = a[l];return;}
    int mid = (l + r) >> 1;
    build(p<<1,	l, mid);
    build(p<<1|1,mid+1, r);
    update(p);
}
void spread(int p) {
    if (add(p)) {
        dat(p<<1) += add(p) * (r(p<<1) - l(p<<1) + 1);
        dat(p<<1|1) += add(p) * (r(p<<1|1) - l(p<<1|1) + 1);
        add(p<<1) += add(p);
        add(p<<1|1) += add(p);
        add(p) = 0;
    }
}
void change(int p, int l, int r, int d) {
    if (l <= l(p) && r >= r(p)) {
        dat(p) += (long long)d * (r(p) - l(p) + 1);
        add(p) += d;
        return;
    }
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    if (l <= mid)	change(p<<1, l, r, d);
    if (r > mid)	change(p<<1|1, l, r, d);
    update(p);
}
long long ask(int p, int l, int r) {
    if (l <= l(p) && r >= r(p))	return dat(p);
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    long long res = 0;
    if (l <= mid)	res += ask(p<<1, l, r);
    if (r > mid)	res += ask(p<<1|1, l, r);
    return res;
}

分块

void build() {
    block = sqrt(n);
    num = n / block;  if (n % block) num++;
    for (int i=1;i<=num;++i)
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    r[num] = n;
    for (int i=1;i<=n;++i) {
        a[i] = Read();
        belong[i] = (i - 1) / block + 1;
        sum[belong[i]] += a[i];
    }
}
void add(int x, int y, int d) {
    for (int i=x;i<=min(x, r[belong[x]]);++i) 
        a[i] += d, sum[belong[i]] += d;
    if (belong[x] != belong[y]) {
        for (int i=l[belong[y]];i<=y;++i)
            a[i] += d, sum[belong[i]] += d;
    }
    for (int i=belong[x]+1;i<=belong[y]-1;++i)
        sum[i] += block * d, tag[i] +=d;
}
int ask(int x, int y) {
    ll ans = 0;
    for (int i=x;i<=min(x, r[belong[x]]);++i) 
        ans += tag[belong[i]] + a[i];
    if (belong[x] != belong[y]) {
        for (int i=l[belong[y]];i<=y;++i)
            ans += tag[belong[i]] + a[i];
    }
    for (int i=belong[x]+1;i<=belong[y]-1;++i)
        ans += sum[i];
    return ans;
}

字符串

基本字符串算法

Hash表

unsigned long long h(char s[]) {
    int len = strlen(s);
    unsigned long long ans = 0;
    for (int i=0;i<len;++i) 
		ans += ans * 131 + (unsigned long long)(s[i] - 'a' + 1);
	return ans;
}

KMP

void prekmp() {
    m = strlen(b + 1);
    Next[1] = 0;
    for (int i=2,j=0;i<=m;++i) {
        while(j && b[i] != b[j + 1])j = Next[j];
        if (b[i] == b[j + 1]) ++j;
        Next[i] = j;
    }
}
ll kmp() {
    n = strlen(a + 1); ans = 0;
    for (int i=1,j=0;i<=n;++i) {
        while(j && a[i] != b[j + 1])j = Next[j];
        if (a[i] == b[j + 1]) ++j;
        if (j == m) {
            ++ans;
            j = Next[j];
        }
    }
    return ans;
}

Manacher

void init() {
	int len = strlen(str), j = 1;
	s[0] = '$', s[1] = '#';
	rep(i, 0, len-1) {
		s[++j] = str[i];
		s[++j] = '#';
	}
	s[++j] = '\0';
}
int Manacher() {
	int len = strlen(s);
	int mx = 0, id = 0, ans = -1;
	rep(i, 0, len - 1) {
		if (mx>i) p[i]=min(mx-i, p[2*id-i]);else p[i] = 1;
		while(i-p[i]>=0&&s[i+p[i]]==s[i-p[i]])p[i]++;
		if(p[i]+i>mx) mx = p[i]+i, id = i;
		ans = max(ans, p[i] - 1);
	}
	return ans;
}

搜索

基本搜索算法

Dfs

void dfs(int x) {
    if (x > n) {
        ...
        return;
    }
    ...
	dfs(x + 1);
    
}

Bfs

void bfs(int x) {
    queue<int> q;
    q.push(x);
    while(q.size()) {
        int x = q.front();
        ...
        q.push(...);
    }
}

迭代加深

其他

常见思路

二分

//求小于等于x最大的那一个
inline bool check(int x) {
    if (...) return true;
    else return false;
}
int work() {
    int l = 0; r = max_n;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))	l = mid;
        else r = mid - 1;
    }
    return l;
}
//求大于等于x的最小的那一个
int work() {
    int l = 0; r = max_n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

预热模板

开新题的模板

#include<bits/stdc++.h>
#define rep(i, a, n) for (int i=a;i<=n;++i)
#define per(i, n, a) for (int i=n;i>=a;--i)
#define endl '\n'
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn =
inline void write(int x) {if(x > 9) write(x/10);putchar(x % 10 + '0');return;}
inline int Read() {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main() {
    
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <stack> 
#define rep(i, a, n) for (int i=a;i<=n;++i)
#define per(i, n, a) for (int i=n;i>=a;--i)
#define endl '\n'
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn = 
inline void write(int x) {if(x > 9) write(x/10);putchar(x % 10 + '0');return;}
inline int Read() {
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main() {
	return 0;
}

关联文件

inline void send() {
	freopen("1.in",  "r",  stdin);
	freopen("1.out", "w", stdout);
}

快读fread

ll f[maxn], c[maxn], ans = 0, n, tmp;
char buf[1<<15], *fs, *ft;
inline char getc(){return(fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline ll Read() {
    ll x=0,f=1;char ch=getc();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}