update：3 / 20 / 2019

—— 搜索 ——

BFS：

题目链接：点我啊╭(╯^╰)╮

题目大意：

    三维搜索最短路径

解题思路：

    BFS与DFS都行，但这里只需要求最短路径，$n$n为$30$30，所以用BFS更合适？？？！！！

代码思路：

    搜索模板，这里给出BFS和DFS两种解题代码，但DFS是过不了滴

BFS：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int L, R, C;
int dx[]= {1,-1,0,0,0,0};
int dy[]= {0,0,1,-1,0,0};
int dk[]= {0,0,0,0,1,-1};
bool vis[50][50][50];
char mp[50][50][50];
struct Node {
	int l, r, c, tot;
} st;

bool judge(int x, int y, int z) {
	return (x>=1 && y>=1 && z>=1 &&\
	        x<=L && y<=R && z<=C &&\
	        !vis[x][y][z] &&
	        mp[x][y][z]!='#');
}

int bfs(int l, int r, int c) {
	queue <Node> q;
	Node a;
	a.l=l;
	a.r=r;
	a.c=c;
	a.tot=0;
	q.push(a);
	while(!q.empty()) {
		a=q.front();
		q.pop();
		if(mp[a.l][a.r][a.c]=='E') return a.tot;
		for(int i=0; i<6; i++) {
			Node n;
			n.l=a.l+dx[i];
			n.r=a.r+dy[i];
			n.c=a.c+dk[i];
			if(judge(n.l, n.r, n.c)) {
				n.tot=a.tot+1;
				vis[n.l][n.r][n.c]=true;
				q.push(n);
			}
		}
	}
	return 0;
}

int main() {
	while(scanf("%d%d%d", &L, &R, &C), L) {
		getchar();
		memset(vis, 0, sizeof(vis));
		for(int i=1; i<=L; i++) {
			for(int j=1; j<=R; j++) {
				for(int k=1; k<=C; k++) {
					scanf("%c", &mp[i][j][k]);
					if(mp[i][j][k]=='S')
						st.l=i, st.r=j, st.c=k;
				}
				getchar();
			}
			getchar();
		}
		int ans = bfs(st.l, st.r, st.c);
		if(!ans)	printf("Trapped!\n");
		else printf("Escaped in %d minute(s).\n", ans);
	}
}

DFS：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3F3F3F3F;
int L, R, C, ans, tot;
int dx[]= {1,-1,0,0,0,0};
int dy[]= {0,0,1,-1,0,0};
int dk[]= {0,0,0,0,1,-1};
bool vis[50][50][50];
char mp[50][50][50];
struct Node {
	int l, r, c;
} st;

bool judge(int x, int y, int z){
	return (x>=1 && y>=1 && z>=1 &&\
			x<=L && y<=R && z<=C &&\
			!vis[x][y][z] && 
			mp[x][y][z]!='#');
}

void dfs(int l, int r, int c) {
	if(mp[l][r][c]=='E'){
		ans=min(ans, tot);
		return;
	} 
	if(tot>ans) return;
	for(int i=0; i<6; i++) {
		int x=l+dx[i];
		int y=r+dy[i];
		int k=c+dk[i];
		if(judge(x, y, k)) {
			vis[x][y][k]=true;
			tot++;
			dfs(x, y, k);
			tot--;
			vis[x][y][k]=false;
		}
	}
}

int main() {
	while(scanf("%d%d%d", &L, &R, &C), L) {
		getchar();
		ans=INF;
		tot=0;
		memset(vis, 0, sizeof(vis));
		for(int i=1; i<=L; i++) {
			for(int j=1; j<=R; j++) {
				for(int k=1; k<=C; k++) {
					scanf("%c", &mp[i][j][k]);
					if(mp[i][j][k]=='S')
						st.l=i, st.r=j, st.c=k;
				}
				getchar();
			}
			getchar();
		}

		dfs(st.l, st.r, st.c);
		if(ans==INF)	printf("Trapped!\n");
		else printf("Escaped in %d minute(s).\n", ans);
	}
}

题目链接：点我啊╭(╯^╰)╮

题目大意：

    从$（1,1）$（1,1）走到$（5,5）$（5,5）求最短路径并输出

核心：用一道简单题记录一下记录模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int dx[]= {1,-1,0,0};
int dy[]= {0,0,1,-1};
int cnt, mp[10][10];
bool vis[10][10];
stack <pii> r;
struct pot {
	int u, v;
	pot *pre;
};

void BFS(int u, int v) {
	queue <pot> Q;
	pot q, n, n_cnt[700];
	q.u = u, q.v = v;
	q.pre = NULL;
	Q.push(q);
	vis[u][v] = true;
	while(!Q.empty()) {
		q = Q.front();
		Q.pop();
		for(int i=0; i<=4; i++) {
			n.u=q.u+dx[i];
			n.v=q.v+dy[i];

			if(n.u<1 || n.u>5 || n.v<1 || n.v>5) continue;
			if(vis[n.u][n.v] || mp[n.u][n.v]) continue;
			//cout<<n.u<<" "<<n.v<<endl;
			vis[n.u][n.v] = true;
			n_cnt[cnt] = q;
			n.pre = &n_cnt[cnt++];	//这里一开始弄错了、没连起来....
			if(n.u==5 && n.v==5) {
				while(n.pre) {
					r.push(make_pair(n.u, n.v));
					n = *n.pre;
				}
				r.push(make_pair(1, 1));
				return;
			}
			Q.push(n);
		}
	}
}

void print() {
	while(!r.empty()) {
		printf("(%d, %d)\n", r.top().first-1, r.top().second-1);
		r.pop();
	}
}

int main() {
	for(int i=1; i<6; i++)
		for(int j=1; j<6; j++)
			scanf("%d", &mp[i][j]);
	BFS(1, 1);
	print();
}

迷宫问题——最短路径条数

    求迷宫的最短路径条数有多少条，一般方法会超时，这里记录一下模板

    简要思路：用$ans$ans记录到每个点的条数，当新到达的点的新距离小于就旧的距离时，更新新点的$ans$ans；若新距离等于旧距离，也就是可能是最短路径的时候，就$ans_{新} += ans_{旧}$ans新​+=ans旧​

    $PS：$PS：若新旧距离相等，则不需要再将该点加入到队列中，因为这个点已经在队列里了

优先队列：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f; 
const ll mod = 1000000007;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int r, c, edx, edy;
int dis[505][505], maze[505][505];
char mp[505][505];
ll ans[505][505];
bool vis[505][505];

struct Point {
    int x, y, t;
    bool operator<(const Point & b) const {
        return t>b.t; 
    }
    Point(){}
    Point(int x,int y,int t):x(x),y(y),t(t) {}
} p;

void BFS() {
    dis[1][1] = 0;
    ans[1][1] = 1;
    priority_queue <Point> pq;
    pq.push(Point(1,1,0));
    
    while(!pq.empty()) {
        int nx, ny;
        //找点 
        Point cur = pq.top(); pq.pop();
        if(vis[cur.x][cur.y] == 1) continue;
        vis[cur.x][cur.y] = 1;
        for(int k=0; k<4; k++) {
            nx = cur.x + dx[k];
            ny = cur.y + dy[k];
            if(vis[nx][ny] == 1) continue;
            if(nx<1 || nx>r || ny<1 || ny>c) continue;
            int t = dis[cur.x][cur.y] + maze[nx][ny];
            if(dis[nx][ny] > t) {
                dis[nx][ny] = t;
                ans[nx][ny] = ans[cur.x][cur.y]%mod;
                pq.push(Point(nx, ny, dis[nx][ny]));
            }
            else if(dis[nx][ny] == t) {
                ans[nx][ny] += ans[cur.x][cur.y];
                ans[nx][ny] %= mod;
                //pq.push(Point(nx, ny, dis[nx][ny]));
            }         
        }
    }
    if(dis[edx][edy] == INF) printf("-1\n");
    else printf("%lld\n", ans[edx][edy]%mod);
} 
 
void init() {
    memset(vis,0,sizeof(vis));
    memset(ans,0,sizeof ans);
    memset(maze,INF,sizeof(maze));
    memset(dis,INF,sizeof(dis));
}

int main(){
    int cas;
    scanf("%d", &cas); 
    while(cas--) {
        scanf("%d%d", &r, &c); 
        init();
        for(int i=1; i<=r; i++) 
            scanf("%s", mp[i]+1);
        for(int i=1; i<=r; i++) 
            for(int j=1; j<=c; j++) 
                if(mp[i][j] == '.') 
					maze[i][j] = 1;
        
        scanf("%d%d", &edx, &edy);
        BFS() ;
    }
}

DFS：

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$n皇后问题变种，这里只要求每一行和每一列不出现即可。

解题思路：

    这里直接从每一行开始dfs，dfs过程中对每一列的那一个确定点进行判断，若满足题意，则dfs下一列，返回时记得回溯操作，判断摆放的次数等于k时即可

代码思路：

    由于此题并未要求每一行和每一列都要有棋子即“皇后”，所以dfs结尾还需要直接dfs下一行，即当前行放了$+$+不放棋子的情况

