蓝桥杯专题整理

1.二分:

描述：可以有效降低时间复杂度为NlogN, 大多情况下前提是找最大值的最小值或最小值的最大值，即在一个区间内有一部分是满足条件的，另一部分不满足，找两个部分交界的那个点。
写法：

int l =  , r = ;
while(l < r){
	int mid = (l + r)>>1;
	if(check(mid)) r = mid;
	else l = mid + 1;
}
//或者
int l = , r = ;
while(l < r){
	int mid = (l + r + 1)>>1;
	if(check(mid)) l =mid;
	else r = mid - 1;
}
//结果均为l或r,此时两者相等。最后可以再double check一下是否有解

例题：

子串简写

在数组上找两个给定的值的组合，有先后之分，两者距离有要求，那么可以固定后值，二分所有前值，vector很好用，相对于数组可以不用新增一个记录下标的变量。
注意：两个给定的值可能相等，特殊情况要考虑进来

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 5e5 + 10;
int k;
string s;
char c1, c2;
vector<int> pos;
int ans;
signed main()
{
	cin>>k;
	cin>>s>>c1>>c2;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == c1){
			pos.push_back(i);
		}
		if(s[i] == c2){
			if(pos.size() == 0 || i - pos[0] + 1 < k) continue;
			int l = 0, r = pos.size() - 1;
			while(l < r){
				int mid = (l + r + 1)>>1;
				if(i - pos[mid] + 1 >= k) l = mid;
				else r = mid - 1;
			}
			ans += l + 1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

青蛙过河

2.优先队列

描述：通过大根堆或小根堆可以以NLogN的速度找到数组中的最值，从而降低时间复杂度
写法：

//小根堆：
priority_queue<pii, vector<pii>, greater<pii>> q;
priority_queue <int,vector<int>,greater<int> > q;
//大根堆(默认)：
priority_queue<pii, vector<pii>> q;
priority_queue <int,vector<int>> q;

例题：

整数删除

找最小值删除同时给它的相邻数加上这个最小值的值。关键在于快速找最小值及其位置还有它相邻的值的位置。前者通过小根堆解决，后者通过双向队列解决。
注意：双向队列的写法，增加一个下标为-1的点，使之变成一个环，方便边界的处理。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
typedef pair<int ,int> pii; 
int n, k, a[N], st[N];
int l[N], r[N];
signed main()
{
	cin>>n>>k;
	priority_queue<pii, vector<pii>, greater<pii>> q;
	for(int i = 0; i < n; i++){
		cin>>a[i];
		q.push({a[i], i});
		st[i] = a[i];
		l[i] = i - 1;
		r[i] = i + 1;
		if(i == n-1) r[i] = -1;
	} 
	while(k){
		pii i = q.top();
		q.pop();
		if(i.first != st[i.second]){
			q.push({st[i.second], i.second});
			continue;
		}
		k--;
		int x = i.second, y = i.first;
		if(l[x] >= 0) st[l[x]] += y;
		if(r[x] >= 0) st[r[x]] += y;
		
		if(l[x] >= 0) r[l[x]] = r[x];
		if(r[x] >= 0) l[r[x]] = l[x];
		st[x] = -1;
	}
	for(int i = 0; i < n; i++){
		if(st[i] >= 0){
			cout<<st[i]<<" ";
		}
	}
	return 0;
}

3.dfs暴力

描述：对问题解决过程进行有逻辑的分析，使得可以通过dfs模拟所有的情况，来得出最终的答案，过程中可以通过剪枝来降低时间复杂度。
1.判断是否存在可行方案，一般有两种写法，一是dfs返回类型为bool，一旦有一种，就一层层返回true，每一次dfs都要进行判断；二是设置一个flag变量，dfs返回类型为void，注意也要实时判断，一旦为1就可以直接返回了。

例题：

飞机降落：

n最大为10，可以模拟所有的情况来判断结果。没有合适的贪心算法。是一道比较模板的dfs遍历

void dfs(int u, int time){ //dfs无返回值
	if(u == n){
		flag = 1;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(flag == 1) return;
		if(st[i] == 1) continue;
		if(time > pl[i].latest){
			flag = 0;
			return;
		}
		st[i] = 1;
		dfs(u + 1, max(time, pl[i].t) + pl[i].l);
		st[i] = 0;
	} 
}

bool dfs(int u, int time){ //dfs返回值为bool类型
	if(u == n){
		return true;
	}
	for(int i = 1; i <= n; i++){
		if(st[i] == 1) continue;
		if(time > pl[i].latest){
			return false;
		}
		st[i] = 1;
		if(dfs(u + 1, max(time, pl[i].t) + pl[i].l)){
			return true;
		}		
		st[i] = 0;
	} 
}

买瓜：

每个瓜都有三种状态（不选，选，切半选），选取若干个，满足重量和为m。dfs三种状态+剪枝提前退出。可以获得一半分数。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 35;
int n, m, a[N];
int ans = N;
void dfs(int u, int sum, int cnt){
	if(u == n){
		if(sum == m) ans = min(ans, cnt);
		return;
	}
	if(sum > m) return;
	if(sum + a[u] <= m) dfs(u + 1, sum + a[u], cnt);
	if(sum + a[u]/2 <= m) dfs(u + 1, sum + a[u]/2, cnt + 1);
	dfs(u + 1, sum, cnt);
}
signed main()
{
	cin>>n>>m;
	m *= 2;
	for(int i = 0; i < n; i++){
		cin>>a[i];
		a[i] *= 2;
	}
	sort(a, a + n);
	dfs(0, 0, 0);
	if(ans == N) cout<<"-1"<<endl;
	else cout<<ans<<endl;
	return 0;
}

颜色平衡树：

树上的dfs,涉及自底向上的更新，思路清晰后写起来并不难。调试时发现没有结果，原因是dfs（i）,应该是dfs（son(u)(i)），要注意到这些细节。可以过60%的数据。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 2e5;
int n, col[N], ans;
vector<int> son[N]; 
unordered_map<int, int> mp[N];
void dfs(int u){
	if(son[u].size() == 0){
		ans++;
		mp[u][col[u]]++;
		return;
	}
	mp[u][col[u]]++;
	for(int i = 0; i < son[u].size(); i++){
		dfs(son[u][i]);
	}
	for(auto i: son[u]){
		for(auto it:mp[i]){
			int x = it.first, y = it.second;
			mp[u][x] += y;
		}
	}
	int tmp = 0, flag = 1;
	for(auto i:mp[u]){
		if(!tmp) tmp = i.second;
		else if(i.second != tmp){
			flag = 0;
			break;
		}
	}
	if(flag) ans++;
	return;
}
signed main()
{
	cin>>n;
	for(int i = 1, f; i <= n; i++){
		cin>>col[i]>>f;
		son[f].push_back(i);
	}
	dfs(1);
	cout<<ans<<endl; 
	return 0;
}

景区导游：

dfs暴力树上两点的距离，dfs返回值为int，注意及时判断return。可以过30%。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int n, k, a[N];
vector<PII> e[N];
int dfs(int u, int fa, int end, int sum){
	if(u == end){
		return sum;
	}
	for(int i = 0; i < e[u].size(); i++){
		int x = e[u][i].first, y = e[u][i].second;
		if(x == fa) continue;
		int tmp = dfs(x, u, end, sum + y);
		if(tmp) return tmp;
	}
	return 0;
}
signed main()
{
	cin>>n>>k;
	for(int i = 1,u,v,t; i < n; i++){
		cin>>u>>v>>t;
		e[u].push_back({v, t});
		e[v].push_back({u, t});
	}
	for(int i = 1; i <= k; i++){
		cin>>a[i];
	}
	int sum = 0;
	for(int i = 2; i <= k; i++){
		sum += dfs(a[i-1], -1, a[i], 0);
	}
	for(int i = 1; i <= k; i++){
		if(i == 1){
			cout<<sum - dfs(a[1], -1, a[2], 0)<<" ";
		}else if(i == k){
			cout<<sum - dfs(a[k-1], -1, a[k], 0)<<" ";
		}else{
			cout<<sum-dfs(a[i-1], -1, a[i], 0)-dfs(a[i], -1, a[i+1], 0)+dfs(a[i-1], -1, a[i+1], 0)<<" ";
		}
	}
	
	return 0;
}

砍树：

模拟从树上一个点到另一个点的过程，这个线路上的边+1，最终权重为m的序号最大的边为答案，涉及边的存储，用map来实现两个点对应一条边的序号
dfs采用bool返回值，只有在线路上的边可以+1

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int n, m;
vector<int> e[N];
int w[N];
map<PII ,int> id; 
bool dfs(int u, int fa, int end){
	if(u == end){
		return true;
	}
	for(int i = 0; i < e[u].size(); i++){
		int s = e[u][i];
		if(s == fa) continue;
		if(dfs(s, u, end)){
			int ID = id[{s, u}];
			w[ID]++;
			return true;	
		}		
	}
	return false;
}
signed main()
{
	cin>>n>>m;
	for(int i = 1,u,v; i <= n-1; i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
		id[{u,v}] = i;
		id[{v,u}] = i;
	}
	for(int i = 1,a,b; i <= m; i++){
		cin>>a>>b;
		dfs(a, -1, b);
	}
	int ans = -1;
	for(int i = n-1; i >= 1; i--){
		if(w[i] == m){
			ans = i;
			break;
		}
	}
	cout<<ans<<endl;
	
	
	return 0;
}

4.dp

描述：针对子问题与整个问题关联，并求最优解的题目，大多情况下可以dfs来暴力求解

例题：

接龙序列：

解法一：数字dp

超级巧妙的把结尾的数字作为dp[i]的含义，dp[i]表示以i为结尾的最长接龙子序列的长度，从左往右遍历一遍即可。把数字当作字符串来看可以很方便地得到第一位和最后一位。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
int n;
int dp[15];
string s;
signed main()
{
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>s;
		int m = s.length();
		dp[s[m-1] - '0'] = max(dp[s[m-1] - '0'], dp[s[0] - '0'] + 1);
	}
	int ans = 1;
	for(int i = 0; i <= 9; i++){
		ans = max(ans, dp[i]);
	}
	cout<<n -ans<<endl;
	return 0;
}

