第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组（部分题解）

2024-05-12 13:36
文章标签 c++ 软件 蓝桥 第十四届 部分 题解 大赛 大学 赛国赛

本文主要是介绍第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组（部分题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 1 子2023
    • 思路:
    • 代码：
  • 2 双子数
    • 思路：
    • 代码：
  • 3 班级活动
    • 思路：
    • 代码：
  • 4 合并数列
    • 思路：
    • 代码：
  • 5 数三角
    • 思路：
    • 代码：
  • 7 AB路线
    • 思路：
    • 代码：
  • 8 抓娃娃
    • 思路：
    • 代码：

1 子2023

思路:

  • 比较基础的线性dp

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
typedef pair<int,int> PII;
const int N = 1e3+10, INF = 0x3f3f3f3f;
int n=2023,ans;
string s="";
int dp[3];
//dp[0]:当前位置之前"2"的个数
//dp[1]:当前位置之前"20"的个数
//dp[2]:当前位置之前:"202"的个数 void solve(){for(int i=1;i<=n;i++) s+=to_string(i);for(int i=0;i<s.size();i++){if(s[i]=='2') dp[0]++,dp[2]+=dp[1]; //2,202else if(s[i]=='0') dp[1]+=dp[0];//20else if(s[i]=='3') ans+=dp[2];//202加上当前位置的3 } cout<<ans; //5484660609
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

2 双子数

