『C/C++』2019CSP模板

思维导图

快读

inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

逆序对

void msort(int s, int t)
{
	if (s == t) return; //如果只有一个数字则返回，无须排序
	int mid=(s+t)/2;
	msort(s,mid); //分解左序列
	msort(mid+1,t); //分解右序列
	int i = s, j = mid + 1, k = s; //接下来合并
	while (i <= mid && j <= t)
	{
		if (a[i] <= a[j])r[k++] = a[i++];
		else
		{
			r[k++] = a[j++]; ans += mid - i + 1;
		}//统计产生逆序对的数量
	}
	while (i <= mid) r[k++] = a[i++]; //复制左边子序列剩余
	while(j<=t)r[k++]=a[j++];//复制右边子序列剩余
	for (int i = s; i <= t; i++) a[i] = r[i]; return 0;
}

朴素Dijkstra

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1024;
const int M = 1024;
struct Edge
{
	int to, next, w;
}edge[M];
int head[M], cnt, n, m, s, cur;
bool v[N];
long long d[N], Min;
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
inline void add(int a, int b, int c)
{
	edge[++cnt].next = head[a];
	edge[cnt].to = b;
	edge[cnt].w = c;
	head[a] = cnt;
}
int main()
{
	n = read(); m = read(); s = read();
	for (int i = 1; i <= n; i++)d[i] = INF;
	for (int i = 1; i <= m; i++)
	{
		int a=read(), b=read(), c=read();
		add(a, b, c);
	}
	d[s] = 0; cur = s;
	while (!v[cur])
	{
		v[cur] = 1; Min = INF;
		for (int i = head[cur]; i; i = edge[i].next)
		{
			if (!v[edge[i].to] && d[edge[i].to] > d[cur] + edge[i].w)
				d[edge[i].to] = d[cur] + edge[i].w;
		}
		for (int i = 1; i <= n; i++)
			if (!v[i] && Min > d[i])
			{
				Min = d[i];
				cur = i;
			}
	}
	for (int i = 1; i <= n; i++)
		printf("%lld ", d[i]);
}

优先队列优化的Dijkstra

void Dijkstra(int s)
{
	priority_queue<pair<int, int> >q;
	//memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++)d[i] = INF;
	memset(v, 0, sizeof(v));
	d[s] = 0;
	q.push(make_pair(0, s));
	while (!q.empty())
	{
		register int now = q.top().second; q.pop();
		if (v[now])continue;
		v[now] = 1;
		for (int i = head[now]; i; i = edge[i].next)
		{
			int son = edge[i].to;
			if (d[son] >= d[now] + edge[i].w)
			{
				d[son] = d[now] + edge[i].w;
				q.push(make_pair(-d[son], son));
			}
		}
	}
}

标准他死了SPFA

void SPFA(int s)
{
    for (int i = 1; i <= n; i++)
		if (i != s)d[i] = INF;
	q.push(s); vis[s] = 1;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for (int i = head[x]; i; i = edge[i].next)
		{
			int son = edge[i].to;
			if (d[son] > d[x] + edge[i].w;)
			{
				d[son] = d[x] + edge[i].w;
				if (!vis[son])
				{
					q.push(son);
					vis[son] = 1;
				}
			}
		}
	}
}

标准弗洛伊德

void floyd()
{
    for (k = 1; k <= n; k++) //枚举断点
		for (i = 1; i <= n; i++) //S
			for (j = 1; j <= n; j++) //T
			{
				if (d[i][k] + d[k][j] < d[i][j])
				{
					d[i][j] = d[i][k] + d[k][j];
					path[i][j] = path[i][k];
				}
			}
}

查集有向图查找最小环

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 200002;
int f[N], d[N], n, Min=INF;
//f[i]:i的祖先节点 d[i]:i到祖先节点的距离
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
int fa(int x)
{
	if (f[x] != x)
	{
		int last = f[x];
		f[x] = fa(f[x]);
		d[x] += d[last];
	}
	return f[x];
}
void check(int a, int b)
{
	int x = fa(a), y = fa(b);
	if (x != y)
	{
		f[x] = y;
		d[a] = d[b] + 1;
	}
	else Min = min(Min, d[a] + d[b] + 1);
}
int main()
{
	freopen("C:\\Users\\97618\\Desktop\\input.txt", "r", stdin);
	n = read();
	for (int i = 1; i <= n; i++)f[i] = i;
	for (int i = 1; i <= n; i++)
	{
		int x = read();
		check(i, x);
	}
	printf("%d", Min);
}
//https://www.luogu.org/problem/P2661

