首页 > 编程语言 >第十四届蓝桥杯大赛软件赛省赛C/C++大学生B组

第十四届蓝桥杯大赛软件赛省赛C/C++大学生B组

时间：2023-04-08 21:55:05浏览次数：45  
标签：return fa 赛省赛 C++ 蓝桥 int solve vec include

第十四届蓝桥杯大赛软件赛省赛C/C++大学生B组

试题A：日期统计

A题直接枚举即可，枚举日期，暴力匹配

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool check(string t){
	if(t.substr(0, 4)!="2023") return false;
	string mon = t.substr(4, 2);
	string day = t.substr(6, 2);
	int m = (mon[0]-'0')*10+(mon[1]-'0');
	int d = (day[0]-'0')*10+(day[1]-'0');
	if(m==1||m==3||m==5||m==7||m==8||m==10||m==12){
		if(d>=1&&d<=31) return true;
	}else if(m==2){
		if(d>=1&&d<=28) return true;
	}else if(m==4||m==6||m==9||m==11){
		if(d>=1&&d<=30) return true;
	}
	return false;
};

string p="",s="";
int ans = 0, n;

string mon[]={"01","02","03","04","05","06","07","08","09","10","11","12"};
string day[]={"01","02","03","04","05","06","07","08","09","10",
"11","12","13","14","15","16","17","18","19","20",
"21","22","23","24","25","26","27","28","29","30","31"};
int md[]={31,28,31,30,31,30,31,31,30,31,30,31};

bool check(string t,string s){
	int j=0;
	for(int i=0;i<t.size();++i){
		if(j==s.size()) return true;
		if(t[i]==s[j]) j++;
	}
	return j==s.size();
}

