第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组（补题）

news/2024/4/29 10:21:46/文章来源:https://blog.csdn.net/2301_77012063/article/details/137102490

文章目录

    • 1 日期统计
    • 2 01串的熵
    • 3 冶炼金属
    • 4 飞机降落
    • 5 接龙数列
    • 6 岛屿个数
    • 7 子串简写
    • 8 整数删除
    • 9 景区导游
    • 10 砍树

前言：时隔一年，再次做这套题(去年参赛选手)，差点道心不稳T_T，故作此补题！

1 日期统计

  • 没写出来，看题解知道了一种暴力的思想，枚举所有2023年的日期，看看有没有满足条件的数。
  • 关于如何提取题中的数字？可以复制到excel当中，然后ctrl+H，将空格替换为英文逗号！
#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
typedef pair<int,int> PII;
const int N = 2e5+10, INF = 0x3f3f3f3f;
int a[N]={0,5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3};
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int n=100,ans;void solve() {for(int m=1;m<=12;m++) //枚举所有日期for(int d=1;d<=mon[m];d++){int tar[9]={0,2,0,2,3,m/10,m%10,d/10,d%10}; //当前日期int num=1;for(int i=1;i<=100;i++){ //看看有没有符合条件的if(a[i]==tar[num]){num++;if(num==9){ans++; break;}}}}cout<<ans;
}signed main() {
//	IOS;int T=1;
//	cin>>T;while(T--) {solve();}return 0;    
}

2 01串的熵

  • 因为0的出现次数比1的出现次数少，所以我们可以枚举0的个数，1的个数即为01串的长度减去0的个数。
  • 然后根据公式即可求得