解法二：dfs暴力

每个数字无非就是选和不选两种情况。ans和最后的结果cnt比较，过程可以增加一些剪枝，可以过23%。

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
int ans;
int getFirst(int x){
	while(x > 9){
		x /= 10;
	}
	return x;
}
int getLast(int x){
	return x % 10;
}
void dfs(int u, int cnt, int last){
	if(u == n + 1){
		ans = max(ans, cnt);
		return;
	}
	if(n - u + cnt < ans) return;
	if(last == -1 || last == getFirst(a[u])){
		dfs(u + 1, cnt + 1, getLast(a[u]));
	}
	dfs(u + 1, cnt, last);
}
signed main()
{
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
	}
	dfs(1, 0, -1);
	cout<<n - ans<<endl;
	return 0;
}

解法三：基于解法二的二维dp

还是选或不选两种，dp（i）(j)表示到第i个数为止，下标为j的最长接龙数列的长度。不选的话，直接把dp(i-1)(j)复制过来就可以了。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10;
int n, a[N], ans;
int dp[N][15];
int getFirst(int x){
	while(x > 9){
		x /= 10;
	}
	return x;
}
int getLast(int x){
	return x % 10;
}
signed main()
{
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i]; 
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 10; j++){
			dp[i][j] = dp[i-1][j];
		}
		int last = getLast(a[i]);
		int first = getFirst(a[i]);
		dp[i][last] = max(dp[i][last], dp[i-1][first] + 1);
	}
	for(int i = 0; i < 10; i++){
		ans = max(ans, dp[n][i]);
	}
	cout<<n - ans<<endl;
	return 0;
}

5.最短路径

网络稳定性：

采用Floyd算法进行暴力

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[5005][5005]; 
int n, m, q;
signed main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>m>>q;
	int u,v,x;
	while(m--){
		cin>>u>>v>>x;
		dp[u][v] = max(dp[u][v], x);
		dp[v][u] = max(dp[v][u], x);
	}
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n ;i++){
			for(int j = 1; j <= n; j++){
				if(i != j && i != k && j != k){
					dp[i][j] = max(dp[i][j], min(dp[i][k],dp[k][j]));
				}
			}
		}
	}
	while(q--){
		cin>>u>>v;
		cout<<dp[u][v]<<endl;
	}
	return 0;
}

#蓝桥杯

蓝桥杯专题整理

http://example.com/2024/04/04/蓝桥杯省赛备赛/蓝桥杯专题整理/

作者

jhxxxxx

发布于

2024年4月4日

许可协议

小白赛9 上一篇

蓝桥杯模拟赛练习下一篇