模板代码

一、快读&快写

template <class T> inline void read(T &x) {
	x = 0;
	T f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') {
			f = -1;
		}
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
	return;
}

template<typename T, typename... Args> void read(T &first, Args &... args) {
	read(first);
	read(args...);
}

template <class T>inline void write(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x < 10) {
		putchar(x + '0');
	} else {
		write(x / 10);
		putchar(x % 10 + '0');
	}
}

template<typename T, typename... Args> void write(T &first, Args &... args) {
	write(first);
	write(args...);
}

二、单调队列

#define mod 10000
int a[1000005], n, k;
struct node {
	int dis;
	int num;
};
deque<node> ad, id;
void fi() {
	for (int i = 1; i <= n; i++) {
		while (!id.empty() && id.back().dis >= a[i]) {
			id.pop_back();
		}
		node cur = {a[i], i};
		id.push_back(cur);
		while (id.front().num + k - 1 < i) {
			id.pop_front();
		}
		if (i >= k) {
			write(id.front().dis);
			putchar(' ');
		}
	}
	return;
}
void fa() {
	for (int i = 1; i <= n; i++) {
		while (!ad.empty() && ad.back().dis <= a[i]) {
			ad.pop_back();
		}
		node cur = {a[i], i};
		ad.push_back(cur);
		while (ad.front().num + k - 1 < i) {
			ad.pop_front();
		}
		if (i >= k) {
			write(ad.front().dis);
			putchar(' ');
		}
	}
	return;
}

int main() {
	read(n, k);
	for (int i = 1; i <= n; i++) {
		read(a[i]);
	}
	fi();
	puts("");
	fa();
	return 0;
}

三、单调栈

int n,p[3000005],val[3000005];
stack<int> st;
int main() {
	read(n);
	for(int i=1;i<=n;i++){
		read(val[i]);
		while(!st.empty()&&val[i]>val[st.top()]){
			p[st.top()]=i;
			st.pop();
		}
		st.push(i);
	}
	for(int i=1;i<=n;i++){
		write(p[i]);
		putchar(' ');
	}
	return 0;
}

四、Dijkstra

const int maxn=500005;
int n, m, s, tot;
int head[maxn], dis[maxn];
bool vis[maxn];
struct edges {
	int w, nxt, to;
} edge[maxn];
struct node {
	int id, dis;
	bool operator < (const node &b) const {
		return dis > b.dis;
	}
};
void add_edge(int u, int v, int w) {
	tot++;
	edge[tot].w = w;
	edge[tot].to = v;
	edge[tot].nxt = head[u];
	head[u] = tot;
}
void dij(int s) {
	priority_queue<node> q;
	for (int i = 1; i <= n; i++) {
		dis[i] = 2147483647;
	}
	dis[s] = 0;
	q.push({s, 0});
	while (!q.empty()) {
		node cur = q.top();
		q.pop();
		int u = cur.id;
		if (!vis[u]) {
			vis[u] = 1;
			for (int i = head[u]; i != 0; i = edge[i].nxt) {
				int v = edge[i].to;
				int w = edge[i].w;
				if (dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					q.push({v, dis[v]});
				}
			}
		}
	}
}
int main() {
	read(n, m, s);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		read(u, v, w);
		add_edge(u, v, w);
	}
	dij(s);
	for (int i = 1; i <= n; i++) {
		write(dis[i]);
		putchar(' ');
	}
	return 0;
}

五、ST表

long long n, m, dp[1000010][20], lg[1000010];
int main() {
	read(n, m);
	for (int i = 1; i <= n; i++) {
		read(dp[i][0]);
	}
	for (int i = 2; i <= n; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	for (int j = 1; j <= lg[n]; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 1; i <= m; i++) {
		int l, r;
		read(l, r);
		write(max(dp[l][lg[r - l + 1]], dp[r - (1 << lg[r - l + 1]) + 1][lg[r - l + 1]]));
		puts("");
	}
	return 0;
}

六、SPFA

int n,m,s,tot;
int head[500005],dis[500005];
bool vis[500005];
struct edges{
    int nxt,to,w;
}edge[500005];
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].w=w;
    edge[tot].to=v;
    head[u]=tot;
}
void SPFA(int s){
    queue<int> q;
    for(int i=1;i<=n;i++){
        vis[i]=0;
        dis[i]=2147483647;
    }
    q.push(s);
    dis[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=0;i=edge[i].nxt){
            int v=edge[i].to;
            int w=edge[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        vis[u]=0;
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    SPFA(s);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

七、差分约束

const int maxn=50005;
int n,m,tot;
int head[maxn],dis[maxn],cnt[maxn],cnt2[maxn];
bool vis[maxn];
struct node{
	int nxt,to,w;
}edge[maxn];
void add_edge(int u,int v,int w){
	tot++;
	edge[tot].nxt=head[u];
	edge[tot].to=v;
	edge[tot].w=w;
    head[u]=tot;
}
bool SPFA(int s){
	queue<int> q;
	for(int i=1;i<=n;i++){
		cnt[i]=cnt2[i]=0;
		vis[i]=0;
		dis[i]=1e9;
	}
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=0;i=edge[i].nxt){
			int v=edge[i].to;
			int w=edge[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt2[v]=cnt2[u]+1;
				if(cnt2[v]==n+1){
					return 1;
				}
				if(!vis[v]){
					vis[v]=1;
					cnt[v]++;
					if(cnt[v]==n+1){
						return 1;
					}
					q.push(v);
				}
			}
		}
	}
	return 0;
}
int main(){
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
	    cin>>u>>v>>w;
	    add_edge(v,u,w);
	}
	for(int i=1;i<=n;i++){
		add_edge(0,i,0);
	}
	if(SPFA(0)){
		cout<<"NO";
		return 0;
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}

八、Kruskal

int n,m,ans,cnt;
int fa[5005];
struct node{
	int x,y,w;
}edge[200005];
/*并查集模板*/
bool cmp(node x,node y){
	return x.w<y.w;
}
void kru(){
	/*并查集初始化*/
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++){
		int fx=find(edge[i].x);
		int fy=find(edge[i].y);
		if(fx!=fy){
			onion(fx,fy);
			ans+=edge[i].w;
			cnt++;
			if(cnt==n-1){
				return;
			}
		}
	}
	ans=-1;
	return;
}
int main() {
	read(n,m);
	for(int i=1;i<=m;i++){
		int x,y,w;
		read(x,y,w);
		edge[i]={x,y,w};		
	}
	kru();
	if(ans==-1){
		cout<<"orz";
		return 0;
	}
	write(ans);
	return 0;
}