void solve(){
	while(cin >> s){
		p += s;
	}
	// cout << p << endl;
	n=p.size();
	string t = "2023";
	for(int i=0;i<12;++i){
		for(int j=0;j<md[i];++j){
			string N = t + mon[i] + day[j];
			if(check(p, N)) {
				ans ++;
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
	solve();
	return 0;
}

试题B：01串的熵

可以看出香浓信息熵有单调性(在0不超过1这个前提下)
因此直接二分即可，顺便输出一下结果对应的函数值

#include<bits/stdc++.h>
using namespace std;
#define int long long
double p(int x,int y){ //x 0 y 1
	double P0 = 1.0*x/(x+y);
	double P1 = 1.0*y/(x+y);
	return -1.0*x*x/(x+y)*log2(P0)-1.0*y*y/(x+y)*log2(P1);
}

void solve(){
	int n = 23333333;
	int l=1, r=(n-1)/2;
	double PP = 11625907.5798;
	while(l<r){
		int mid = (l+r)>>1;
		double t = p(mid, n-mid);
		if(t<PP) l=mid+1;
		else r=mid;
	}
	cout << l << endl;
	
	l=11027421;
	printf("%.5lf", p(l, n-l));
}

signed main(){
	solve();
	return 0;
}

试题C：冶炼金属

貌似可以直接O(1)算，但是我选择直接二分

二分的正确性在保证有解的前提下成立

#include<iostream>
#include<vector>
using namespace std;
//V:normal -> 1:X
void solve(){
	int n;
	cin >> n;
	long long x,y,X=1e9,Y=0;
	vector<pair<int,int>> vec;
	for(int i=0;i<n;++i){
		cin >> x >> y;
		vec.push_back({x,y});
	}
	auto check=[&](long long x)->bool{
		for(auto u:vec){
			if(u.first/x < u.second) return false;
		}
		return true;
	};
	long long l=1,r=1e9;
	while(l<r){
		long long mid=(l+r+1)>>1;
		if(check(mid)) l=mid; // x/mid >= y
		else r=mid-1;
	}
	Y=l;
	auto find=[&](long long x)->bool{
		for(auto u:vec){
			if(u.first/x > u.second) return false;
		}
		return true;
	};
	l=1,r=1e9;
	while(l<r){
		long long mid=(l+r)>>1;
		if(find(mid)) r=mid;
		else l=mid+1;
	}
	X=l;
	cout<<X<<" " << Y<<endl;
}

int main(){
	solve();
	return 0;
}

顺便跑了几组对拍：

试题D：飞机降落

N ≤ 10 直接搜，不要想什么贪心

#include<iostream>
#include<vector>
#include<array>
using namespace std;

bool vis[20];
int n;

bool dfs(int num,int now, vector<array<int,3>>& vec){
	if(num==n){
		return true;
	}
	int flag = 0;
	for(int i=0;i<n;++i){
		if(!vis[i]){
			if(now>vec[i][0]+vec[i][1]) return false;
			vis[i] = true;
			flag |= dfs(num+1, now+vec[i][2], vec);
			vis[i]=false;
		}
	}
	return flag;
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;++i) vis[i] = 0;

	vector<array<int,3>> vec;
	for(int i=0;i<n;++i){
		int x,y,z;
		cin >> x >> y >> z;
		vec.push_back({x,y,z});
	}
	bool res = dfs(0, 0, vec);
	cout<<(res?"YES":"NO")<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; cin >>_;
	while(_--) solve();
	return 0;
}
/*
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
*/

试题E：接龙数列

删最少数使得他是接龙序列，即求原序列的最大接龙子序列，然后用n减去。
最大接龙子序列求法：DP
但是我们发现转移类型一共只有9种1~9结尾的数字
因此我们可以开一个数组f[i]表示前i个数字，以第i个结尾的最大接龙子序列。
再开一个数组bac[1~9]表示 以1~9结尾的最大接龙子序列
每次用第i个数组开头的字母对应的数组更新f[i]，然后再用f[i]反过来更新bac即可
细节看代码

#include<iostream>
#include<vector>
#include<array>
#include<string>
using namespace std;

int n;

void solve(){
	cin >> n;
	vector<string> vec;
	for(int i=0;i<n;++i){
		string t;
		cin >> t;
		vec.push_back(t); 
	}
	vector<int> bac(10); //1,2,3....
	vector<int> f(n+1, 0);
	int ans = 0 ;
	for(int i=0;i<n;++i){
		f[i]=max(1, bac[vec[i][0]-'0']+1);
		ans=max(ans, f[i]);
		bac[vec[i].back()-'0'] = 
		  	max(bac[vec[i].back()-'0'], f[i]);
	}
	cout << n-ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

试题F：岛屿个数

先用边缘的海水进行bfs求出"真的海水"，然后再对所有岛屿进行BFS,此时BFS的时候非真的海水可以直接识别为陆地然后入队。
两遍BFS得到答案。

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;

int n,m;
char G[60][60];
int vis[60][60], g[60][60], water[60][60];

int d[][2]={1,0,0,1,-1,0,0,-1};
int mov[][2]={{1,0},{-1,0},{0,1},{0,-1},{1,-1},
				{1,1},{-1,-1},{-1,1}};

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[i][j] = g[i][j] = water[i][j] = 0;
		}
	}

	for(int i=1;i<=n;++i){
		cin >> (G[i]+1);
		for(int j=1;j<=m;++j){
			g[i][j] = G[i][j]-'0';
		}
	}

	queue<pair<int,int>> q;
	for(int i=1;i<=n;++i){
		if(g[i][1] == 0){
			water[i][1] = true;
			q.push({i, 1});
		}
		if(g[i][m] == 0){
			water[i][m] = true;
			q.push({i, m});
		}
	}

	for(int i=1;i<=m;++i){
		if(g[1][i] == 0){
			if(!water[1][i]){
				water[1][i] = true;
				q.push({1, i});
			}
		}
		if(g[n][i] == 0){
			if(!water[n][i]){
				water[n][i] = true;
				q.push({n, i});
			}
		}
	}

	while(q.size()){
		auto u=q.front(); q.pop();
		int x=u.x,y=u.y;
		for(int i=0;i<8;++i){
			int xx=x+mov[i][0], yy=y+mov[i][1];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!water[xx][yy]&&!g[xx][yy]){
				q.push({xx, yy});
				water[xx][yy] = true;
			}
		}
	}

	while(q.size()) q.pop();
	
	int idx = 0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!water[i][j]&&g[i][j]&&!vis[i][j]){
				q.push({i, j});
				vis[i][j]=++idx;
				while(q.size()){
					auto u=q.front(); q.pop();
					int x=u.x,y=u.y;
					for(int i=0;i<4;++i){
						int xx=x+d[i][0], yy=y+d[i][1];
						if(xx>=1&&xx<=n&&yy>=1&&yy<=m
						&&!vis[xx][yy]&&!water[xx][yy]){
							vis[xx][yy]=idx;
							q.push({xx,yy});
						}
					}
				}
			}
		}
	}
	cout << idx << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	cin >>_;
	while(_--) solve();
	return 0;
}