核心：dfs，很经典

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char mp[10][10];
int n, k, ans, num;
bool vis[10];

void dfs(int x) {
	if(num==k) {
		ans++;
		return;
	}
	if(x>n) return;
	
	for(int j=1; j<=n; j++) {
		if(mp[x][j]=='#' && !vis[j]) {
			num++;
			vis[j]=true;
			dfs(x+1);
			num--;
			vis[j]=false;
		}
	}
	dfs(x+1);
}

int main() {
	while(scanf("%d%d", &n, &k)) {
		if(n==-1) break;
		ans=num=0;
		getchar();
		memset(vis, 0, sizeof(vis));
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++)
				scanf("%c", &mp[i][j]);				
			getchar();
		}
		
		dfs(1);
		printf("%d\n", ans);
	}
}

舞蹈链：

这篇博客很精细：点我点我！！

$Dancing Links（精确覆盖模板）：$DancingLinks（精确覆盖模板）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 500010
#define M 1010
struct DancingLink{
    int n,s,ansd;//列数 节点总数 
    int S[M],A[M],H[M];//S[]该列节点总数  A[]答案  H[]行首指针 
    int L[N],R[N],U[N],D[N]; //L[],R[],U[],D[] 上下左右 
    int X[N],C[N];//X[] C[] 行列编号 
    void init(int n){//初始化 
        this->n=n;
        for(int i=0;i<=n;i++)
            U[i]=i,D[i]=i,L[i]=i-1,R[i]=i+1;
        R[n]=0,L[0]=n;s=n+1;
		memset(S,0,sizeof(S));
		memset(H,-1,sizeof(H));
    }
    void DelCol(int c){//删除列 
        L[R[c]]=L[c];R[L[c]]=R[c];
        for(int i=D[c];i!=c;i=D[i])
            for(int j=R[i];j!=i;j=R[j])
                U[D[j]]=U[j],D[U[j]]=D[j],--S[C[j]];
    }
    void ResCol(int c){//恢复列 
        for(int i=U[c];i!=c;i=U[i])
            for(int j=L[i];j!=i;j=L[j])
                ++S[C[j]],U[D[j]]=j,D[U[j]]=j;
        L[R[c]]=c,R[L[c]]=c;
    }
    void AddNode(int r,int c){//添加节点 
        ++S[c],C[++s]=c,X[s]=r;
        D[s]=D[c],U[D[c]]=s,U[s]=c,D[c]=s;
        if(H[r]<0) H[r]=L[s]=R[s]=s;//行首节点
        else  R[s]=R[H[r]],L[R[H[r]]]=s,L[s]=H[r],R[H[r]]=s;
    }
    bool dfs(int d){//深度，深搜遍历 
        if(!R[0]){
            ansd=d;return true;
        }
        int c=R[0];
        for(int i=R[0];i;i=R[i]) if(S[i]<S[c]) c=i;
        DelCol(c);
        for(int i=D[c];i!=c;i=D[i]){
            A[d]=X[i];
            for(int j=R[i];j!=i;j=R[j]) DelCol(C[j]);
            if(dfs(d+1)) return true;
            for(int j=L[i];j!=i;j=L[j]) ResCol(C[j]);
        }
        ResCol(c);return false;
    }

} dlx; 

int main(){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF) {
		dlx.init(m);
		for(int i=1; i<=n; i++) {
			int num,j;
			scanf("%d",&num);	//第 i行有 num个 1
			while(num--) {
				scanf("%d",&j);
				dlx.AddNode(i,j);
			}
		}
		if(!dlx.dfs(0)) printf("NO\n");
		else {
			printf("%d",dlx.ansd);
			sort(dlx.A,dlx.A+dlx.ansd);
			for(int i=0; i<dlx.ansd; i++) 
				printf(" %d",dlx.A[i]);
			printf("\n");
		}
	}
}

$Dancing Links（重复覆盖模板）：$DancingLinks（重复覆盖模板）：

本模板取自 $HDU$HDU $3498$3498

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 100010
#define M 1010
struct DancingLink{
    int n,s,ansd;//列数 节点总数 
    int S[M],A[M],H[M];//S[]该列节点总数  A[]答案  H[]行首指针 
    int L[N],R[N],U[N],D[N]; //L[],R[],U[],D[] 上下左右 
    int X[N],C[N],vis[M];//X[] C[] 行列编号 
    void init(int n){//初始化 
        this->n=n;
        for(int i=0;i<=n;i++)
            U[i]=i,D[i]=i,L[i]=i-1,R[i]=i+1;
        R[n]=0,L[0]=n;s=n+1;
        memset(S,0,sizeof(S));
        memset(H,-1,sizeof(H));
    }
    void DelCol(int c){//删除列 
        for(int i=D[c];i!=c;i=D[i])
            L[R[i]]=L[i],R[L[i]]=R[i];
    }
    void ResCol(int c){//恢复列 
        for(int i=U[c];i!=c;i=U[i])
            L[R[i]]=R[L[i]]=i;
    }
    void AddNode(int r,int c){//添加节点 
        ++S[c],C[++s]=c,X[s]=r;
        D[s]=D[c],U[D[c]]=s,U[s]=c,D[c]=s;
        if(H[r]<0) H[r]=L[s]=R[s]=s;//行首节点
        else  R[s]=R[H[r]],L[R[H[r]]]=s,L[s]=H[r],R[H[r]]=s;
    }
    int f(){
        int ret=0;
        memset(vis,0,sizeof(vis));
        for(int i=R[0];i;i=R[i])
            if(!vis[i]){
                ret++;vis[i]=1;
                for(int j=D[i];j!=i;j=D[j])
                    for(int k=R[j];k!=j;k=R[k])
                        vis[C[k]]=1;    
            }
        return ret;
    }
    void dfs(int d){//深度，深搜遍历 
        if(d+f()>=ansd) return;
        if(!R[0]){
            if(d<ansd) ansd=d;
            return;
        }
        int c=R[0];
        for(int i=R[0];i;i=R[i]) if(S[i]<S[c]) c=i;
        for(int i=D[c];i!=c;i=D[i]){
            DelCol(i);
            A[d]=X[i];
            for(int j=R[i];j!=i;j=R[j]) DelCol(j);
            dfs(d+1);
            for(int j=L[i];j!=i;j=L[j]) ResCol(j);
            ResCol(i);
        }
    }

} dlx; 

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        dlx.init(n);
        for(int i=1; i<=m; i++) {
            int a,b;
            scanf("%d%d",&a,&b);    //第 i行有 num个 1
            dlx.AddNode(a,b);
            dlx.AddNode(b,a);
        }
        for(int i=1; i<=n; i++)
            dlx.AddNode(i,i);
        dlx.ansd = 0x3f3f3f;
        dlx.dfs(0);
        printf("%d\n", dlx.ansd);
    }
}

舞蹈链 —— M × M 数独模板

数独为M × M，则有M × M × M行 、M × M × 4列
下面是数独题任意大小模板：

#include<bits/stdc++.h>
using namespace std;

const int M=16;//数独大小
const int MN=M*M*M+10;
const int MM=M*M*4+10;
const int MNN=MN*4+MM; //最大点数,数独问题节点没有那么多

struct DLX {
	int n,m,si;//n行数m列数si目前有的节点数
	int U[MNN],D[MNN],L[MNN],R[MNN],Row[MNN],Col[MNN];
	int H[MN],S[MM]; //记录行的选择情况和列的覆盖情况
	int ansd,ans[MN];
	void init(int _n,int _m) { //初始化空表
		n=_n;m=_m;
		for(int i=0; i<=m; i++) { //初始化第一横行（表头）
			S[i]=0;U[i]=D[i]=i;L[i]=i-1;R[i]=i+1;        
		}
		R[m]=0;L[0]=m;si=m;                 
		for(int i=1; i<=n; i++) H[i]=-1;
	}
	void link(int r,int c) {  
		++S[Col[++si]=c];Row[si]=r;
		D[si]=D[c];U[D[c]]=si;U[si]=c;D[c]=si;
		if(H[r]<0) H[r]=L[si]=R[si]=si;
		else {
			R[si]=R[H[r]];L[R[H[r]]]=si;
			L[si]=H[r];R[H[r]]=si;
		}
	}
	void remove(int c) {      //列表中删掉c列
		L[R[c]]=L[c];R[L[c]]=R[c];
		for(int i=D[c]; i!=c; i=D[i])
			for(int j=R[i]; j!= i; j=R[j]) 
				U[D[j]]=U[j],D[U[j]]=D[j],--S[Col[j]];
	}
	void resume(int c) {      //恢复c列
		for(int i=U[c]; i!=c; i=U[i])
			for(int j=L[i]; j!=i; j=L[j])
				++S[Col[U[D[j]]=D[U[j]]=j]];
		L[R[c]]=R[L[c]]=c;
	}
	bool dance(int d) { 
		if(R[0]==0) { 
			ansd=d;return 1;
		}
		int c=R[0];
		for(int i=R[0]; i!=0; i=R[i])if(S[i]<S[c])c=i;
		remove(c);
		for(int i=D[c]; i!=c; i=D[i]) {
			ans[d]=Row[i];
			for(int j=R[i]; j!= i; j=R[j]) remove(Col[j]);
			if(dance(d+1)) return 1;
			for(int j=L[i]; j!=i; j=L[j]) resume(Col[j]);
		}
		resume(c); return 0;
	}
	void place(int &r,int &c1,int &c2,int &c3,int &c4,int i,int j,int k) {
		r=(i*M+j)*M+k;
		c1=M*M*0+i*M+j+1;
		c2=M*M*1+i*M+k;
		c3=M*M*3+j*M+k;
		c4=M*M*2+((i/4)*4+(j/4))*M+k;//确定第几个小九宫（16宫？），九宫4改3
	}
} dlx;