Kruskal最小生成树

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read()
{
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct Edge
{
    int u,v,w;
}edge[200005];
int fa[5005],n,m,ans,eu,ev,cnt;
il bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
//快排的依据（按边权排序）
il int find(int x)
{
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
//并查集循环实现模板，及路径压缩，不懂并查集的同学可以戳一戳代码上方的“并查集详解”
il void kruskal()
{
    sort(edge,edge+m,cmp);
    //将边的权值排序
    for(re int i=0;i<m;i++)
    {
        eu=find(edge[i].u), ev=find(edge[i].v);
        if(eu==ev)
        {
            continue;
        }
        //若出现两个点已经联通了，则说明这一条边不需要了
        ans+=edge[i].w;
        //将此边权计入答案
        fa[ev]=eu;
        //将eu、ev合并
        if(++cnt==n-1)
        {
            break;
        }
        //循环结束条件，及边数为点数减一时
    }
}
int main()
{
    n=read(),m=read();
    for(re int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    //初始化并查集
    for(re int i=0;i<m;i++)
    {
        edge[i].u=read(),edge[i].v=read(),edge[i].w=read();
    }
    kruskal();
    printf("%d",ans);
    return 0;
}

Prim最小生成树

void prim()
{
	priority_queue<pair<int, int> >q;
	memset(d, 0x3f, sizeof(d));
	memset(v, 0, sizeof(v));
	d[1] = 0;
	q.push(make_pair(0, 1));
	while (tot<n)
	{
		register int now = q.top().second; q.pop();
		if (v[now])continue;
		v[now] = 1; ans += d[now]; tot++;
		for (int i = head[now]; i; i = edge[i].next)
		{
			int son = edge[i].to;
			if (v[son])continue;
			if (d[son] >= /*d[now] +*/ edge[i].w)
			{
				d[son] = /*d[now] +*/ edge[i].w;
				q.push(make_pair(-d[son], son));
			}
		}
	}
}

Tarjan强连通分量

void Tarjan(int now)
{
	dfn[now] = low[now] = ++Time;
	S.push(now); inS[now] = 1;
	for (int i = head[now]; i; i = edge[i].next)
	{
		int son = edge[i].to;
		if (!dfn[son])
		{
			Tarjan(son);
			low[now] = min(low[now], low[son]);
		}
		else if (inS[son])
			low[now] = min(low[now], dfn[son]);
	}
    int k;
	if (low[now] == dfn[now])
	{
		ring++;
		do
		{
			k = S.top(); S.pop();
			inS[k] = 0;
            belone[k]=ring;
            ringsize[ring]++;
//===================这里吐出来的k都是同一个环中的元素======================
//=========================自行对k做需要的处理============================
		} while (now != k);
	}
}

Tarjan割点

#include<bits/stdc++.h>
#define N (1000000+10)
using namespace std;
int a[N],next[N],head[N],dfn[N],low[N],Time,size;
bool cut[N];
void add(int x,int y)
{
	a[++size]=y;
	next[size]=head[x];
	head[x]=size;
}
void tarjan(int now, int fa)
{
	int snum = 0;
	dfn[now] = low[now] = ++Time;
	for (int i = head[now]; i; i = edge[i].next)
	{
		int son = edge[i].to;
		if (!dfn[son])
		{
			snum++;
			tarjan(son,fa);
			low[now] = min(low[now], low[son]);
			if (low[son] >= dfn[now] && now != fa)cut[now] = true;//两个条件
			if (now == fa && snum >= 2)cut[now] = true;
		}
		else low[now] = min(low[now], dfn[son]);
	}
}
int main()
{
	int n,m,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int tmp1,tmp2;
		scanf("%d%d",&tmp1,&tmp2);
		add(tmp1,tmp2);
		add(tmp2,tmp1);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])tarjan(i,i);
	for (int i=1;i<=n;i++)if(cut[i])ans++;
    printf("%d\n",ans);
    for (int i=1;i<=n;i++)if(cut[i]) printf("%d ",i);
}

拓扑排序

#include<bits/stdc++.h>
using namespace std;
struct Edge
{
    int to,w,next;
}a[100024];
int head[100024],rd[100024],in[100024],dp[100024],n,m,size,Max;
bool stop[10024],done[10024][10024];
/*
拓扑排序执行步骤
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
*/
inline void add(int x,int y)
{
    a[++size].to=y;
    a[size].next=head[x];
    head[x]=size;
}
inline void tuopusort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)//选择入度为0的点一起处理
    if(rd[i]==0)
    q.push(i);

    while(!q.empty())
    {
        int fa=q.front();q.pop();//一个一个吐出来处理
        for(int i=head[fa];i;i=a[i].next)
        {
            int son=a[i].to;
            rd[son]--;
            if(rd[son]==0)
            {
                q.push(son);
                dp[son]=max(dp[fa]+1,dp[son]);
                Max=max(dp[son],Max);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int s;scanf("%d",&s);
        memset(stop,0,sizeof(stop));
        memset(in,0,sizeof(in));
        for(int j=1;j<=s;j++)scanf("%d",&in[j]),stop[in[j]]=1;
        for(int j=in[1];j<=in[s];j++)
        if(!stop[j])
        for(int k=1;k<=s;k++)
        if(!done[j][in[k]])
        {
            done[j][in[k]]=1;
            rd[in[k]]++;
            add(j,in[k]);
        }
    }
    tuopusort();
    cout<<Max+1;
}

二分最大值最小

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

二分最小值最大

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

扩展欧几里得

void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}