思路：

  • 欧拉筛求素数，然后枚举所有素数，找到满足条件的
  • 记得超出范围时要及时break,不然会爆long long

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 5e6+10, INF = 0x3f3f3f3f;
int L=2333,R=23333333333333; 
int ans;
int prime[N],cnt;
bool isprime[N];
set<int> s;void get_prime(){memset(isprime,1,sizeof(isprime));isprime[1]=0;for(int i=2;i<N;i++){if(isprime[i]) prime[++cnt]=i;for(int j=1;j<=cnt&&i*prime[j]<N;j++){isprime[i*prime[j]]=0;if(i%prime[j]==0) break;}}
}void solve(){get_prime();for(int i=1;i<=cnt;i++){int res=prime[i]*prime[i]*prime[i+1]*prime[i+1];if(res>R) break; //及时break,不然会溢出long long!!!for(int j=i+1;j<=cnt;j++){int res=prime[i]*prime[i]*prime[j]*prime[j];if(res>=L&&res<=R) ans++;if(res>R) break;}}cout<<ans; //947293
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

3 班级活动

思路：

  • 认真读题，题目中说了“有且仅有一名同学”，也是就是说两两相同，每对数之间是不同的
  • 所以id个数大于2的部分都是要修改的，根据贪心的思想，我们更希望把这些多出的部分和单个的id来配对！
  • 所以分为两类，多出的部分sum1，和单个的sum2,比较那个大
  • sum1>=sum2,把多出的部分修改为和单个的id相同的id，然后把剩下的sum1全都修改
  • sum1<sum2,就把多出的部分修改为和单个的id相同的id，然后把剩下的sum2修改一半即可！

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,a[N],ans; void solve(){cin>>n;map<int,int> mp;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}int sum1=0,sum2=0,ans=0;for(auto i:mp){if(i.se>2) sum1+=i.se-2; //多出的else if(i.se<2) sum2++; //单个的}if(sum1>=sum2) sum1-=sum2,ans+=sum2+sum1;else sum2-=sum1,ans+=sum1,ans+=sum2/2;cout<<ans;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

4 合并数列

思路：

  • 双指针，分别指向两个数组开头
  • 比较哪个大，小的那个就和后边的合并
  • 相等的话都同时右移

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,m,a[N],b[N];void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];int cnt=0;int i=1,j=1,k1=1,k2=1;while(i<=n||j<=m){
//		cout<<i<<' '<<j<<' '<<a[i]<<' '<<b[j]<<endl;if(a[i]==b[j]){i+=k1; j+=k2;k1=1; k2=1;}else if(a[i]>b[j]){b[j]+=b[j+k2]; ++k2; ++cnt;}else{a[i]+=a[i+k1]; ++k1; ++cnt;}}cout<<cnt;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

5 数三角

思路：

  • 以每个点为顶点，找出到顶点距离相等的点的集合，然后遍历这些点，满足条件答案加1，当然这里的满足条件指的是三点不共线
  • 用斜率来判断三点是否共线

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,ans;
vector<PII> arr;double get_dist(int x1,int y1,int x2,int y2){ //两点间距离 return pow(x1-x2,2)+pow(y1-y2,2);
}bool check(PII p1,PII p2,PII p3){if(p1.fi==p2.fi&&p1.fi==p3.fi) return true; //共线 double k1=(p1.se-p2.se)*1.0/(p1.fi-p2.fi);double k2=(p1.se-p3.se)*1.0/(p1.fi-p3.fi);return k1==k2; //斜率相等，共线 
}void solve(){cin>>n;for(int i=0;i<n;i++){int x,y; cin>>x>>y;arr.push_back({x,y}); //记录坐标 } for(int i=0;i<n;i++){map<int,vector<int>> mp; //存储到i号点距离相等的点的集合 for(int j=0;j<n;j++){if(i!=j){PII p1=arr[i],p2=arr[j];double d=get_dist(p1.fi,p1.se,p2.fi,p2.se);mp[d].push_back(j);}}for(auto t:mp){ //遍历所有的距离 vector<int> v=t.se; //到i号点距离相等的点 for(int j=0;j<v.size();j++){for(int k=j+1;k<v.size();k++){if(!check(arr[i],arr[v[j]],arr[v[k]])) ++ans;}}}}cout<<ans;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

7 AB路线

思路：

  • bfs,每个点可以走多次

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e3+10, INF = 0x3f3f3f3f;
int n,m,k,ans=-1;
char g[N][N];
bool st[N][N][11];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct node{int x,y,num,step;
};void bfs(){queue<node> q;q.push({0,0,1,0});st[0][0][1]=1;while(q.size()){auto t=q.front(); q.pop();int x=t.x,y=t.y,num=t.num,step=t.step;if(x==n-1&&y==m-1){ans=step;break;}for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<0||ty<0||tx>=n||ty>=m) continue;if(num==k){if(g[x][y]==g[tx][ty]||st[tx][ty][1]) continue;st[tx][ty][1]=1;q.push({tx,ty,1,step+1});}else if(g[tx][ty]==g[x][y]){if(st[tx][ty][num+1]) continue;st[tx][ty][num+1]=1;q.push({tx,ty,num+1,step+1});}}}}void solve(){cin>>n>>m>>k;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>g[i][j];}}bfs();cout<<ans;
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

8 抓娃娃

思路：

  • 判断线段是否被区间包含，只需要判断线段的中点是否在区间内，因为题目中已说线段的长度是小于等于区间长度的
  • 所以求出每个线段的终点，然后二分找到范围即可

代码：

#include<bits/stdc++.h>
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define int long long
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,m;
int a[N][2],b[N];void solve(){cin>>n>>m;for(int i=1;i<=n;i++){int l,r; cin>>l>>r;l<<=1; r<<=1;a[i][0]=l,a[i][1]=r;b[i]=l+r>>1; //获取该线段中点 }sort(b+1,b+1+n);for(int i=1;i<=m;i++){int l,r; cin>>l>>r;l<<=1; r<<=1;int pos1=lower_bound(b+1,b+1+n,l)-b;int pos2=upper_bound(b+1,b+1+n,r)-b;cout<<pos2-pos1<<endl;} 
}signed main(){int T=1;
//	IOS;
//	cin>>T;while(T--){solve();} return 0;
}

这篇关于第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 B 组（部分题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/982771。

相关文章

C++中实现调试日志输出

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
Ubuntu 怎么启用 Universe 和 Multiverse 软件源?

Ubuntu 怎么启用 Universe 和 Multiverse 软件源?

《Ubuntu怎么启用Universe和Multiverse软件源?》在Ubuntu中，软件源是用于获取和安装软件的服务器，通过设置和管理软件源，您可以确保系统能够从可靠的来源获取最新的软件... Ubuntu 是一款广受认可且声誉良好的开源操作系统，允许用户通过其庞大的软件包来定制和增强计算体验。这些软件
阅读更多...
在 VSCode 中配置 C++ 开发环境的详细教程

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode（VSCode）中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境：详细教程1. 什么是 VSCode？2. 安装 VSCo
阅读更多...
C++11的函数包装器std::function使用示例

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2