char ss[M+5][M+5];

int main() {
	int ca=0;
	while(scanf("%s",ss[0])!=EOF) {
		for(int i=1; i<M; i++)
			scanf("%s",ss[i]);
		dlx.init(M*M*M,M*M*4);
		int r,c1,c2,c3,c4;
		for(int i = 0; i < M; i++)
			for(int j = 0; j < M; j++)
				for(int k = 1; k <= M; k++)
					if(ss[i][j] == '-' || ss[i][j] == 'A'+k-1) {
						dlx.place(r,c1,c2,c3,c4,i,j,k);
						dlx.link(r,c1);
						dlx.link(r,c2);
						dlx.link(r,c3);
						dlx.link(r,c4);
					}
		dlx.dance(0);
		int v,x,y;
		for(int i=0; i<dlx.ansd; i++) {
			v=(dlx.ans[i]-1)%M;
			x=(dlx.ans[i]-1)/M/M;
			y=(dlx.ans[i]-1)/M%M;
			ss[x][y]=v+'A';
		}
		if(ca++)
			printf("\n");
		for(int i=0; i<M; i++)
			printf("%s\n",ss[i]);
	}
}

—— 动态规划 ——

LCS + 输出最长公共子序列：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[1005], b[1005];
int dp[1005][1005];

void lcs(char a[], char b[]){
	int len1 = strlen(a);
	int len2 = strlen(b);
	memset(dp, 0, sizeof(dp));
	for(int i=1; i<=len1; i++)
		for(int j=1; j<=len2; j++){
			if(a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	printf("%d\n", dp[len1][len2]);
}

void print(char a[], char b[]){
	stack <char> s;
	int len1 = strlen(a);
	int len2 = strlen(b);
	while(dp[len1][len2]){
		if(dp[len1][len2] == dp[len1-1][len2]) len1--;
		else if(dp[len1][len2] == dp[len1][len2-1]) len2--;
		else {
			len1--, len2--;
			s.push(a[len1]);
		}
	}
	while(!s.empty()){
		printf("%c", s.top());
		s.pop();
	}
	puts("");
}

int main(){
	while(~scanf("%s %s", a, b)){
		lcs(a, b);
		print(a, b);
	}
}

LCS + 输出最长公共子串：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
char a[N], b[N];
int dp[N][N], index, res;

void lcs(char a[], char b[]){
	int len1 = strlen(a);
	int len2 = strlen(b);
	index = res = 0; 
	memset(dp, 0, sizeof(dp));
	for(int i=1; i<=len1; i++)
		for(int j=1; j<=len2; j++){
			if(a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			if(res <= dp[i][j]){
				res = dp[i][j];
				index = i;
			}
		}
	printf("%d\n", res);
}

void print(char a[], char b[]){
	for(int i=index-res; i<index; i++) 
		printf("%c", a[i]);
	puts("");
}

int main(){
	while(~scanf("%s %s", a, b)){
		lcs(a, b);
		print(a, b);
	}
}

单调递增最长子序列：

设计一个$O(n2)$O(n2)时间的算法，找出由 $n$n 个数组成的序列的最长单调递增子序列。

输入样例:

5
1 3 5 2 9

输出样例:

4

思路：用$f[i]$f[i]表示前 $i$i 个最长递增子序列的长度，那么遍历一遍 $i$i，$f[i] = f[j] + 1（j&lt;i）$f[i]=f[j]+1（j<i）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[10005], f[10005]; 

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", a+i);
	for(int i=1; i<=n; i++){
		f[i] = 1;
		for(int j=0; j<i; j++)
			if(a[i]>a[j] && f[i]<f[j]+1)
				f[i] = f[j] + 1;
	}
	printf("%d", f[n]);
}

最长路：

Description

Input

Output

Sample Input

1
6 3
1 4 5 6 7 1
1 5 10
1 4 3
2 4 100
2
1 6 1000
2 5 110

Sample Output

Case #1:
1002
123

HINT

用最长路很容易超时…
PS：第一次贴的代码是错的，这是更新之后正确的：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
typedef pair <int,int> pii;
vector <pii> V1[N];
vector <pii> V2[N];
ll c[N], dp1[N], dp2[N];
int cas, t=0, n, m, q;

void solve1(int id) {
	for(int i=0; i<V1[id].size(); i++) {
		int j = V1[id][i].first;
		ll k = V1[id][i].second;
		dp1[j] = max(dp1[j], dp1[id] + k + c[j]);
	}
}

void solve2(int id) {
	for(int i=0; i<V2[id].size(); i++) {
		int j = V2[id][i].first;
		ll k = V2[id][i].second;
		dp2[j] = max(dp2[j], dp2[id] + k + c[j]);
	}
}

int main() {
	scanf("%d", &cas);
	while(cas--) {
		scanf("%d%d", &n, &m);
		memset(dp1, 0, sizeof(dp1));
		memset(dp2, 0, sizeof(dp2));
		for(int i=1; i<=n; i++){
			scanf("%lld", c+i);
			V1[i].clear(); V2[i].clear();
		}
		
		ll k;	
		int u, v;
		for(int i=1; i<n; i++)  V1[i].push_back(make_pair(i+1, 0));
        for(int i=2; i<=n; i++)  V2[i].push_back(make_pair(i-1, 0));
		while(m--) {
			scanf("%d%d%lld", &u, &v, &k);
			V1[u].push_back(make_pair(v, k));
			V2[v].push_back(make_pair(u, k));
		}
		
		dp1[1] = c[1]; dp2[n] = c[n];
		for(int i=1; i<=n; i++) 
			solve1(i), solve2(n-i+1);
		
		printf("Case #%d:\n", ++t);
		scanf("%d", &q);
		while(q--){
			scanf("%d%d%lld", &u, &v, &k);
			if(dp1[n] < dp1[u]+k+dp2[v])
				printf("%lld\n", dp1[u]+k+dp2[v]);
			else printf("%lld\n", dp1[n]);
		}
	}
}

背包dp：

吃水不忘挖井人

01背包(ZeroOnePack)：有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

完全背包(CompletePack)：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

多重背包(MultiplePack)：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。

01背包：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10005;

int n, m;
int w[maxn], v[maxn];
int dp[maxn];
bool path[maxn][maxn];

void output()	//路径输出 {
	int i=n, j=m;
	while (i>=0 && j>0){
        if(path[i][j] == 1){
            printf("%d ", i+1);
            j -= w[i];
        }
        i--;
    }
    printf("\n");
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++)
		scanf("%d%d", &w[i], &v[i]); 
	memset(dp, 0, sizeof(dp));
	memset(path, false, sizeof(path));
	
	for(int i=0; i<n; i++) {
		for(int j=m; j>=w[i]; j--)	//注意是逆序、逆序、逆序！！ 
			if (dp[j] < dp[j - w[i]] + v[i]){
                dp[j] = dp[j - w[i]] + v[i];
                path[i][j]=true;
            }
	}
	printf("%d\n", dp[m]);
	output();
}

完全背包：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10005;

int n, m;
int w[maxn], v[maxn];
int dp[maxn];
bool path[maxn][maxn];

void output(){
	int i=n, j=m;
	while (i>=0 && j>0){
        if(path[i][j] == 1){
            printf("%d ", i+1);
            j -= w[i];
        }
        else i--;
    }
    printf("\n");
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++)
		scanf("%d%d", &w[i], &v[i]); 
	memset(dp, 0, sizeof(dp));
	memset(path, false, sizeof(path));
	
	for(int i=0; i<n; i++) {
		for(int j=w[i]; j<=m; j++)	//注意是顺序、顺序、顺序！！ 
			if (dp[j] < dp[j - w[i]] + v[i]){
                dp[j] = dp[j - w[i]] + v[i];
                path[i][j]=true;
            }
	}
	printf("%d\n", dp[m]);
	output();
}

多重背包：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10005;

int n, m;
int w[maxn], v[maxn], c[maxn];
int dp[maxn];
bool path[maxn][maxn];

