前言

此文主要总结所有的 noip 范围内的模板代码

part 1 基础算法

二分

左侧二分（找最小值，形如 FFFFFTTTT）

int bs(int k){
	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;
}

右侧二分（找最大值，形如 TTTTFFFFF）

int bs(int k){
	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;
}

前缀和

一维过于简单，略

二维：

初始化

void init(){
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}
}

查询

int query(int x1 , int y1 , int x2 , int y2){
	int tmp = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
	return tmp;
}

可以自己画个图想想

part2 数据结构

单调队列

单调队列优化 dp 的话以后再补吧 qwq

滑动窗口最大值 / 最小值

单调队列中一般是存最值位置下标

dp 优化：

1. 维护窗口大小
2. dp 根据单调队列中的值转移
3. 维护窗口的单调性 （求最大值维护单调递减 ， 求最小值维护单调递增）
4. 入队 dp

const int N = 1e5 + 5;

int n , a[N];
int q[N] , hh , tt = -1;

void f_max(){
	hh = 0 , tt = -1;
	
	for(int i = 1 ; i <= n ; i ++){
		// dp codes here
		
		while(hh <= tt && q[hh] < i - k + 1) hh ++;
		while(hh <= tt && a[i] >= a[q[tt]]) tt --;
		q[++ tt] = i;
		// put your operations
	}
}

void f_min(){
	hh = 0 , tt = -1;
	
	for(int i = 1 ; i <= n ; i ++){
		// dp codes here
		
		while(hh <= tt && q[hh] < i - k + 1) hh ++;
		while(hh <= tt && a[i] <= a[q[tt]]) tt --;
		q[++ tt] = i;
		// put your operations
	}
}

并查集

这里为带权并查集写法

const int N = 1e5 + 5;

int fa[N] , s[N];

void init(){
	for(int i = 1 ; i <= n ; i ++){
		fa[i] = i , s[i] = 1;
	}
}

int find1(int x){
	if(x == fa[x]) return x;
	return fa[x] = find1(fa[x]);
}

int find2(int x){              // 也可以将父节点权值更新，在一些特殊情况下需要
	if(x != fa[x]){
		int t = fa[x];
		fa[x] = find2(fa[x]);
		s[x] += s[t];
	}
	return fa[x];
}

void uni(int x , int y){
	int u = find1(x) , v = find1(y);
	if(u != v){
		s[u] += s[v] , fa[u] = v;
	}
}

ST 表

初始化

void init(){
	for(int i = 1 ; i <= n ; i ++){
		lg[i] = lg[i >> 1] + 1;
		
		f[i][0] = a[i];
	}
	
	for(int k = 1 ; k <= lg[n] ; k ++){
		for(int i = 1 ; i + (1 << k) - 1 <= n ; i ++){
			f[i][k] = Max(f[i][k - 1] , f[i + (1 << (k - 1))][k - 1]);
		}
	}
}

查询

int query(int l , int r){
	int k = lg[r - l + 1];
	return Max(f[l][k] , f[r - (1 << k) + 1][k]);
}

树状数组

$$lowbit(x) = x \& (-x)$$

查询 (query)

int query(int x){
	int s = 0;
	while(x){
		s += tr[x];
		x -= lowbit(x);
	}
	return s;
}

修改 (modify)

void modify(int x , int k){
	while(x <= n){
		tr[x] += k;
		x += lowbit(x);
	}
}

具体可见笔者所写 树状数组总结

part 3 图论

最短路

dijkstra 算法

struct edge{
	int to , w;
};

struct node{
	int id , p;
	
	bool operator <(const node &lhs)const &{
		return p > lhs.p;
	}
};

int n , m , s , dis[N] , vis[N];
vector<int> g[N];

void dijkstra(){
	priority_queue<node> q;
	memset(dis , inf , sizeof dis);
	dis[s] = 0;
	q.push({s , 0});
	
	while(!q.empty()){
		node u = q.top(); q.pop();
		if(vis[u.id]) continue;
		vis[u.id] = 1;
		
		for(auto v : g[u.id]){
			if(vis[v.to]) continue;
			if(dis[v.to] > u.p + v.w){
				dis[v.to] = u.p + v.w;
				q.push({v.to , dis[v.to]});
			}
		}
	}
}

二分图

这里用匈牙利求最大匹配

bool dfs(int u){
	for(int i = 1 ; i <= m ; i ++){
		if(g[u][i] && !vis[i]){
			vis[i] = 1;
			if(!lnk[i] || dfs(lnk[i])){
				lnk[i] = u;
				return true;
			}
		}
	}
	return false;
}

int match(){
	int cnt = 0;
	
	for(int i = 1 ; i <= n ; i ++){
		memset(vis , 0 , sizeof vis);
		if(dfs(i)) cnt ++;
	}
	return cnt;
}

连通性

判断割点

void dfs(int u , int fa){
	num[u] = low[u] = ++ dfn;
	
	for(auto v : g[u]){
		if(!num[v]){
			si[u] ++;
			dfs(v , u);
			low[u] = min(low[u] , low[v]);
			if(low[v] >= num[u] && v != fa) isc[u] = 1;
		}
		else if(num[v] < num[u] && v != fa){
			low[u] = min(low[u] , num[v]);
		}
	}
	if(u == root && si[u] >= 2) isc[u] = 1;
}

求强连通分量

void dfs(int u){
	st.push(u);
	low[u] = num[u] = ++ dfn;
	
	for(auto v : g[u]){
		if(!num[v]){
			dfs(v);
			low[u] = min(low[u] , low[v]);
		}
		else if(!scc[v]){
			low[u] = min(low[u] , num[v]);
		}
	}
	if(low[u] == num[u]){
		cnt ++;
		while(!st.empty()){
			int v = st.top(); st.pop();
			scc[v] = cnt;
			if(u == v) break;
		}
	}
}