/*
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
*/

试题G：子串简写

二分/双指针都行
先按照位置处理出来两个数组
然后枚举开头的位置，二分出结尾在另一个数组的合法位置，直接累加答案

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;

int k;
char st,ed;
string p;

void solve(){
	cin >> k;
	cin >> p >> st >> ed;
	vector<int> ps,pe;
	for(int i=0;i<p.size();++i){
		if(p[i]==st) ps.push_back(i);
		if(p[i]==ed) pe.push_back(i);
	}

	long long ans = 0;
	for(int i=0;i<ps.size();++i){
		int x = ps[i];
		int X = x + k - 1;
		int l=0,r=pe.size()-1;
		while(l<r){
			int mid=(l+r)>>1;
			if(pe[mid] >= X) r=mid;
			else l=mid+1;
		}
		if(pe[l] >= X){
			ans += pe.size() - l;
		}
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

试题H：整数删除

双链表维护每个数左边和右边分别是什么数
set维护每个位置的值和要删的最小值
本题考察STL的用法

#include<iostream>
#include<vector>
#include<algorithm>
#include<array>
#include<string>
#include<queue>
#include<set>
#define x first
#define y second
using namespace std;

int n,k;

void solve(){
	cin >> n >> k;
	vector<int> a(n+1),pre(n+1),nxt(n+1);
	set<pair<int,int>> ds;

	for(int i=1;i<=n;++i){
		pre[i] = i-1;
		nxt[i] = i+1;
	}

	for(int i=1;i<=n;++i){
		cin >> a[i];
		ds.insert({a[i], i});
	}

	for(int t=1;t<=k;++t){
		auto pos=ds.begin();
		int x=pos->first, y=pos->second;
		int l = pre[y], r = nxt[y];

		ds.erase(pos);
		pre[nxt[y]]=pre[y];
		nxt[pre[y]]=nxt[y];
		pre[y]=-1, nxt[y]=-1;
		
		if(l>0){
			ds.erase(ds.find({a[l], l}));
			a[l] += x;
			ds.insert({a[l], l});
		}
		if(r<=n){
			ds.erase(ds.find({a[r], r}));
			a[r] += x;
			ds.insert({a[r], r});
		}
	}
	vector<pair<int,int>> temp;
	for(auto u:ds){
		temp.push_back({u.y, u.x});
	}
	sort(temp.begin(), temp.end());
	for(auto u:temp){
		cout << u.y << " ";
	}cout<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

试题I：景区导游

LCA, 没啥好说的

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;
#define debug(x) cout<<#x<<": "<<x<<endl
#define N 100010
vector<pair<int,int>> edge[N];
int n,m,k;
int dep[N],fa[20][N];
int rout[N];
queue<int> q;

void bfs(){
	for(int i=1;i<=n;++i) dep[i]=-1;
	dep[1]=0;
	q.push(1);
	while(q.size()){
		auto u=q.front(); q.pop();
		for(auto v:edge[u]){
			int ver = v.x, w=v.y;
			if(dep[ver]==-1){
				dep[ver] = dep[u] + w;
				q.push(ver);
				fa[0][ver] = u;
				for(int i=1;i<=19;++i){
					fa[i][ver] = fa[i-1][fa[i-1][ver]];
				}
			}
		}
	}
}

int lca(int x,int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i=19;i>=0;--i){
		if(dep[fa[i][x]] >= dep[y])
			x = fa[i][x];
	}
	if(x==y) return x;
	for(int i=19;i>=0;--i){
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x], y=fa[i][y];
	}
	return fa[0][x];
}

int dist(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}

void solve(){
	cin >> n >> k;
	for(int i=1;i<n;++i){
		int x,y,z;
		cin >> x >> y >> z;
		edge[x].push_back({y, z});
		edge[y].push_back({x, z});
	}
	bfs();
	vector<int> a(k+1);
	for(int i=1;i<=k;++i){
		cin >> a[i];
	}

	int now = a[1];
	long long time = 0;
	for(int i=1;i<=k;++i){
		time += dist(now, a[i]);
		now = a[i];
	}

	cout << time - dist(a[1], a[2]) << " ";
	now = a[1];
	for(int i=2;i<=k;++i){
		int temp = time;
		temp -= dist(now, a[i]);
		if(i!=k){
			temp -= dist(a[i], a[i+1]);
			temp += dist(now, a[i+1]);
		}
		cout << temp << " ";
		now = a[i];
	}cout << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}
/*
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1
*/

试题J：砍树

树上差分，也是LCA，最后再DFS一下

#include<iostream>
#include<vector>
#include<array>
#include<string>
#include<queue>
#define x first
#define y second
using namespace std;
#define debug(x) cout<<#x<<": "<<x<<endl
#define N 100010

int n,m,k;
vector<int> edge[N];
pair<int,int> p[N];
int w[N],dep[N],fa[20][N];
pair<int,int> edges[N];

void bfs(){
	for(int i=1;i<=n;++i) dep[i]=-1;
	queue<int> q;
	q.push(1);
	dep[1]=1;
	while(q.size()){
		auto u=q.front(); q.pop();
		for(auto v:edge[u]){
			if(dep[v]==-1){
				dep[v]=dep[u]+1;
				q.push(v);
				fa[0][v] = u;
				for(int i=1;i<=19;++i)
					fa[i][v]=fa[i-1][fa[i-1][v]];
			}
		}
	}
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x, y);
	for(int i=19;i>=0;--i){
		if(dep[fa[i][x]] >= dep[y])
			x=fa[i][x];
	}
	if(x==y) return x;
	for(int i=19;i>=0;--i){
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x], y=fa[i][y];
	}
	return fa[0][x];
}