void output(){
	int i=n, j=m;
	while (i>=0 && j>0){
        if(path[i][j] == 1 && c[i]){
            printf("%d ", i+1);
            j -= w[i];
            c[i]--;
        }
        else
			i--;
    }
    printf("\n");
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++)
		scanf("%d%d%d", &w[i], &v[i], &c[i]); 
	memset(dp, 0, sizeof(dp));
	memset(path, false, sizeof(path));
	
	for(int i=0; i<n; i++)
		for(int k=0; k<c[i]; k++)
			for(int j=m; j>=w[i]; j--)	//也是逆序！！ 相当于重复01背包！ 
				if (dp[j] < dp[j - w[i]] + v[i]){
					dp[j] = dp[j - w[i]] + v[i];
                	path[i][j] = true;
				}
		
	printf("%d\n", dp[m]);
	output();
}

多重背包+二进制优化：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;

int n, m;
int w[maxn], v[maxn], c[maxn];
int dp[maxn];

void zero(int weight, int value){
	for(int i=m; i>=weight; i--)
		dp[i]=max(dp[i], dp[i-weight]+value);
}

void complet(int weight, int value){
	for(int i=weight; i<=m; i++)
		dp[i]=max(dp[i], dp[i-weight]+value);
}

void multi(int weight, int value, int amount){
   	if(weight*amount>=m)	//容量小的时候相当于无限背包 
   	{
	   	complet(weight, value);
	   	return;
	}
	int k=1;
	while(k<amount)	//当k个仍小于容量时，用01背包 
	{
   		zero(k*weight, k*value);
   		amount-=k;
   		k<<=1;
   	}
   	zero(amount*weight, amount*value);	//最后剩余再用01背包 
}

int main() {
	scanf("%d%d", &n, &m);
	memset(dp, 0, sizeof(dp));
	for(int i=0; i<n; i++)
		scanf("%d%d%d", &w[i], &v[i], &c[i]); 
	
	for(int i=0; i<n; i++)
		multi(w[i], v[i], c[i]);
		
	printf("%d\n", dp[m]);
}

数位dp：

浅谈数位DP
在了解数位dp之前，先来看一个问题：

  例1.求a~b中不包含49的数的个数. 0 < a、b < 2*10^9

注意到n的数据范围非常大，暴力求解是不可能的，考虑dp,如果直接记录下数字，数组会开不起，该怎么办呢？要用到数位dp.

 数位dp一般应用于：

求出在给定区间[A,B]内，符合条件P(i)的数i的个数.

条件P(i)一般与数的大小无关，而与 数的组成 有关.

这样，我们就要考虑一些特殊的记录方法来做这道题.一般来说，要保存给定数的每个位置的数.然后要记录的状态为当前操作数的位数，剩下的就是根据题目的需要来记录.可以发现，数位dp的题做法一般都差不多，只是定义状态的不同罢了.

下面开始针对例题进行分析:

我们要求[a,b]不包含49的数的个数，可以想到利用前缀和来做，具体来说，就是[a,b] = [0,b] - [0,a),(")"是不包括a),我们先求出给定a,b的每个位置的数，保存在数组s中，例如a = 109,那么a[1] = 9,a[2] = 0,a[3] = 1.然后开始dp，我们可以选择记忆化搜索或者是递推，前一种相对于第二种而言简单和较为容易理解一些，所以我们选择记忆化搜索.那么需要记录些什么呢？首先长度是一定要记录的，然后记录当前的数位是否为4，这样就便于在记忆化搜索中得到答案.

然后进行记忆化搜索，记录上一位是否为4和枚举这一位，如果没有限制的话很好办，直接枚举就可以了，但是这样可能会超空间，因此我们每次都必须要判断是否有最大的限制，这里不是很好说，看代码更容易理解：

#include <bits/stdc++.h>
using namespace std;

int a, b, shu[20], dp[20][2];

int dfs(int len, bool if4, bool shangxian)
{
    if (len == 0)
        return 1;
    if (!shangxian && dp[len][if4])   //为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意.
        return dp[len][if4];
    int cnt = 0, maxx = (shangxian ? shu[len] : 9);
    for (int i = 0; i <= maxx; i++)
    {
        if (if4 && i == 9)
            continue;
        cnt += dfs(len - 1, i == 4, shangxian && i == maxx);  //只有之前有限制现在的达到了上限才能构成限制
    }
    return shangxian ? cnt : dp[len][if4] = cnt; //如果有限制，那么就不能记忆化，否则记忆的是个错误的数.
}

int solve(int x)
{
    memset(shu, 0, sizeof(shu));
    int k = 0;
    while (x)
    {
        shu[++k] = x % 10;  //保存a,b的数
        x /= 10;
    }
    return dfs(k, false, true);
}

int main()
{
    scanf("%d%d", &a, &b);
    printf("%d\n", solve(b) - solve(a - 1));

    return 0;
}

再来看一道题：例题2.求a~b中不包含62和4的数的个数. 0 < a、b < 2*10^9

分析：和上一题一样，只需要再判断一下4是否出现和上一位是否为6即可.

#include <bits/stdc++.h>
using namespace std;

int a, b,shu[20],dp[20][2];

int dfs(int len, bool if6, bool shangxian)
{
    if (len == 0)
        return 1;
    if (!shangxian && dp[len][if6])
        return dp[len][if6];
    int cnt = 0, maxx = (shangxian ? shu[len] : 9);
    for (int i = 0; i <= maxx; i++)
    {
        if (i == 4 || if6 && i == 2)
            continue;
        cnt += dfs(len - 1, i == 6, shangxian && i == maxx);
    }
    return shangxian ? cnt : dp[len][if6] = cnt;
}

int solve(int x)
{
    memset(shu, 0, sizeof(shu));
    int k = 0;
    while (x)
    {
        shu[++k] = x % 10;
        x /= 10;
    }
    return dfs(k, false, true);
}

int main()
{
    scanf("%d%d", &a, &b);
    printf("%d\n", solve(b) - solve(a - 1));

    return 0;
}

例题4:找出1~n范围内含有13并且能被13整除的数字的个数
分析：和例1相比多了一个整除，怎么处理呢？其实只需要在记忆化搜索中增加一个参数mod即可，

利用(a * b) % mod = (a % mod) * (b % mod)和（a + b） % mod = （a % mod） + （b % mod）来计算.

比如说73 % 10 = ((7 % 10) * 10 + 3) % 10,但要注意本题是要找含有13的数，那么在处理的时候就要进行分类讨论.

#include <bits/stdc++.h>
using namespace std;

int n, shu[20], dp[20][20][10];

int dfs(int len, int mod, int zhuangtai, bool shangxian)
{
    if (len == 0)
        return mod == 0 && zhuangtai == 2;
    if (!shangxian && dp[len][mod][zhuangtai])
        return dp[len][mod][zhuangtai];
    int cnt = 0, maxx = (shangxian ? shu[len] : 9);
    for (int i = 0; i <= maxx; i++)
    {
        int tz = zhuangtai;
        if (zhuangtai != 2 && i != 1)
            tz = 0;
        if (zhuangtai == 1 && i == 3)
            tz = 2;
        if (i == 1 && zhuangtai != 2)
            tz = 1;
        cnt += dfs(len - 1, (mod * 10 + i) % 13, tz, shangxian && i == maxx);
    }
    if (!shangxian)
        dp[len][mod][zhuangtai] = cnt;
    return cnt;
}

int main()
{
    while (~scanf("%d", &n))
    {
        memset(shu, 0, sizeof(shu));
        memset(dp, 0, sizeof(dp));
        int k = 0;
        while (n)
        {
            shu[++k] = n % 10;
            n /= 10;
        }
        printf("%d\n", dfs(k, 0, 0, 1));
    }

    return 0;
}

状压dp：

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=6321

题目大意：

给出n个点和m个操作，每次操作可以可以在两个点之间连线或者删除这两个点之间的连线，问匹配数为1、2…n/2的边的数量，意思就是求出互不相交的j条边的组数，j为1~n/2。

解题思路：

用图的思想来理解点，首先最多有10个点，每个点都有被占用和未被占用两种状态，所以一共有2^10种状态。

每次增加一条边，则在0~1023种状态中找，a和b在二进制位数下都是0的状态，然后更新这个状态的a和b相应位数都变为1之后的新状态

代码思路：

1、用num[a] 表示1<<(a-1)，用cnt[i] 表示二进制下i的1的数目

2、dp[ i+num[a]+num[b] ]直接加上当前dp[ i ]的值并取模

3、同理，若是减边，则是dp[ i ]减去dp[ i-num[a]-num[b] ]的值并取模

核心：

状态转换为二进制，并不断地用原状态来更新下一个状态，记录答案，注意取模时为负数！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll dp[1025], cnt[1025];    //记录每一种情况 
ll num[15];     
ll ans[15];    //计算成功匹配边数的数目 
int n;

void add(int a, int b)
{
    for(int i=0; i<(1<<n); i++)
    {
        if((i&num[a])==0 && (i&num[b])==0)    //a和b两个点都没占用 
        {    
            if(cnt[i]%2==0)    //记录该种情况加边后的dp 并更新答案 
            {
                dp[i+num[a]+num[b]] = (dp[i+num[a]+num[b]] + dp[i])%mod;
                ans[cnt[i]/2+1] = (ans[cnt[i]/2+1]+dp[i])%mod;
            }
        }
    }
}

