当前位置： 首页 > article >正文

第十四届蓝桥杯C++省赛B组 补题(3 - 10)

article 2024/11/14 12:30:11

文章目录

  • C ： 冶炼金属
  • D：飞机降落(全排列枚举)
  • E：接龙数列(简单dp)
  • F ：岛屿个数(bfs)
  • G ： 字串简写
  • H：整数删除(链表模拟)
  • I：景区导游（LCA）
  • J ： 砍树 (树上边差分)

民间数据入口

C ： 冶炼金属

模拟一下即可

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;

int n , a , b , mx = 2e9 , mn = 0;

int main(){

	cin >> n;
	
	for(int i=1;i<=n;i++){
		cin >> a >> b;
		mx = min(a / b , mx);
		mn = max(a / (b + 1) + 1 , mn);
	}
	
	cout << mn << " " << mx;


	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

D：飞机降落(全排列枚举)

可以注意到 N 最大为 10 ， 完全可以用全排列去做 ， 最坏复杂度是 O ( N ! ∗ N ∗ T ) O(N!*N*T) O(N!∗N∗T) ， 约为 4e8 ， 2s 完全可以接受；

要注意 现在时间 和 降落范围时间 的比较 ， 如果 现在时间 不足 起飞的最早时间 ， 不能用现在时间直接加上降落时间 ， 而应该 贪心的更新 现在时间
也就是下面的这个代码段

if(now < a[id].x) now = a[id].x + a[id].z;
else now += a[id].z;

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;

int n , m , t , res;
int b[N];
struct node{
	int x , y , z;
}a[N];

bool judge(){
	int now = 0;
	for(int i=1;i<=n;i++){
		int id = b[i]; 
		if(a[id].x + a[id].y < now) return 0;
		if(now < a[id].x) now = a[id].x + a[id].z;
		else now += a[id].z;
	}
	return 1;
	
}

int main(){

	cin >> t;
	
	while(t--){
		res = 1;
		cin >> n;
		for(int i=1;i<=n;i++){
			cin >> a[i].x >> a[i].y >> a[i].z;
			res *= i;
			b[i] = i;
		}
		bool f = 0;
		for(int i=1;i<=res;i++){
			if(judge()){ f = 1;break;}
			next_permutation(b + 1 , b + 1 + n);
		}
		if(f) cout << "YES\n";
		else cout << "NO\n";
	}


	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

E：接龙数列(简单dp)

思路 ： 维护一个以数 x 结尾的序列最长长度 ， 做 dp 即可

dp[i][0] 表示 第 i 位不选的 最长长度
不选的时候直接从前一位转移
dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);
dp[i][1] 表示 第 i 位选上的最长长度
当这一位选上的时候 ， 就要接在前面最优的上面 ， 维护一下就好
dp[i][1] = c[a[i] / 10] + 1;
c[a[i] % 10] = max(c[a[i] % 10] , dp[i][1]);
c[x] 代表以 x 结尾的最长数列的长度

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;

int n , c[20] , a[N];
string s;
int dp[N][2] , ans;

int main(){

	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> s;
		int len = s.size() - 1;
		a[i] = (s[0] - '0') * 10 + s[len] - '0'; 
	}
	
	for(int i=1;i<=n;i++){
		dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);
		dp[i][1] = c[a[i] / 10] + 1;
		c[a[i] % 10] = max(c[a[i] % 10] , dp[i][1]);
	}
	
	cout << n - max(dp[n][0] , dp[n][1]);

	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

F ：岛屿个数(bfs)

这个题思路很棒 ， 我们把一个环内部的无论是水还是子岛屿都看成这个环形岛屿内部的陆地 ， 每个要计数的陆地都有一个特点 ， 那就是他一定会被水包围 ， 那我们从海水出发 ， 给所有可到达的海水打上标记 ， 那么被包围的一个环无论有多少子环和海水 ， 都算作一部分 ， 我们计算被包围的部分的个数即可。
注意实际操作的时候要给图的周围加上一圈海水 ， 方便操作且符合题意

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 60;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;

int t , n , m , a[N][N] , ans;
bool vis[N][N];//海水标记
int dir[8][2] = {0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
int dirs[4][2] = {0,1,0,-1,1,0,-1,0};

bool ok(int x,int y){
	return x >= 1 && y >= 1 && x <= n + 2 && y <= m + 2 && !a[x][y] && !vis[x][y];
}

bool oks(int xx,int yy){
	return xx >= 1 && yy >= 1 && xx <= n + 2 && yy <= m + 2 && !vis[xx][yy];
}


void bfs1(int x,int y){
	
	queue<PII>q;
	q.push({x,y});
	vis[x][y] = 1;
	while(!q.empty()){
		PII t = q.front();
		q.pop();
		for(int i=0;i<8;i++){
			int xx = t.fi + dir[i][0];
			int yy = t.se + dir[i][1];
			if(ok(xx,yy)){
				vis[xx][yy] = 1;
				q.push({xx,yy});
			}
		}
	}
}

int bfs2(int x,int y){
	queue<PII>q;
	q.push({x,y});
	vis[x][y] = 1;
	while(!q.empty()){
		PII t = q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int xx = t.fi + dir[i][0];
			int yy = t.se + dir[i][1];
			if(oks(xx,yy)){
				vis[xx][yy] = 1;
				q.push({xx,yy});
			}
		}
	}
	return 1;
}