int f[N];

void dfs(int u,int pre){
	f[u] = w[u];
	for(auto v:edge[u]){
		if(v!=pre){
			dfs(v, u);
			f[u] += f[v];
		}
	}
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<n;++i){
		int x,y;
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
		edges[i] = {x, y};
	}
	bfs();
	for(int i=1;i<=m;++i){
		cin >> p[i].x >> p[i].y;
		w[p[i].x] ++, w[p[i].y] ++;
		w[fa[0][lca(p[i].x, p[i].y)]] -= 1;
		w[lca(p[i].x, p[i].y)] -= 1;
	}
	dfs(1, -1);
	int ans = -1;
	for(int i=1;i<n;++i){
		int x=edges[i].x, y=edges[i].y;
		if(dep[x]<dep[y]) swap(x, y);
		//y-x
		if(f[x]==m){
			ans=max(ans, i);
		}
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int _=1; 
	// cin >>_;
	while(_--) solve();
	return 0;
}

标签：return,fa,赛省赛,C++,蓝桥,int,solve,vec,include
From： https://www.cnblogs.com/bujidao1128/p/17299331.html

相关文章

  • C++多核多线程同步实现
    使用MakefileC++11工程模拟dsp的多核同步逻辑，使用多线程模拟多核，多个线程通过C++11的条件变量实现同步。当某一线程执行到同步函数syn_func时，判断是否其他线程执行到此处了，若有其他线程没有执行到此处，本线程就应阻塞。当最后一个线程执行到同步函数时，通知所有线程解除阻塞，实现......
  • C++,OpenCV图像像素运算(6)
    参与算术运算图像的数据类型、通道数目、大小必须相同算术运算加法：addvoidadd(InputArraysrc1,InputArraysrc2,OutputArraydst,InputArraymask=noArray(),intdtype=-1);/******************************************************************** src1： 输入图1* ......
  • C++primer第五章
    5.1 简单语句表达式语句的作用是执行表达式并丢弃掉求值结果。最简单h的语句是空语句，空语句中只有一个单独的分号。复合语句是指用花括号括起来的语句和声明序列，复合语句也被称为块。一个块就是一个作用域。5.2 语句作用域定义在控制结构内的变量作......
  • C++ 并发编程实战 第二章 线程管控
    第二章线程管控std::thread简介构造和析构函数///默认构造///创建一个线程，什么也不做thread()noexcept;///带参构造///创建一个线程，以A为参数执行F函数template<classFn,class...Args>explicitthread(Fn&&F,Args&&...A);///拷贝构造（不可用）thread......
  • C++primer第四章表达式
    4.1 基础4.1.1 基本概念当一个对象作为右值时，用的是对象的值。当一个对象作为左值时，用的是对象的身份(在内存中的位置)。如果表达式的求值结果是左值，decltype作用于该表达式得到一个引用类型。4.1.2 优先级与结合律括号优先级比较高。在第四章结尾处附上了......
  • 大二蓝桥杯菜鸟的自我反省 & 未来计划
    悟已往之不谏知来者之可追保持你的决心！xilan：大学就像一个梦幻的泡泡，外面则是竞争残酷的社会。内心：想做动画/AI方向，简单的目标才能走得更深更远一定要去教室自习室！怀疑自己的时候看一看：zhuanlan.zhihu.com/p/479036890本周任务acwing：每日3题，笔记完成角色动画隔2天，跑一......
  • 2023年蓝桥杯软件类省赛 C/C++ B组 解析
    还有一题忘了题意是什么了，等拿到题面了再更中间的题目顺序也忘了，填空题的数据也暂时还没有，暂时只有简单的思路，包括后面大题数据范围和是否多组都有点记不清A将题面序列处理成数组放代码里直接枚举八个位置的\(O(n^8)\)复杂度对于\(n=100\)的范围显然本地跑也跑不出来但由......
  • 蓝桥杯 2022 省 B
    C-刷题统计https://www.luogu.com.cn/problem/P8780签到题，先大跨步对每周的题数取模，然后暴力计算最后一周需要做的题。intmain(){ i64a=read(),b=read(),n=read(); i64ans=n/(5*a+2*b)*7,rest=n%(5*a+2*b); for(inti=1;i<=5;i......
  • CMU_15_445_project_0_C++_Primer
    CMU15_445project_0C++Primertask1Copy-On-WriteTrieGetGet比较简单,遍历字符串和trie,找得到就返回值,找不到就返回nullptr.Put每个树有一个没有value的根节点,节点的类型分为TrieNode类和TrieNodeWithValue类,TrieNode是基类不存value,TrieNodeWithValue类继......
  • C++笔记（一）
    C++笔记（一）反复考量之后，还是决定将C++作为我的第二语言以及以后的主力开发语言。目录C++笔记（一）语法基础基本数据类型变量、常量作用域基本运算补码字节序基本结构顺序结构分支结构循环结构指针内存空间动态分配内存二级指针空指针野指针函数指针常见容器类型数组语法基础基本数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99