void sub(int a, int b)
{
    for(int i=0; i<(1<<n); i++)    //a和b两个点都占用  
    {
        if((i&num[a])>0 && (i&num[b])>0)
        {
            if(cnt[i]%2==0)    //记录该种情况减边后的dp 并更新答案 
            {
                dp[i] = (dp[i] - dp[i-num[a]-num[b]]+mod)%mod;
                ans[cnt[i]/2] = (ans[cnt[i]/2] - dp[i-num[a]-num[b]]+mod)%mod;
            }
        }
    }
}

int main()
{
    int caz;
    scanf("%d", &caz);
    for(int i=0; i<11; i++) 
        num[i]=1<<i;
    for(int i=1;i<=1023;i++)
        cnt[i]=__builtin_popcount(i);
    
    while(caz--)
    {
        int m, a, b;
        scanf("%d %d", &n, &m);
        memset(dp, 0, sizeof(dp));
        memset(ans, 0, sizeof(ans));
        dp[0]=1; //最初开始加边时从0开始加 
        char ch[10];
        for(int i=0; i<m; i++)
        {
            scanf("%s%d%d", ch, &a, &b);
            if(ch[0]=='+') add(a-1, b-1);
            else sub(a-1, b-1);
            for(int i=1; i<=n/2; i++)
            { 
                printf("%lld", ans[i]);
                if(i==n/2) printf("\n");
                else printf(" ");
             } 
        }
    }
    return 0;
}

补题链接：传送门

题目大意：

  有$T$T组样例，$n$n份问卷，每份问卷有$m$m个问题，答案由A或B组成(相当于$n$n条长度为$m$m的01序列)，在这$m$m个问题中任意选取一部分，要使这新的零散问卷互不相同，且至少有k对，问这样选取一共有多少种方案？？？

解题思路：

  因为$m&lt;=10$m<=10，所以一共只有$2^{10}$210种状态，用状态压缩即可解决，还有一点就是$k$k种互不相同的状态的存储问题（当时因为这一点想了很久），看代码即可

代码思路：

  暴力枚举每种状态即可，设A为0，只需要判断是否为B即可

核心：考虑状态的可行性和互不相同的判断方法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

char ch[1010][15];
int dp[1<<11], binary[1005];

int main()
{
	int cas=1, T;
	scanf("%d", &T);
	while(T--)
	{
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
		getchar();
		for(int i=1; i<=n; i++) scanf("%s",ch[i]);
		if(n*(n-1)/2<k) 
		{
			printf("Case #%d: 0\n", cas++);
			continue;
		}
		
		int ans=0;
		for(int i=1; i<(1<<m); i++)
		{
			int num=0;
			memset(dp, 0, sizeof(dp));
			for(int j=1; j<=n; j++)
			{
				int tot=0;
				for(int t=0; t<m; t++) 
				{
					if(i&(1<<t) && ch[j][t]=='B')	
						tot += (1<<t);
				}
				
				binary[j] = tot;
				dp[tot] = 0;
			}
			
			for(int j=1; j<=n; j++) 
			{
				int k = ++dp[ binary[j] ];
				num += (j-k);
			}
			if(num>=k) ans++;
		}
		
		printf("Case #%d: %d\n", cas++, ans);
		
	}		
	return 0;
}

单调队列：

一直弄不明白单调队列是什么，在网上也找不到易懂的介绍。

最后结合别人博客上的介绍和程序看才理解是怎么回事。

我们从最简单的问题开始：
给定一个长度为N的整数数列a(i),i=0,1,…,N-1和窗长度k.

要求：

  f(i) = max{a(i-k+1),a(i-k+2),..., a(i)},i = 0,1,...,N-1

问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。

解法一：
很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。

这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。

那么有没有更快一点的算法呢？

解法二：
我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。

单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。

1.首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2.队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首元素删除。

从上面的介绍当中，我们知道，单调队列与队列唯一的不同就在于它不仅要保存元素的值，而且要保存元素的索引（当然在实际应用中我们可以只需要保存索引，而通过索引间接找到当前索引的值）。

为了让读者更明白一点，我举个简单的例子。

假设数列为：8，7，12，5，16，9，17，2，4，6. N=10,k=3.

那么我们构造一个长度为3的单调递减队列：

首先，那8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：

0：插入8，队列为：（8，0）

1：插入7，队列为：（8，0），（7，1）

2：插入12，队列为：（12，2）

3：插入5，队列为：（12，2），（5，3）

4：插入16，队列为：（16，4）

5：插入9，队列为：（16，4），（9，5）

。。。。依此类推

那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，。。。

那我们举个栗子：烽火传递__传送门
这里就用单调队列使 O(n2) 的dp优化成了 O(n) 的单调队列。

下面给出博主学单调队列的题目来源：2018 多校 contest3__A

最后给出模板：

#include <bits/stdc++.h>
using namespace std;
#define M 2000005 

int i, n, k, a[M], Q[M], I[M]; 

void getMax()
{ 
    int head=1, tail=0; 
    for(i=1; i<=n; i++)
    { 
        while(head<=tail && Q[tail]<=a[i]) tail--; 
        tail++; 
        Q[tail]=a[i]; I[tail]=i; 
        if(i>=k)
        {
        	while(I[head] <= i-k) head++; 
        	printf("%d ", Q[head]); 
	}
    } 
} 

void getMin()
{ 
    int head=1, tail=0; 
    for(i=1; i<=n; i++)   
    { 
        while(head<=tail && Q[tail]>=a[i]) tail--; 
        tail++; 
        Q[tail]=a[i]; I[tail]=i; 
        if(i>=k)
        {
        	while(I[head] <= i-k) head++; 
        	printf("%d ", Q[head]); 
	}
    } 
} 

int main(){ 
    scanf("%d %d", &n, &k); 
    for(i=1; i<=n; i++) 
        scanf("%d", &a[i]); 
    getMin(); 
    printf("\n"); 
    getMax(); 
    return 0; 
} 

—— 图论 ——

最短路模板——Dijkstra+堆优化：

时间复杂度对比：
Dijkstra：$O(n^2)$O(n2)
Dijkstra + 优先队列（堆优化）：$O(2*E+V*logV)$O(2∗E+V∗logV)
SPFA：$O(k*E)$O(k∗E)，$k$k为每个节点进入队列的次数，一般小于等于$2$2，最坏情况为$O(V*E)$O(V∗E)
BellmanFord： $O(V*E)$O(V∗E)，可检测负圈
Floyd： $O(n^3)$O(n3)，计算每对节点之间的最短路径

结论:

$①$①当权值为非负时，用Dijkstra。
$②$②当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。
$③$③当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。
$④$④SPFA检测负环：当存在一个点入队大于等于V次时，则有负环。

$PS$PS：优先队列和SPFA都有可能被题目卡数据$......$......

Dijkstra：

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3F3F3F3F;
const int N = 1005;
int m, n, st, mp[N][N];
int dis[N], vis[N];

void init() {
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			if (i == j)	mp[i][j] = 0;
			else mp[i][j] = INF;
		}
		dis[i]=INF;
	}
}

void creatgraph() {
	int t1, t2, t3;
	for (int i=0; i<m; i++) {
		scanf("%d%d%d", &t1, &t2, &t3);//两个顶点和权值
		if (mp[t1][t2] > t3)//防止重复输入相同节点，但是权值不同
			mp[t1][t2] = t3;
		//mp[t2][t1] = t3;
	}
}