朴素并查集

#include<bits/stdc++.h>
using namespace std;
int n,m,p,x,y,fa[10009];
int find(int x)
{
	while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
void combine(int a,int b)
{
	fa[find(a)]=find(b);
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		combine(x,y);
	}
	for(int i=1;i<=p;i++)
	{
		cin>>x>>y;
		if(find(x)==find(y))cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

LCA最近公共祖先(倍增)

int depth[N], f[N][22];
void dfs(int now, int fa)//初始调用dfs(root, 0);
{
	depth[now] = depth[fa] + 1;
	f[now][0] = fa;
	for (int i = 1;i<=21; i++)
		f[now][i] = f[f[now][i - 1]][i - 1];
	for (int i = head[now]; i; i = edge[i].next)
		if (edge[i].to != fa)
			dfs(edge[i].to, now);
}
int lca(int x, int y)
{
	if (depth[x] < depth[y])swap(x, y);
	for (int i = 21; i >=0; i--)
	{
		if (depth[f[x][i]] >= depth[y])
			x = f[x][i];
		if (x == y)return x;
	}
	for (int i = 21; i >= 0; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

快速幂取模

int QuickPow(int x, int y, int z)
{
	x %= z;
	int res = x;
	int ans = 1;
	while (y)
	{
		if (y & 1)ans = ans * res % z;
		res = res * res % z;
		y = y >> 1;
	}
	return ans % z;
}

标准KMP

#include<bits/stdc++.h>
using namespace std;
const int N=1000024;
string a,b;
int next[N],n,k;
inline void Getnext()//针对子串
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<b.length())//从头到尾
      if(j==-1 || b[i]==b[j])//匹配成功，继续下一个字符
          next[++i]=++j;
      else j=next[j];//不成功，回调再匹配
}
inline void KMP()
{
    int i=0,j=0;
    while(i<a.length())
    {
        if(j==-1 || a[i]==b[j])//j==-1（开头跳位）或a[i]==b[j]匹配成功，令i++，j++，继续匹配下一个字符
            i++,j++;
        else j=next[j];//不成功，进行合理移动，再来一遍
        if(j==b.length())//末尾成功，整串成功，输出结果并移动再继续
        {
            j=next[j];
            cout<<i-b.length()+1<<endl;//母串位置-子串长度+1
        }
    }
}
int main()
{
    cin>>a>>b;
    Getnext();
    KMP();
    for(int i=1;i<=b.length();++i)
        printf("%d ",next[i]);//输出next数组（实际上不同版本有不同），此处真正使用的部分是 0~lenb-1
    return 0;
}

ST之区间最大值

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[100001], st[100001][100],n,m;
void prework()
{
    for (int i = 1; i <= n; i++)st[i][0] = a[i];
    for (int j = 1; j <= log2(n); j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int ask(int l, int r)
{
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    prework();
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", ask(l, r));
    }

}

欧拉筛质数

int vis[maxn],prime[N],cnt=0;//cnt用来计数，prime数组保存素数
void prework(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prime[cnt++]=i;//如果未被标记过，则表示为素数
		for(int j=0;j<cnt && i*prime[j]<=n;j++)//当标记的合数超出范围则退出
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;//关键步骤
		}
	}
}
bool isprime(int x)
{
    return vis[x];
}

树状数组1：单点修改

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1010000;
int a[MAX], c[MAX], n, m;
int lowbit(int x) { return x & (-x); }
int getsum(int x)
{
	int ans = 0;
	for (int i = x; i; i -= lowbit(i))
		ans += c[i];
	return ans;
}
void updata(int x, int y)
{
	for (int i = x; i <= n; i += lowbit(i))
		c[i] += y;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]), updata(i,a[i]);
	while (m--)
	{
		int f,x, y;
		scanf("%d%d%d", &f, &x, &y);
		if (f == 1)updata(x, y);
		else if (f == 2)printf("%d\n", getsum(y) - getsum(x-1));
	}
}