int main(){

	cin >> t;
	
	while(t--){
		
		ans = 0;
		
		memset(vis , 0 , sizeof(vis));
		memset(a   , 0 , sizeof(a));
		cin >> n >> m;
		for(int i=2;i<=n+1;i++){
			for(int j=2;j<=m+1;j++){
				scanf("%1d",&a[i][j]);
			}
		}
		
		bfs1(1,1);
		
		for(int i=1;i<=n+2;i++){
			for(int j=1;j<=m+2;j++){
				if(!vis[i][j]) ans += bfs2(i,j);
			}
		}
		
		cout << ans << "\n";
		
		
	}
	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

G ： 字串简写

这个题思路很好想 ， 线性处理 ， 每个 c2 字符计算前面符合条件的 c1 字符的贡献即可
前面符合条件的个数 = 前面总数 - k 范围内的数量
这些都是能线性去求的

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 5e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;

int n , len , l;
string s;
char a , b;
int cnt[N] , c;

int main(){

	cin >> n >> s >> a >> b;
	len = s.size();
	for(int i=0;i<n-1;i++){
		if(s[i] == b) cnt[i] = c;
		if(s[i] == a) c++;  
	}
	l = -1 ;
	for(int i=n-1;i<len;i++){
		if(s[++l] == a) c--;
		if(s[i] == b) cnt[i] = c;
		if(s[i] == a) c++;
	}
	
//	for(int i=0;i<len;i++) cout << cnt[i] << " ";

	ll ans = 0;
	c = 0;
	for(int i=0;i<len;i++){
		if(s[i] == b) ans += 1ll * (c - cnt[i]);
		if(s[i] == a) c++; 
	}
	
	cout << ans ;
	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

H：整数删除(链表模拟)

对于每一个待操作节点 ， 要维护他左边要操作的节点 ， 维护其右边待操作的节点 ， 和当前值；
处理顺序使用小根堆去维护 ， 因为堆中某一个点的信息可能多次出现 ， 我们还要记录一下每个位置的当前值 ， 只处理有效的节点

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N = 5e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;
/*
5 3
1 4 2 8 7
l , r , now ;
*/

struct node{
	int l , r , now , f;
}a[N];

bool cmp(PII a,PII b){
	return a.se < b.se ; 
}

int n , m , now[N];
priority_queue<PII , vector<PII> , greater<PII> > q;

signed main(){
	
	IOS
	
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i].now;
		now[i] = a[i].now;
		if(i != 1) a[i].l = i - 1;
		else a[i].l = -1;
		if(i != n) a[i].r = i + 1;
		else a[i].r = -1;
		q.push({a[i].now , i});
	}
	
	for(int i=1;i<=m;i++){
		int id = q.top().se ;
		int s = q.top().fi ;
		q.pop();
		while(now[id] != s){
			id = q.top().se;
			s = q.top().fi;
			q.pop();
		}//这个地方是一定不会取完的 ， 所以不用判空
		int l = a[id].l , r = a[id].r;
		if(l != -1){//维护左端点
			a[l].now += a[id].now;
			now[l] = a[l].now;
			a[l].r = r;
			q.push({a[l].now , l});
		}
		if(r != -1){//维护右端点
			a[r].now += a[id].now;
			now[r] = a[r].now;
			a[r].l = l;
			q.push({a[r].now , r});
		}
		a[id].f = 1;
	}
	
	for(int i=1;i<=n;i++) if(!a[i].f) cout << a[i].now << " ";
	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

I：景区导游（LCA）

LCA 板子

#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int N = 1e5+10;
typedef pair<int,int>PII;
#define int long long

int n , m;
vector<PII>ve[N];
int f[N][30] , d[N] , disx[N][30];
int dp[N][2] , s[N];

void dfs(int x,int fa,int dis){
	
	f[x][0] = fa;disx[x][0] = dis;
	for(int i=1;(1<<i)<=d[x];i++) f[x][i] = f[f[x][i-1]][i-1] , disx[x][i] = disx[x][i-1] + disx[f[x][i-1]][i-1];
	
	for(auto [y,l] : ve[x]){
		if(y == fa) continue;
		d[y] = d[x] + 1;dfs(y , x , l);
	}
}

int lca(int x,int y){
	int ans = 0;
	if(d[x] < d[y]) swap(x , y);
	for(int i=20;i>=0;i--) if(d[x] - (1 << i) >= d[y]) ans += disx[x][i] , x = f[x][i] ;
	if(x == y) return ans;
	for(int i=20;i>=0;i--){
		if(f[x][i] != f[y][i]){
			ans += disx[x][i] + disx[y][i];
			x = f[x][i];
			y = f[y][i]; 
		}
	}
	return ans + disx[x][0] + disx[y][0];
}

signed main(){
	
	IOS
	
	cin >> n >> m;
	for(int i=1;i<n;i++){
		int u , v , w;
		cin >> u >> v >> w;
		ve[u].push_back({v,w});
		ve[v].push_back({u,w});
	}
	dfs(1 , 0 , 0);
	
	for(int i=1;i<=m;i++) cin >> s[i];
	int ans = 0;
	for(int i=1;i<=m;i++){
		if(i + 1 <= m) dp[i][0] = lca(s[i] , s[i+1]) , ans += dp[i][0];
		if(i + 1 <= m) dp[i][1] = lca(s[i] , s[i+2]);
	}
	int now = 0;
	for(int i=1;i<=m;i++){
		now = ans;
		if(i - 1 >= 1) now -= dp[i-1][0];
		if(i + 1 <= m) now -= dp[i][0];
		if(i - 1 >= 1 && i + 1 <= m) now += dp[i-1][1];
		cout << now << " ";
	}
	


	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

J ： 砍树 (树上边差分)

要断开两个点 ， 就要断开两个点之间的边 ， 就是两点之间每条边贡献 + 1 ，用树上边差分去做 ， 找贡献等于 m 且最大的边

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;

int n , m , f[N][21] , d[N] , c[N] , ans;
vector<int>ve[N];
map<PII,int>mp;

void dfs(int x,int fa){
	f[x][0] = fa;
	for(int i=1;(1<<i)<=d[x];i++) f[x][i] = f[f[x][i-1]][i-1];
	
	for(auto k : ve[x]){
		if(k == fa) continue;
		d[k] = d[x] + 1;
		dfs(k , x);
	}
}

int lca(int x,int y){
	if(d[x] < d[y]) swap(x,y);
	for(int i=20;i>=0;i--) if(d[x] - (1 << i) >= d[y]) x = f[x][i];
	if(x == y) return x;
	for(int i=20;i>=0;i--){
		if(f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}

void dfs1(int x,int fa){
	
	for(auto k : ve[x]){
		if(k == fa) continue;
		dfs1(k , x);
		c[x] += c[k];
	}
	if(c[x] == m) ans = max(ans , mp[{x,fa}]);
}

int main(){

	IOS

	cin >> n >> m;
	for(int i=1;i<=n-1;i++){
		int u , v;
		cin >> u >> v;
		mp[{u,v}] = mp[{v,u}] = i;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	
	dfs(1,0);
	
	for(int i=1;i<=m;i++){
		int u , v , w;
		cin >> u >> v;
		w = lca(u , v);
		c[u]++;c[v]++;c[w]-=2;
	}
	
	dfs1(1,0);
	
	if(ans == 0) cout << "-1";
	else cout << ans;


	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

http://www.kler.cn/a/11706.html

相关文章：

  • 【C++】一种针对代码的连续条件检查方案，累计布尔结果
  • python: postgreSQL using psycopg2 or psycopg
  • 记录学习react的一些内容
  • 【学习笔记】数据结构（七）
  • 2024开发者浏览器必备扩展，不允许还有人不知道~
  • 分享一个傻瓜式一键启动的加速器
  • 网络安全之从原理看懂 XSS
  • 4月想跳槽的同学，没有更好的选择，可以去美团
  • pmp证书报考流程+pmp备考+pmp学习干货+pmp指南汇总
  • Socket套接字编程(实现TCP和UDP的通信)
  • 随想录Day55--动态规划: 392.判断子序列 , 115.不同的子序列
  • HTTP协议详解(一)
  • C ++匿名函数:揭开C++ Lambda表达式的神秘面纱
  • CloudCompare如何使用基础功能？
  • Java这么卷，还有前景吗？
  • 接口面试题
  • LeetCode 1041. 困于环中的机器人
  • namedtuple 命名元祖
  • 让PyTorch训练速度更快，你需要掌握这17种方法
  • 倍增？最近公共祖先？——从定义到实现，帮你一步步吃掉它！
  • Python零基础教程
  • IO-IO基础
  • day7 线程的取消和清理
  • Python基础-08 函数基础
  • Python-代码阅读(1)-funcs.py
  • 00.如何学习spring