void dijkstra(int st) {
	memset(vis, 0, sizeof(vis));
	for (int i=1; i<=n; i++) dis[i] = mp[st][i];
	vis[st] = 1;
	for (int i=1; i<=n-1; i++) {	//循环n-1次
		/*找出离起点最近的点*/
		int minn = INF, k = -1;
		for (int j=1; j<=n; j++) {
			if (!vis[j] && dis[j]<minn) {
				minn = dis[j];
				k = j;
			}
		}
		if(k==-1) break;
		vis[k] = 1;
		for (int j=1; j<=n; j++) {	//松弛操作，找到媒介使得出现新的最短路
			if (!vis[j] && dis[k]+mp[k][j] < dis[j])
				dis[j] = dis[k] + mp[k][j];
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &st);	//n个顶点，m条边
	init();	//初始化地图
	creatgraph();	//建图
	dijkstra(st);
	for(int i=1; i<=n; i++) {
		if(i==1) printf("%d", dis[i]);
		else printf(" %d", dis[i]);
	}
}

Dijkstra + 堆优化（优先队列）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const ll inf = (ll)1e16;

vector <pii> V[N];
int n, m;
bool vis[N];
ll dis[N];

struct Node{
	int id;
	ll d;
	Node(){}
	Node(int id, ll d):id(id),d(d){}
	bool operator < (const Node &A)const{
		return d > A.d;
	}
};

void dijkstra(int st){
	for(int i=1; i<=n; i++){
		vis[i] = 0;
		dis[i] = inf;
	}

	dis[st] = 0;
	priority_queue<Node> Q;
	Q.push(Node(st, 0));
	Node nd;

	while(!Q.empty()){
		nd = Q.top(); Q.pop();
		if(vis[nd.id]) continue;
		vis[nd.id] = true;
		for(int i=0; i<V[nd.id].size(); i++){
			int j = V[nd.id][i].first;
			int k = V[nd.id][i].second;
			if(nd.d + k < dis[j] && !vis[j]){
				dis[j] = nd.d + k;
				Q.push(Node(j, dis[j]));
			}
		}
	}
}

int main(){
	int x, y, z, st, ed, cas = 0;
	scanf("%d", &cas);
	while(cas--){
		scanf("%d%d%d", &n, &m, &st);
		for(int i=1; i<=n; i++) V[i].clear();
		while(m--){
			scanf("%d%d%d", &x, &y, &z);
			V[x].push_back(make_pair(y, z));
			//V[y].push_back(make_pair(x, z));
		}
		dijkstra(st);
		for(int i=1; i<=n; i++)
			if(i==1) printf("%d", dis[i]);
			else printf(" %d", dis[i]);
	}
}

Dijkstra + 配对堆（高级）：

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int mn = 100005;
const int maxn = 200005 ;
const int inf = 2147483647;
typedef __gnu_pbds::priority_queue< pair<int,int> ,\
greater< pair<int,int> >,pairing_heap_tag > heap;
heap::point_iterator id[mn];//记录下每个点的迭代器 
heap q;

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

struct edge{int to, next, dis;};
edge e[maxn * 2];
int head[mn], edge_max;
int n, m, st, dis[mn];

void add(int x, int y, int z){
    e[++edge_max].to=y;
    e[edge_max].dis=z;
    e[edge_max].next=head[x];
    head[x]=edge_max;
}

void dij(int x){
    for(int i=1; i<=n; i++) dis[i] = inf;
    dis[x]=0;
    id[x] = q.push(make_pair(0, x));//每次push会返回新加入点的迭代器 
    while(!q.empty()){
        int now = q.top().second;
        q.pop();
        for(int i=head[now]; i; i=e[i].next){
            if(e[i].dis+dis[now] < dis[e[i].to]){
                dis[e[i].to] = dis[now]+e[i].dis;
                if(id[e[i].to]!=0) //如果在堆中 
                    q.modify(id[e[i].to], make_pair(dis[e[i].to], e[i].to));//修改权值 
                else id[e[i].to] = q.push(make_pair(dis[e[i].to], e[i].to));//加入堆 
            }
        }
    }
}
int main(){
    int x, y, z;
    n=read(), m=read(), st=read();
    for(int i=1; i<=m; i++){
        x=read(), y=read(), z=read();
        add(x, y, z);
    }
    dij(st);
	for(int i=1; i<=n; i++)
		if(i==1) printf("%d", dis[i]);
		else printf(" %d", dis[i]);
}

链式前向+SPFA：

链式前向星

图的存储一般有两种：邻接矩阵、前向星。

若图是稀疏图，边很少，开二维数组a[][]很浪费;

若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做.

前向星的效率不是很高，优化后为链式前向星，效率有所提升。

（一）链式前向星

1. 结构

这里用两个东西：

1 结构体数组edge存边，edge[i]表示第i条边,

2 head[i]存以i为起点的第一条边(在edge中的下标)

struct EDGE{
	int next;   //下一条边的存储下标(默认0) 
	int to;     //这条边的终点 
	int w;      //权值 
}; 
EDGE edge[500010];

2.增边：若以点i为起点的边新增了一条，在edge中的下标为j.

那么edge[j].next=head[i];然后head[i]=j.

即每次新加的边作为第一条边，最后倒序遍历

void Add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	//cnt为边的计数，从1开始计 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
} 

3. 遍历

遍历以st为起点的边

for(int i=head[st]; i!=0; i=edge[i].next)

以i开始为第一条边，每次指向下一条(以0为结束标志) （若下标从0开始，next应初始化-1）

一个简单的输出有向图熟悉链式前向星：

#include <iostream>
using namespace std;
 
#define MAXM 500010
#define MAXN 10010
 
struct EDGE{
	int next;   //下一条边的存储下标 
	int to;     //这条边的终点 
	int w;      //权值 
}; 
EDGE edge[MAXM];
 
int n, m, cnt;
int head[MAXN];  //head[i]表示以i为起点的第一条边 
 
void Add(int u, int v, int w) {  //起点u, 终点v, 权值w 
	edge[++cnt].next = head[u];
	edge[cnt].w = w;
	edge[cnt].to = v;
	head[u] = cnt;    //第一条边为当前边 
} 
 
void Print() {
	int st;
	cout << "Begin with[Please Input]: \n";
	cin >> st;
	for(int i=head[st]; i!=0; i=edge[i].next) {//i开始为第一条边，每次指向下一条(以0为结束标志)若下标从0开始，next应初始化-1 
		cout << "Start: " << st << endl;
		cout << "End: " << edge[i].to << endl;
		cout << "W: " << edge[i].w << endl << endl; 
	}
}
 
int main() {
	int s, t, w;
	cin >> n >> m;
	for(int i=1; i<=m; i++) {
		cin >> s >> t >> w;
		Add(s, t, w);
	}
	Print(); 
	return 0;
}
                                        （二）链式前向星-SPFA
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN = 200010;
const int MAXM = 500010;
const int ANS_MAX = 2147483647;
 
struct EDGE {
	int next;
	int to;
	ll w;
} edge[MAXM];
 
int n, m, st, ed, cnt, pre[MAXN];
int head[MAXN], num[MAXN];
ll dis[MAXN];
bool vis[MAXN];
queue<int> Q;
 
inline int Read() {  //读入优化 可忽略 
	char c;
	int ans = 0;
	bool Sign = false;
	while(!isdigit(c=getchar()) && c != '-');
	if(c == '-') {Sign = true;c = getchar();}
	do {ans = (ans<<3) + (ans<<1) + (c - '0');} 
	while(isdigit(c=getchar()));
	return Sign ? -ans : ans;
}
 
void Add(int u, int v, ll w) {
	edge[++cnt].next = head[u];
	edge[cnt].to = v;
	edge[cnt].w = w;
	head[u] = cnt;
}
 
void read() {
	int x, y;
	ll w;
	n = Read();
	m = Read();
	st = Read();
	for(int i=1; i<=m; i++) {
		x = Read();
		y = Read();
		w = Read();
		Add(x, y, w);
	}
}
 
bool SPFA(int x) {
	while(!Q.empty()) Q.pop();
	for(int i=1; i<=n; i++) dis[i] = ANS_MAX;
	dis[x] = 0;
	num[x] = 1;
	Q.push(x);
	vis[x] = true;
	while(!Q.empty()) {
		int k = Q.front();
		Q.pop();
		vis[k] = false;
		if(dis[k] == ANS_MAX) continue;
		for(int i=head[k]; i!=0; i=edge[i].next) {
			int j = edge[i].to;
			if(dis[j] > dis[k] + edge[i].w) {
				dis[j] = dis[k] + edge[i].w;
				num[j] = num[k]+1;
				pre[j] = k;
				//if(num[j]>n) return 1;	//判断负环 
				if(!vis[j]) {
					Q.push(j);
					vis[j] = true;
				}
			}
		}
	}
	return 0;
}
 
void print_path(int end) { //打印最短路的路径
	stack <int> path;
	int now = end;
	while(1) { //前驱
		path.push(now);
		if(now == st) break;
		now = pre[now];
	}
	while(!path.empty()) {
		now = path.top();
		path.pop();
		if(path.empty()) printf("%d\n", now);
		else printf("%d-->", now);
	}
}
 
int main() {
	int cas;
	cas = Read();
	while(cas--){
		memset(vis, 0, sizeof(vis));
		memset(num, 0, sizeof(num));
		memset(head, 0, sizeof(head));
		memset(pre, -1, sizeof(pre));
		cnt = 0;
		read();
		SPFA(st);
		//SPFA(1) ? printf("YES\n") : printf("NO\n");
		for(int i=1; i<=n; i++) printf("%lld ", dis[i]);
		printf("\n");
		//for(int i=1; i<=n; i++) print_path(i);
	}
}

Floyd：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = INT_MAX/100;
int n, m, d[3000][3000];
void floyed() {
	for(int k=0; k<n; k++) {                                //插入k点
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(d[i][k]<INF && d[k][j]<INF)                //消除加法溢出问题
					d[i][j]=min(d[i][j], d[i][k]+d[k][j]);   //更新两点距离
			}
		}
	}
}
void init() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++)
			if(i==j) d[i][j]=0;
			else d[i][j]=INF;
	}
	for(int i=0; i<m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		d[x-1][y-1]=z;
	}
}
int main() {
	init();
	floyed();
}

—— 数学 ——

快速乘：

$O（logn）:$O（logn）:

ll mult(ll a, ll b, ll p) {
    a %= p;
	b %= p;
    ll ans = 0;
    while(b) {
        if( b&1 ) ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ans;
}

$O（1）:$O（1）:

出自：

ll fast_mult(ll a, ll b) {
    return (a*b - (ll)((long double)a/mod*b)*mod+mod)%mod;
}

$PS：$PS：
     ①、double可能会挂，最好long double
     ②、$u,v&gt;=p$u,v>=p可能会挂，必要时先%$p$p
     ③、用浮点数算出$u*v/p$u∗v/p的值时事实上允许了$±1$±1的误差，因此可能出现负数，所以必须$+p$+p再%$p$p。因此理论上不需要+$eps$eps

另一种模板：

ll pmod(ll a, ll b) {
	ll d=(ll)floor(a*(long double)b/mod+0.5);
	ll ret=a*b-d*mod;
	if (ret<0) ret+=mod;
	return ret;
}

也称$O(1)$O(1)快速乘

但还有一种黑科技，根据牛客的一道题：电音之王

用$O(1)$O(1)快速乘可以勉强卡过这道题
但根据出题人DLS的一句话题解，正确做法为：Montgomery modular multiplication

暂时没人写详细的博客
这里附上DLS用Montgomery modular multiplication的解题代码：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
 
typedef unsigned long long u64;
typedef __int128_t i128;
typedef __uint128_t u128;
int _,k;
u64 A0,A1,M0,M1,C,M;
 
struct Mod64 {
	Mod64():n_(0) {}
	Mod64(u64 n):n_(init(n)) {}
	static u64 init(u64 w) { return reduce(u128(w) * r2); }
	static void set_mod(u64 m) {
		mod=m; assert(mod&1);
		inv=m; rep(i,0,5) inv*=2-inv*m;
		r2=-u128(m)%m;
	}
	static u64 reduce(u128 x) {
		u64 y=u64(x>>64)-u64((u128(u64(x)*inv)*mod)>>64);
		return ll(y)<0?y+mod:y;
	}
	Mod64& operator += (Mod64 rhs) { n_+=rhs.n_-mod; if (ll(n_)<0) n_+=mod; return *this; }
	Mod64 operator + (Mod64 rhs) const { return Mod64(*this)+=rhs; }
	Mod64& operator -= (Mod64 rhs) { n_-=rhs.n_; if (ll(n_)<0) n_+=mod; return *this; }
	Mod64 operator - (Mod64 rhs) const { return Mod64(*this)-=rhs; }
	Mod64& operator *= (Mod64 rhs) { n_=reduce(u128(n_)*rhs.n_); return *this; }
	Mod64 operator * (Mod64 rhs) const { return Mod64(*this)*=rhs; }
	u64 get() const { return reduce(n_); }
	static u64 mod,inv,r2;
	u64 n_;
};
u64 Mod64::mod,Mod64::inv,Mod64::r2;
 
u64 pmod(u64 a,u64 b,u64 p) {
	u64 d=(u64)floor(a*(long double)b/p+0.5);
	ll ret=a*b-d*p;
	if (ret<0) ret+=p;
	return ret;
}
 
 
void bruteforce() {
	u64 ans=1;
	for (int i=0;i<=k;i++) {
		ans=pmod(ans,A0,M);
		u64 A2=pmod(M0,A1,M)+pmod(M1,A0,M)+C;
		while (A2>=M) A2-=M;
		A0=A1; A1=A2;
	}
	printf("%llu\n",ans);
}
 
int main() {
	for (scanf("%d",&_);_;_--) {
		scanf("%llu%llu%llu%llu%llu%llu%d",&A0,&A1,&M0,&M1,&C,&M,&k);
		Mod64::set_mod(M);
		Mod64 a0(A0),a1(A1),m0(M0),m1(M1),c(C),ans(1),a2(0);
		for (int i=0;i<=k;i++) {
			ans=ans*a0;
			a2=m0*a1+m1*a0+c;
			a0=a1; a1=a2;
		}
		printf("%llu\n",ans.get());
	}
}

（比$O(1)$O(1)快速乘快了$1$1秒多）

组合数：

一、 一般组合数计算

若对$ans$ans取模，则无法保证下一步是否能被整除，所以只能对最后的结果取模

时间复杂度：$O(m)$O(m)
$mod$mod的要求：无
有效范围：$1&lt;=n,m&lt;=60$1<=n,m<=60

//一般方法求C（n，m）最后取模。C(62,28)溢出。有效范围1<n,m<=60
ll CNormal(int n, int m){
	if ( m>n ) return 0;
	ll ans = 1;
	for (int i=1; i<=m; i++)
	{
		ans *= (n - m + i);
		ans /= i;
	}
	return ans % mod;
}

二、 杨辉三角

可以在过程中取模，但时间复杂度较高

公式：$C(n,m)=C(n-1,m)+C(n-1,m-1)$C(n,m)=C(n−1,m)+C(n−1,m−1)
时间复杂度：$O(nm)$O(nm)
$mod$mod的要求：无
有效范围：$1&lt;=n,m&lt;=1000$1<=n,m<=1000

//杨辉三角求C（n，m）
ll matrix[110][110];
ll CMatrix(int n, int m){
	if ( m>n ) return 0;
	ll ans = 0;
	matrix[1][0] = matrix[1][1] = 1;
	for (int i=2; i<=n; i++)
	{
		int k = min(i, m);
		for(int j=0; j<=k; j++)
		{
			if ( j==0 || j==i )	matrix[i][j] = 1;
			else matrix[i][j] = (matrix[i-1][j] + matrix[i-1][j-1]) % mod;
		}
	}
	return matrix[n][m];
}

三、 逆元

公式：$C(n,m)=\cfrac{m!}{n!×(m-n)!}$C(n,m)=n!×(m−n)!m!​
时间复杂度：$O(logp+m)$O(logp+m)
$mod$mod要求：$p$p为质数，且$m&lt;p$m<p或$GCD(p, m)=1$GCD(p,m)=1
有效范围：$1&lt;=n,m&lt;=10^6$1<=n,m<=106

ll fac[1<<20];
ll qpow(ll a, ll b, ll c) {	//快速幂 
	ll ans = 1;
	a = a % c;
	while (b) {
		if ( b&1 )
			ans = (ans * a) % c;
		b >>= 1;
		a = (a * a) % c;
	}
	return ans;
}
void init() { //先打出阶乘，节省时间
	fac[1] = 1;
	for (int i=2; i<=(1<<20); i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
}
ll C(ll n, ll m) {	//逆元求组合数 
	return fac[n] * qpow(fac[m] * fac[n - m] % mod, mod - 2, mod) % mod;
}

四、 分解因子

时间复杂度：$O(n)$O(n)
$mod$mod的要求：无（可为合数）
有效范围：$1&lt;=n,m,p&lt;=10^6$1<=n,m,p<=106

// 求素数表
int prime[1000000] = {0};
bool isPrime[1000000];
void getPrime(int maxn){
	int n = 0;
	memset(isPrime, true, sizeof(isPrime));
	for (int i=2; i<=maxn; i++)
	{
		if ( isPrime[i] )
		{
			prime[n++] = i;
			for (int j=i*2; j<=maxn; j+=i) isPrime[j] = false;
		}
	}
}
ll qpow(ll a, ll b, ll c) {	//快速幂 
	ll ans = 1;
	a = a % c;
	while (b) {
		if ( b&1 )
			ans = (ans * a) % c;
		b >>= 1;
		a = (a * a) % c;
	}
	return ans;
}
//获得n！中因子p的个数
ll getPNum(ll n, ll p){
	ll ans = 0;
	while ( n )
	{
		ans += n / p;
		n /= p;
	}
	return ans;
}
 
//利用因子求C(n,m)
ll CFactor(ll n, ll m){
	if ( m>n ) return 0;
	ll ans = 1;
	for (int i=0; prime[i]!=0 && prime[i]<=n; i++)
	{
		ll a = getPNum(n, prime[i]);
		ll b = getPNum(m, prime[i]);
		ll c = getPNum(n - m, prime[i]);
		a -= (b + c);
		ans *= qpow(prime[i], a, mod);
		ans %= mod;
	}
	return ans;
}

五、 Lucas定理*

$mod$mod的要求：质数
有效范围：$1&lt;=n,m,p&lt;=10^9$1<=n,m,p<=109

①$p$p较大、不进行预处理

ll qpow(ll a, ll b, ll c){
    ll ans = 1;
    a %= c;
    while(b)
    {
        if(b & 1)
			ans = (ans % c) * (a % c) % c;
        b >>= 1;
        a = (a % c) * (a % c) % c;
    }
    ans %= c;
    return ans;
}
//x关于p的逆元，p为素数
ll inv(ll x, ll p){
    return qpow(x, p - 2, p);
}
//组合数C(n, m) % p
ll C(ll n, ll m, ll p){
    if(m > n)	return 0;
    ll up = 1, down = 1;//分子分母;
    for(int i = n-m+1; i <= n; i++)	up = up * i % p;
    for(int i = 1; i <= m; i++)	down = down * i % p;
    return up * inv(down, p) % p;
}
ll Lucas(ll n, ll m){
    if(m == 0)	return 1;
    return C(n % mod, m % mod, mod) * Lucas(n / mod, m / mod) % mod;
}

②$p$p较小、$p&lt;10^6$p<106、半预处理

ll fac[1<<20];
ll qpow(ll a, ll b, ll c) {	//快速幂 
	ll ans = 1;
	a = a % c;
	while (b) {
		if ( b&1 )
			ans = (ans * a) % c;
		b >>= 1;
		a = (a * a) % c;
	}
	return ans;
}
void init() { //先打出阶乘，节省时间
	fac[1] = 1;
	for (int i=2; i<=(1<<20); i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
}
ll C(ll n, ll m) {	//逆元求组合数 
	return fac[n] * qpow(fac[m] * fac[n - m] % mod, mod - 2, mod) % mod;
}
ll Lucas(ll n, ll m){
    if(m == 0)	return 1;
    return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}

六、 拓展Lucas定理*

$mod$mod的要求：无
有效范围：$1&lt;=n,m,p&lt;=10^9$1<=n,m,p<=109
即$n,m$n,m都很大且$p$p不为质数的时候，用此定理

暂时不作介绍，以后再来填坑
参考：http://www.cnblogs.com/fzl194/p/9095177.html
https://blog.****.net/u013269631/article/details/43485189

矩阵快速幂：

快速幂：

ll qpow(ll a, ll b, ll c) {	//快速幂 
	ll ans = 1;
	a = a % c;
	while (b) {
		if ( b&1 )
			ans = (ans * a) % c;
		b >>= 1;
		a = (a * a) % c;
	}
	return ans;
}

矩阵快速幂：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10;
const ll mod = 1e9+7;
int n;

struct Matrix	//矩阵结构体 
{
    ll a[maxn][maxn];
    void init(){    //初始化为单位矩阵 
        memset(a, 0, sizeof(a));
        for(int i=0; i<n; ++i){
            a[i][i] = 1;
        }
    }
};

Matrix mul(Matrix a, Matrix b)	//矩阵乘法 
{
    Matrix ans;
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            ans.a[i][j] = 0;
            for(int k=0; k<n; ++k){
                ans.a[i][j] += a.a[i][k] * b.a[k][j];
                ans.a[i][j] %= mod; 
            }
        }
    } 
    return ans;
}

Matrix qpow(Matrix a, int k)	//矩阵快速幂 
{
    Matrix ans = a;
    ans.init();
    while(k){
        if(k&1) ans = mul(ans, a);
        a = mul(a, a);
        k>>=1;
    } 
    return ans;
}

void output(Matrix a)	//输出矩阵 
{
	for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            printf("%lld ", a.a[i][j]);
        }
        printf("\n");
    }
}