树状数组2：区间修改

//树状数组代码
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,q,m,mod,x,y,tree[500001];
ll lowbit(ll num){
	return num&-num;//返回值为二进制下num从左往右第一个1的位置
}
void build(ll s,ll num){
	for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;//当s在i的范围内 第num位数组加上num
}
ll ask(ll s){
	ll ans=0;
	for(ll i=s;i>=1;i-=lowbit(i)) ans+=tree[i];//建树的反操作
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&m);
		build(i,m);//建立树状数组
	}
	for(int i=1;i<=q;i++){
		scanf("%lld%lld%lld",&mod,&x,&y);//输入1或2
		if(mod==1) build(x,y);//修改与建树可以共用一个函数
		if(mod==2) printf("%lld\n",ask(y)-ask(x-1)/*思考为什么是x-1*/);//区间查询则为右边界前缀和减去左边界前缀和
	}
}

线段树1

#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
struct node
{
	int l, r;
	long long pre, add;
}t[4*N+2];
int a[N], n, m;
void build(int x, int l, int r)
{
	t[x].l = l; t[x].r = r;
	if (l == r)
	{
		t[x].pre = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
	t[x].pre = t[x * 2].pre + t[x * 2 + 1].pre;
}
void pushdown(int x)
{
	if (t[x].add)
	{
		t[x * 2].pre += t[x].add * (t[x * 2].r - t[x * 2].l + 1);
		t[x * 2 + 1].pre += t[x].add * (t[x * 2 + 1].r - t[x * 2 + 1].l + 1);
		t[x * 2].add += t[x].add;
		t[x * 2 + 1].add += t[x].add;
		t[x].add = 0;
	}
}
void change(int p, int x, int y, int z)
{
	if (x <= t[p].l && y >= t[p].r)
	{
		t[p].pre += (long long)z * (t[p].r - t[p].l + 1);
		t[p].add += z;
		return;
	}
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (x <= mid)change(p * 2, x, y, z);
	if (y > mid)change(p * 2 + 1, x, y, z);
	t[p].pre = t[p * 2].pre + t[p * 2 + 1].pre;
}
long long ask(int p, int x, int y)
{
	if (x <= t[p].l && y >= t[p].r) return t[p].pre;
	pushdown(p);
	int mid = (t[p].l + t[p].r) >> 1;
	long long ans = 0;
	if (x <= mid) ans += ask(p * 2, x, y);
	if (y > mid) ans += ask(p * 2 + 1, x, y);
	return ans;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		int q, x, y, z;
		scanf("%d", &q);
		if (q == 1)
		{
			scanf("%d%d%d", &x, &y, &z);
			change(1, x, y, z);
		}
		else
		{
			scanf("%d%d", &x, &y);
			printf("%lld\n", ask(1, x, y));
		}
	}
}