#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
const int N = 2e5+10, INF = 0x3f3f3f3f;
int len=23333333,cnt;
double res,tar=11625907.5798; void solve() {for(int i=0;i<=len;i++){ //0的数量 int j=len-i; //1的数量 res=-1.0*(1.0*i/len)*i*(log(1.0*i/len)/log(2))+(-1)*(1.0*j/len)*j*(log(1.0*j/len)/log(2));if(res>=tar){printf("%.4f %.4f\n",res,tar);cout<<i<<endl; break;}}}signed main() {
//	IOS;int T=1;
//	cin>>T;while(T--) {solve();}return 0;    
}

3 冶炼金属

  • 读完题目后，我们可以枚举答案来求得V的最大值和最小值，即用到二分答案。
#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
const int N = 1e4+10, INF = 0x3f3f3f3f;
int n,a[N],b[N];
int res1,res2;bool check1(int x){for(int i=1;i<=n;i++){int num=a[i]/x; //转换的个数if(num>b[i]) return false;}return true;
}int calc1(){int l=0,r=1e9+10;while(l+1<r){int mid=l+r>>1;if(check1(mid)) r=mid; //满足条件，缩小范围求最小值else l=mid;}return r;
}bool check2(int x){for(int i=1;i<=n;i++){int num=a[i]/x;if(num<b[i]) return false;}return true;
}int calc2(){int l=0,r=1e9+10;while(l+1<r){int mid=l+r>>1;if(check2(mid)) l=mid;else r=mid;}return l;
}void solve() {cin>>n;for(int i=1;i<=n;i++)cin>>a[i]>>b[i];res1=calc1(); //最小值res2=calc2(); //最大值cout<<res1<<' '<<res2;
}signed main() {
//	IOS;int T=1;
//	cin>>T;while(T--) {solve();}return 0;    
}

4 飞机降落

  • N的数据范围只有10，我们可以暴力枚举所有飞机降落的顺序，如果有一个满足就符合要求。
  • 用全排列函数next_permutation函数可以实现这一操作
#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
const int N = 1e3+10, INF = 0x3f3f3f3f;
struct node{int t,d,l;
}a[N];
int n,id[N]; void solve() {cin>>n;for(int i=1;i<=n;i++){int t,d,l; cin>>t>>d>>l;a[i]={t,d,l}; id[i]=i;}do{int now=0,flag=1;for(int i=1;i<=n;i++){int t=a[id[i]].t,d=a[id[i]].d,l=a[id[i]].l;if(t+d<now){ //不符合flag=0;break;} else{if(t>now) now=t+l;else now+=l;}}if(flag){cout<<"YES"<<endl;return;}}while(next_permutation(id+1,id+1+n)); cout<<"NO"<<endl;
}signed main() {
//	IOS;int T=1;cin>>T;while(T--) {solve();}return 0;    
}

5 接龙数列

  • 可以将问题转化为求最长的符合要求的接龙序列，然后用总个数减去最长的接龙序列的长度。
  • 这就需要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
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n,num=0;
int x,dp[N];
//dp[i]表示以i为结尾的最长接龙序列的长度 void solve(){cin>>n;string s;for(int i=0;i<n;i++){cin>>s;int x=s[0]-'0',y=s[s.size()-1]-'0'; //取出第一位和最后一位 dp[y]=max(dp[y],dp[x]+1);num=max(num,dp[y]);}cout<<n-num;
}signed main() {
//	IOS;int T=1;
//	cin>>T;while(T--) {solve();}return 0;    
}

6 岛屿个数

  • 连通块，图的遍历问题
  • 可以将所有的连通块染色，每一种颜色代表一个连通块。
  • 然后检查所有的岛屿是不是子岛屿，即该岛屿是否在“环”的内部，如何判断是否在环的内部呢？
  • 如果该岛屿内的任意一个点可以走到边界或边界之外，说明该岛屿不在环内，可以把其它的岛屿看作障碍物；如果在环内，则不可能到达边界点！
  • 判断是否为子岛屿时，需要沿着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 = 1e3+10, INF = 0x3f3f3f3f;
char g[N][N];
int m,n,cnt,ans;
int c[N][N]; 
int dx[]={0,1,0,-1,-1,1,1,-1};
int dy[]={1,0,-1,0,1,1,-1,-1};
set<int> s;void bfs(int sx,int sy){cnt++; //该连通块染色为cntqueue<PII> q;q.push({sx,sy});while(q.size()){auto t=q.front(); q.pop();c[t.fi][t.se]=cnt;for(int i=0;i<4;i++){int tx=t.fi+dx[i];int ty=t.se+dy[i];if(tx<=0||tx>m||ty<=0||ty>n) continue;if(c[tx][ty]||g[tx][ty]=='0') continue;q.push({tx,ty});}}
}bool vis[N][N],flag;
//判断是否在环内
bool check(int x,int y,int col){if(flag) return true;for(int i=0;i<8;i++){int tx=x+dx[i];int ty=y+dy[i];if(c[tx][ty]!=col&&c[tx][ty]) continue;
//		if(col==3) cout<<tx<<' '<<ty<<' '<<flag<<endl;if(tx<=1||ty<=1||tx>=m||ty>=n){ //到达边界，不在环内flag=1;return true;}if(vis[tx][ty]) continue; //已访问过vis[tx][ty]=1;if(check(tx,ty,col)) return true;}return false; //在环内
}void solve() {cin>>m>>n;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)cin>>g[i][j];cnt=0; ans=0; s.clear(); //多组样例！注意清空!memset(c,0,sizeof(c));for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){if(!c[i][j]&&g[i][j]=='1'){bfs(i,j);}}
//	cout<<endl;
//	for(int i=1;i<=m;i++){
//		for(int j=1;j<=n;j++)
//		  cout<<c[i][j];
//		cout<<endl;
//	}set<int> s; //set去重for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){
//	  	cout<<i<<' '<<j<<' '<<c[i][j]<<endl;if(g[i][j]=='1'&&!s.count(c[i][j])&&check(i,j,c[i][j])){s.insert(c[i][j]);}memset(vis,0,sizeof(vis)); flag=0;}cout<<s.size()<<endl;
}signed main() {
//	IOS;int T=1;cin>>T;while(T--) {solve();}return 0;    
}

7 子串简写

  • 我们可以记录两个字符a,b的所有位置，然后枚举第一个字符a，二分找到第一个符合要求的字符b的位置，之后所有的字符b都是符合要求的，累加所有答案即可
  • 复杂度为O(n log(n))
#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 lb lower_bound
typedef pair<int,int> PII;
const int N = 2e5+10, INF = 0x3f3f3f3f;
int k,ans;
string s;
set<int> s1;
vector<int> a;
char c1,c2;void solve() {
//	freopen("in.txt","r",stdin); cin>>k>>s>>c1>>c2;for(int i=0;i<s.size();i++){if(s[i]==c1) s1.insert(i); //保存所有位置if(s[i]==c2) a.push_back(i);}for(auto i:s1){int cnt=lb(a.begin(),a.end(),i+k-1)-a.begin(); //二分查找ans+=a.size()-cnt;}
//	freopen("out.txt","w",stdout); cout<<ans;
}signed main() {
//	IOS;int T=1;
//	cin>>T;while(T--) {solve();}return 0;    
}

8 整数删除

  • 优先队列+链表
  • 每次取出数列中的最小值，可以用优先队列实现。
  • 删除和相邻两数加上被删除的值这两个操作用链表来实现。
  • 代码见蓝桥发题解的大佬

9 景区导游

  • 不会T_T
  • 用LCA来求解

10 砍树

  • 树上差分模板题

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_1027714.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数据结构与算法（二）优先队列

数据结构与算法（二）优先队列

数据结构与算法&#xff08;二&#xff09; 优先队列 一、优先队列的基本概念 我们的电脑总是运行着多个程序&#xff0c;电脑会给每个程序分配一个优先级&#xff0c;并首先执行下一个优先级更高的程序。在此情况下&#xff0c;可将其抽象为一个数据结构&#xff0c;该数据结构…
阅读更多...
鸿蒙HarmonyOS开发-FA模型访问Stage模型DataShareExtensionAbility

鸿蒙HarmonyOS开发-FA模型访问Stage模型DataShareExtensionAbility

无论FA模型还是Stage模型&#xff0c;数据读写功能都包含客户端和服务端两部分。 FA模型中&#xff0c;客户端是由DataAbilityHelper提供对外接口&#xff0c;服务端是由DataAbility提供数据库的读写服务。 Stage模型中&#xff0c;客户端是由DataShareHelper提供对外接口&…
阅读更多...
【JavaEE】_Spring MVC项目获取URL中的参数

【JavaEE】_Spring MVC项目获取URL中的参数

目录 1. 单参数 2. 多参数 1. 单参数 .java文件如下&#xff1a; package com.example.demo.controller;import com.example.demo.Person; import org.springframework.web.bind.annotation.*;import java.util.Arrays; import java.util.List;RequestMapping("/Para&…
阅读更多...
SpringBoot Redis 之Lettuce 驱动

SpringBoot Redis 之Lettuce 驱动

一、前言 一直以为SpringBoot中 spring-boot-starter-data-redis使用的是Jredis连接池&#xff0c;直到昨天在部署报价系统生产环境时&#xff0c;因为端口配置错误造成无法连接&#xff0c;发现报错信息如下&#xff1a; 一了解才知道在SpringBoot2.X以后默认是使用Lettuce作…
阅读更多...
jmeter中参数加密

jmeter中参数加密

加密接口常用的方式有&#xff1a; MD5&#xff0c;SHA&#xff0c;HmacSHA RSA AES&#xff0c;DES&#xff0c;Base64 压测中有些参数需要进行加密&#xff0c;加密方式已接口文档为主。 MD5加密 比如MD5加密的接口文档&#xff1a; 请求URL&#xff1a;http://101.34.221…
阅读更多...
【机器学习】数据探索(Data Exploration)---数据质量和数据特征分析

【机器学习】数据探索(Data Exploration)---数据质量和数据特征分析

一、引言 在机器学习项目中&#xff0c;数据探索是至关重要的一步。它不仅是模型构建的基础&#xff0c;还是确保模型性能稳定、预测准确的关键。数据探索的过程中&#xff0c;数据质量和数据特征分析占据了核心地位。数据质量直接关系到模型能否从数据中提取有效信息&#xff…
阅读更多...
linux中查看内存占用空间

linux中查看内存占用空间

文章目录 linux中查看内存占用空间 linux中查看内存占用空间 使用 df -h 查看磁盘空间 使用 du -sh * 查看每个目录的大小 注意这里是当前目录下的文件大小&#xff0c;查看系统的可以回到根目录 经过查看没有发现任何大的文件夹。 继续下面的步骤 如果您的Linux磁盘已满&a…
阅读更多...
VScode中cmake调试

VScode中cmake调试

一般的cmake命令行测试方法&#xff1a; cmake -S . -B build cmake --build build ./build/cmake_debug 在vscode中使用图形化界面操作的方法 main.cpp #include <iostream>int main() {int num_a, num_b;num_a 10;num_b 20;std::cout << "num_a &qu…
阅读更多...
TTS通用播放库技术设计

TTS通用播放库技术设计

TTS音频播放库技术设计 目录介绍 01.整体介绍概述 1.1 项目背景介绍1.2 遇到问题1.3 基础概念介绍1.4 设计目标1.5 问题答疑和思考 02.技术调研说明 2.1 语音播放方案2.2 TTS技术分析2.3 语音合成技术2.4 方案选择说明2.5 方案设计思路2.6 文本生成音频 03.系统TTS使用实践 3…
阅读更多...
CSS（六）

CSS（六）

一、精灵图 1.1 为什么需要精灵图 一个网页中往往会应用很多小的背景图像作为修饰&#xff0c;当网页中的图像过多时&#xff0c;服务器就会频繁地接收和发送请求图片&#xff0c;造成服务器请求压力过大&#xff0c;这将大大降低页面的加载速度。 因此&#xff0c;为了有效…
阅读更多...
Vue挂载全局方法

Vue挂载全局方法

简介&#xff1a;有时候&#xff0c;频繁调用的函数&#xff0c;我们需要把它挂载在全局的vue原型上&#xff0c;方便调用&#xff0c;具体怎么操作&#xff0c;这里来记录一下。 一、这里以本地存储的方法为例 var localStorage window.localStorage; const db {/** * 更新…
阅读更多...
面试八股——Redis——分布式锁——Redisson

面试八股——Redis——分布式锁——Redisson

1.看门狗机制 注意看门狗机制&#xff1a;redisson会监听持有锁的线程&#xff0c;并每隔一段时间(releaseTime/3&#xff0c;默认releaseTime为30s)&#xff0c;如果线程还未释放锁的话&#xff0c;会给锁做一次续期。 2. 主从一致性 实际开发中我们会搭建多台redis服务器&a…
阅读更多...
八大技术趋势案例（区块链量子计算）

八大技术趋势案例（区块链量子计算）

科技巨变，未来已来，八大技术趋势引领数字化时代。信息技术的迅猛发展，深刻改变了我们的生活、工作和生产方式。人工智能、物联网、云计算、大数据、虚拟现实、增强现实、区块链、量子计算等新兴技术在各行各业得到广泛应用，为各个领域带来了新的活力和变革。 为了更好地了解…
阅读更多...
BOT攻击是什么，应当如何防护？

BOT攻击是什么，应当如何防护？

抢票失败、小程序崩溃、平台遭恶意灌水……这些我们日常都可能遇到过的问题的背后很有可能是BOT攻击在兴风作浪。对于企业用户来说&#xff0c;据相关调研显示&#xff0c;近八成企业都曾因BOT攻击而受到经济损失&#xff0c;而面对越来越复杂的BOT攻击&#xff0c;大多数企业表…
阅读更多...
数据结构 之 队列习题 力扣oj(附加思路版)

数据结构 之 队列习题 力扣oj(附加思路版)

优先级队列 #include<queue> --队列 和 优先级队列的头文件 优先级队列&#xff1a; 堆结构 最大堆 和 最小堆 相关函数&#xff1a; front() 获取第一个元素 back() 获取最后一个元素 push() 放入元素 pop() 弹出第一个元素 size() 计算队列中元素…
阅读更多...
鸿蒙HarmonyOS应用开发之USB DDK开发指导

鸿蒙HarmonyOS应用开发之USB DDK开发指导

场景介绍 USB DDK&#xff08;USB Driver Develop Kit&#xff09;是为开发者提供的USB驱动程序开发套件&#xff0c;支持开发者基于用户态&#xff0c;在应用层开发USB设备驱动。提供了一系列主机侧访问设备的接口&#xff0c;包括主机侧打开和关闭接口、管道同步异步读写通信…
阅读更多...
学习JavaEE的日子 Day32 线程池

学习JavaEE的日子 Day32 线程池

Day32 线程池 1.引入 一个线程完成一项任务所需时间为&#xff1a; 创建线程时间 - Time1线程中执行任务的时间 - Time2销毁线程时间 - Time3 2.为什么需要线程池(重要) 线程池技术正是关注如何缩短或调整Time1和Time3的时间&#xff0c;从而提高程序的性能。项目中可以把Time…
阅读更多...
没学数模电可以玩单片机吗?

没学数模电可以玩单片机吗?

我们首先来看一下数电模电在单片机中的应用。数电知识在单片机中主要解决各种数字信号的处理、运算&#xff0c;如数制转换、数据运算等。模电知识在单片机中主要解决各种模拟信号的处理问题&#xff0c;如采集光照强度、声音的分贝、温度等模拟信号。而数电、模电的相互转换就…
阅读更多...
Ubuntu 系统下安装 Redis

Ubuntu 系统下安装 Redis

目录 一、上传 Redis 安装包并解压缩 二、编译 1、安装gcc&#xff0c;不然后面编译报错 2、开始编译 三、生成后台服务 四、修改配置文件 1、设置密码 2、设置后台启动 五、启动服务 一、上传 Redis 安装包并解压缩 tar -zxvf redis-6.0.2.tar.gz 二、编译 1、安装g…
阅读更多...
【分布式】——CAPBASE理论

【分布式】——CAPBASE理论

CAP&BASE理论 ⭐⭐⭐⭐⭐⭐ Github主页&#x1f449;https://github.com/A-BigTree 笔记链接&#x1f449;https://github.com/A-BigTree/tree-learning-notes ⭐⭐⭐⭐⭐⭐ Spring专栏&#x1f449;https://blog.csdn.net/weixin_53580595/category_12279588.html Sprin…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业