int main()
{
	ll k;
	Matrix a;
	scanf("%d %lld", &n, &k);
	
	for(int i=0; i<n; i++)	//输入矩阵 
        for(int j=0; j<n; j++)
            scanf("%lld", &a.a[i][j]);
	a = qpow(a, k);
	output(a);	//输出矩阵 
	
	return 0;
}

黑科技函数：

next_permutation() 全排列函数

    排列（Arrangement），简单讲是从 $N$N 个不同元素中取出 $M$M 个，按照一定顺序排成一列，通常用$A(M,N)$A(M,N)表示。当$M=N$M=N时，称为全排列（Permutation）。
    从数学角度讲，全排列的个数$A(N,N)=(N)*(N-1)*...*2*1=N!$A(N,N)=(N)∗(N−1)∗...∗2∗1=N!，但从编程角度，如何获取所有排列？那么就必须按照某种顺序逐个获得下一个排列，通常按照升序顺序（字典序）获得下一个排列。

    例如对于一个集合$A=$A={$1,2,3$1,2,3}，首先获取全排列$a1: 1,2,3$a1:1,2,3；然后获取下一个排列$a2: 1,3,2$a2:1,3,2；按此顺序，$A$A 的全排列如下：

$a1: 1,2,3$a1:1,2,3 ;　　$a2: 1,3,2;$a2:1,3,2; 　　$a3: 2,1,3$a3:2,1,3 ;　　$a4: 2,3,1$a4:2,3,1 ;　　$a5: 3,1,2$a5:3,1,2 ;　　$a6: 3,2,1$a6:3,2,1 ;　　共 $6$6 种。

    那么我们有时就需要求下一种全排列，在STL中的algorithm已经给出了一种健壮、高效的方法，即 next_permutation(int *begin, int *end)
    注意，这个函数是直接将传递的数组转换成了下一个全排列数组，并且有一个返回值。
    当返回为 $1$1 时，表示找到了下一全排列；返回 $0$0 时，表示无下一全排列。注意，如果从begin到end为降序，则表明全排列结束，逆置使其还原到升序

    因而我们可以用这个返回值求得所有的全排列

同时，相对应的，上一个排列即为prev_permutation(int *begin, int *end)

#include<bits/stdc++.h>
using namespace std;

int main() {
	char a[3]= {'a','b','c'}; //第一个排列保证正序，有时候根据题目要求，需要对其进行排序处理。
	for(int i=1; i<=6; i++) { //i为总共排列的个数  ，及 3！
		for(int j=0; j<3; j++)
			printf("%c ", a[j]);
		printf("\n");
		next_permutation(a, a+3);//放在第一个排列的后边，输出第一个排列的下一个排列
	}
	printf("*******************\n");
	
	int b[4]= {0,1,2,3};
	do{
        for(int i=0; i<4; printf("%d ", b[i++]));
        printf("\n");
    } while(next_permutation(b, b+4));
    printf("*******************\n");
    
    int c[3]={3,2,1};
	next_permutation(c, c+3);
	for(int i=0; i<3; printf("%d ", c[i++]));
}

atoi() 与 itoa()函数用法

atoi() 函数的原型为： int atoi(const char *str );

函数功能：把字符串转换成整型数
参数str：要进行转换的字符串
返回值：每个函数返回 int 值，此值由将输入字符作为数字解析而生成。 如果该输入无法转换为该类型的值，则atoi的返回值为 0

函数说明: 参数str字符串，如果第一个非空格字符不存在或者不是数字也不是正负号则返回零，否则开始做类型转换，之后检测到非数字(包括结束符 \0) 字符时停止转换，返回整型数

itoa() 函数的原型为： char *itoa( int value, char *string,int radix);

value：要转换的数据
string：目标字符串的地址
radix：转换后的进制数，可以是10进制、16进制等，范围必须在 2~36

itoa并不是一个标准的C函数，它是Windows特有的，如果要写跨平台的程序，请用sprintf。
是Windows平台下扩展的，标准库中有sprintf，功能比这个更强，用法跟printf类似：

char str[255];
sprintf(str, “%x”, 100); //将100转为16进制表示的字符串。

下面是一个十进制转八进制的方法：

#include "stdio.h"
#include "stdlib.h"
 
int main(void){
	int num = 10;
	char str[100];
	itoa(num, str, 8);      //将整数10转换为八进制保存在str字符数组中
	printf("%s\n", str);
	system("pause");
	return 0;
}

下面是一个十进制转二进制的方法：

#include "stdio.h"
#include "stdlib.h"
 
int main(void){
	int num = 15;
	char str[100];
	int n = atoi(itoa(num, str, 2));   //先把num转换为二进制的字符串，再把该字符串转换为整数
	printf("%d\n",n);
	system("pause");
	return 0;
}

char *_itoa( int value, char *string, int radix );

char *_i64toa( __int64 value, char *string, int radix );

char * _ui64toa( unsigned _int64 value, char *string, int radix );

wchar_t * _itow( int value, wchar_t *string, int radix );

wchar_t * _i64tow( __int64 value, wchar_t *string, int radix );

wchar_t * _ui64tow( unsigned __int64 value, wchar_t *string, int radix );

程序代码如下：

#include "stdio.h"
#include "stdlib.h"
 
int main(void){
	char buffer[20];
	int i = 3445;
	long l = -344115L;
	unsigned long ul = 1234567890UL;
 
	_itoa( i, buffer, 10 );
	printf( "String of integer %d (radix 10): %s\n", i, buffer );
	_itoa( i, buffer, 16 );
	printf( "String of integer %d (radix 16): 0x%s\n", i, buffer );
	_itoa( i, buffer, 2 );
	printf( "String of integer %d (radix 2): %s\n", i, buffer );
 
	_ltoa( l, buffer, 16 );
	printf( "String of long int %ld (radix 16): 0x%s\n", l,buffer );
 
	_ultoa( ul, buffer, 16 );
	printf( "String of unsigned long %lu (radix 16): 0x%s\n", ul,buffer );
 
	system("pause");
	return 0;
}

取整函数 ceil、floor、round

$floor()$floor()：地面，地板，所以函数向下取整，即最接近$x$x的较小整数

$ceil()$ceil()：天花板，所以函数向上取整，即最接近$x$x的较大整数

$round()$round()：大约，环绕，所以函数四舍五入

double round(double r)
{
    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
}