线段树2

#include <bits/stdc++.h>
#define son1 x*2
#define son2 x*2+1
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000000;
typedef unsigned long long ll;
ll n, m, ans, MOD;
struct kuai
{
	ll l, r, w, add, mul;
}s[N];
inline ll read()
{
	ll s = 0, w = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
ll build(ll x, ll L, ll R)
{
	s[x] = kuai{ L,R,0,0,1 };
	if (L == R)
		return s[x].w = read() % MOD;
	ll mid = (L + R) >> 1;
	return s[x].w = (build(son1, L, mid) + build(son2, mid + 1, R)) % MOD;
}
void down(ll x)
{
	s[son1].add = (s[x].add + s[son1].add * s[x].mul) % MOD;
	s[son2].add = (s[x].add + s[son2].add * s[x].mul) % MOD;
	s[son1].mul = (s[son1].mul * s[x].mul) % MOD;
	s[son2].mul = (s[son2].mul * s[x].mul) % MOD;
	s[son1].w = (s[son1].w * s[x].mul + s[x].add * (s[son1].r - s[son1].l + 1)) % MOD;
	s[son2].w = (s[son2].w * s[x].mul + s[x].add * (s[son2].r - s[son2].l + 1)) % MOD;
	s[x].add = 0;
	s[x].mul = 1;
}
ll ask(ll x, ll L, ll R)
{
	down(x);
	if (s[x].l >= L && s[x].r <= R)
		return s[x].w % MOD;
	ll mid = (s[x].l + s[x].r) >> 1, ans = 0;
	if (L <= mid)ans += ask(son1, L, R);
	if (R > mid)ans += ask(son2, L, R);
	return ans % MOD;
}
void updata(ll x, ll w, ll typ, ll L, ll R)
{
	down(x);
	if (typ == 1 && s[x].l >= L && s[x].r <= R)
	{
		s[x].mul = (s[x].mul * w) % MOD;
		s[x].add = (s[x].add * w) % MOD;
		s[x].w = (s[x].w * s[x].mul) % MOD;
		return;
	}
	if (typ == 2 && s[x].l >= L && s[x].r <= R)
	{
		s[x].add = (s[x].add + w) % MOD;
		s[x].w = (s[x].w + s[x].add * (s[x].r - s[x].l + 1)) % MOD;
		return;
	}
	ll mid = (s[x].l + s[x].r) >> 1;
	if (L <= mid)updata(son1, w, typ, L, R);
	if (R > mid)updata(son2, w, typ, L, R);
	s[x].w = s[son1].w + s[son2].w;
}
int main()
{
	n = read(); MOD = read();
	build(1, 1, n); m = read();
	for (ll i = 1; i <= m; i++)
	{
		ll typ = read(), x = read(), y = read();
		if (typ != 3)updata(1, read(), typ, x, y);
		else printf("%lld\n", ask(1, x, y));
	}
}

背包九讲

01背包

初始化
    恰好装满：f[x]=-INF;f[0]=0;
	没有要求装满：f[x]=0;

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--)
		f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+c[i]);
        f[j] = max(f[j], f[j - v[i]] + c[i]);//空间优化

常数优化

for (int i = 1; i <= n; i++)
{
    int bound = max(V - sum{v[i]...v[n]}, v[i]);
    for (int j = V; j >= bound, j--)
        f[j] = max(f[j], f[j - v[i]] + c[i]);
}
///////////////////////////////////////////////////////////////////
完全背包

for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= V; j++)
        f[i][j]=max(f[i−1][j],f[i][j−v[i]]+c[i])
        f[j] = max(f[j], f[j - v[i]] + c[i]);//空间优化

也可转01求解（二进拆分）

优化：
    若两件物品i、j满足j的体积大而价值比i小，则将物品j去掉
//////////////////////////////////////////////////////////////////
多重背包（单种物品有多个）

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--)
        for (int k = 0; k <= p[i] && k*v[i]; k++)
		f[j] = max(f[j], f[j - k * v[i]] + k * c[i]);

转01求解（二进拆分）

for (int i = 1; i <= n; i++)
{
	int num = min(p[i], V / v[i]);
	for (int k = 1; num > 0; k <<= 1)
	{
		if (k > num) k = num+;
		num -= k;
		for (int j = V; j >= v[i] * k; j--)
			f[j] = max(f[j], f[j - v[i] * k] + c[i] * k);
	}
//////////////////////////////////////////////////////////////////
混合背包

第一重for总写，后面的用if分类区别处理即可
//////////////////////////////////////////////////////////////////
二维费用背包(“最多K件物品”等隐式条件)

for (int i = 1; i <= n; i++)
    for (int a = V; a >= v[i]; a--)
        for (int b = M; b >= m[i]; b--)
            f[i][a][b] = max(f[i−1][a][b], f[i−1][a−v[i]][b−m[i]] + c[i]);
            f[a][b] = max(f[a][b], f[a - v[i]][b - m[i]] + c[i]);
//////////////////////////////////////////////////////////////////
分组背包（每组最多一个）

for (所有的组k)
    for (int j = V; j >= 0; j--)
        for (所有属于组k的i)
            f[j] = max{f[j], f[j - v[i]] + c[i]}
//////////////////////////////////////////////////////////////////

莫队

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1024;
int a[N], cnt[N], belong[N];
int n, m, len, kuainum, now, ans[N];
struct kuai
{
	int l, r, id;
} q[N];
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
int cmp(kuai a, kuai b)
{
	//对于左端点在同一奇数块的区间，右端点按升序排列，反之降序
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void add(int pos)
{
	if (!cnt[a[pos]]) ++now;
	++cnt[a[pos]];
}
void del(int pos)
{
	--cnt[a[pos]];
	if (!cnt[a[pos]]) --now;
}
int main()
{
	n = read();
	len = sqrt(n);
	kuainum = ceil((double)n / len);
	for (int i = 1; i <= kuainum; i++)
		for (int j = (i - 1) * len + 1; j <= i * len; j++)
			belong[j] = i;
	for (int i = 1; i <= n; ++i) a[i] = read();
	m = read();
	for (int i = 1; i <= m; ++i) {
		q[i].l = read(), q[i].r = read();
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i)
	{
		int ql = q[i].l, qr = q[i].r;
		while (l < ql) del(l++);
		while (l > ql) add(--l);
		while (r < qr) add(++r);
		while (r > qr) del(r--);
		ans[q[i].id] = now;
	}
	for (int i = 1; i <= m; ++i) printf("%d",ans[i]), putchar('\n');
	return 0;
}

杂

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#include <utility>
#include <algorithm>
priority_queue<int> q;
priority_queue<pair<int,int> > q;
reverse()
next_permutation()

字符串转数字
#include<stdlib.h>
int atoi(字符数组)或int atoi(字符串.c_str())
long atol() double atof()
long strtol(字符串.c_str(),NULL,某进制)//字符串转10进制

手动排列/组合
#include<iostream>
using namespace std;
int a[1000],v[1000],n,k;
void dfs(int cnt,int num)
{
    for(int i=1;i<=n;i++)//组合 for(int i=num+1;i<=n;i++)
        if(!v[i])
        {
            a[cnt]=i;
            v[i]=1;
            if(cnt==k)
            {
                for(int i=1;i<=k;i++)
                    cout<<a[i];
                cout<<endl;
        }
            else dfs(cnt+1,i);
            v[i]=0;
        }
}
int main()
{
    cin>>n>>k;
    dfs(1,0);
    return 0;
}

最大公约数和最小公倍数
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;
}

优化的普通质数判断
bool Is_prime(int n)
{
	if (n == 1) return false;
	if (n == 2 || n == 3) return true;
	if (n % 6 != 1 && n % 6 != 5) return false;
	for (register int i = 5; i * i <= n; i += 6)
		if (n % i == 0 || n % (i + 2) == 0) return false;
	return true;
}

cin提速
std::ios::sync_with_stdio(false);