第十四届蓝桥杯c++b组

2024-04-12 22:12
文章标签 c++ 蓝桥 第十四届

本文主要是介绍第十四届蓝桥杯c++b组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.日期统计

前四位已经固定，四重循环暴力生成后四位，并将合法的日期记录下来，然后检验这些日期能否被生成

具体如何检验：

由于题目说的是子序列，所以可以跳着选，但是相对顺序是不能变的，所以对于给定的100个数，从前往后一位一位和日期的8位匹配，如果一位匹配成功就匹配下一位，如果日期的8位都匹配成功了，那么就说明该日期合法

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int mon[13]={-1,31,29,31,30,31,30,31,31,30,31,30,31};
void solve() {set<int>s;int a[100]={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};for(int i=0;i<=9;i++){for(int j=0;j<=9;j++){for(int k=0;k<=9;k++){for(int m=0;m<=9;m++){int tmp=2023;tmp=tmp*10+i;tmp=tmp*10+j;tmp=tmp*10+k;tmp=tmp*10+m;string x=to_string(tmp);int month=(x[4]-'0')*10+x[5]-'0';int day=(x[6]-'0')*10+x[7]-'0';if(month>=1&&month<=12&&day>=1&&day<=mon[month]) s.insert(tmp);}}}}int ans=0;for(auto v:s){string t=to_string(v);int cnt=0;for(int i=0;i<100;i++){if(a[i]==t[cnt]-'0') cnt++;}if(cnt==(int)t.size()) ans++;}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

2.01串的熵

就是很简单的式子，枚举0的个数和1的个数，检验能否满足给定式子

#include<bits/stdc++.h>
#define endl '\n'
#define eps 1e-4
#define int long long
using namespace std;
void solve() {for(int i=0;i<=23333333;i++){//枚举0的个数int j=23333333-i;//1的个数if(i>j) break;double p0=(double)i/23333333;//0的占比double p1=(double)j/23333333;//1的占比double sum0=(-1)*i*p0*log2(p0);double sum1=(-1)*j*p1*log2(p1);double sum=sum0+sum1;if(abs(sum-11625907.5798)<eps){cout<<i<<endl;return;}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

3.冶炼金属

法一：

找一下规律，比如题目中的样例

3
75 3
53 2
59 2

75/3=25
75/4=1875/25=3
75/24=3
75/23=3
...
75/19=3
75/18=4

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];int maxn=2e9,minn=0;for(int i=1;i<=n;i++){int u=a[i]/b[i];int v=a[i]/(b[i]+1)+1;maxn=min(maxn,u);minn=max(minn,v);}cout<<minn<<' '<<maxn<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

法二：二分答案

在[1,1e9]二分出一个答案

如果是求最小的转换率，那么对于每个答案，check每条记录是否满足产出均小于等于b[i]，如果是返回true，找到最小的返回为true的转换率

产出的均小于等于b,需要找到最小的x满足产出均等于b[i],一定存在,因为题目说一定有解

求最大的转换率同理

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
bool check1(int x){for(int i=1;i<=n;i++){if(a[i]/x>b[i]) return false;}return true;//产出的均小于等于b,需要找到最小的x满足产出均等于b[i],一定存在,因为题目说一定有解
}
bool check2(int x){for(int i=1;i<=n;i++){if(a[i]/x<b[i]) return false;}return true;//产出的均大于等于b,需要找到最大的x满足产出均等于b[i],一定存在,因为题目说一定有解
}
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];int l=1,r=1e9;while(l<r){int mid=(l+r)>>1;if(check1(mid)) r=mid;else l=mid+1;}int minn=l;l=1,r=1e9;while(l<r){int mid=(l+r+1)>>1;if(check2(mid)) l=mid;else r=mid-1;}int maxn=l;cout<<minn<<' '<<maxn<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

4.飞机降落

数据很小，直接暴力枚举每种情况，并check是否至少一种情况可以使得飞机成功降落

全排列即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=15;
int t[N],d[N],l[N];
int a[N];
int n;
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>t[i]>>d[i]>>l[i],a[i]=i;do{bool ok=true;int ed=0;//上一架飞机降落结束时间for(int i=1;i<=n;i++){if(t[a[i]]+d[a[i]]<ed){ok=false;break;}int st=max(ed,t[a[i]]);//开始降落时间ed=st+l[a[i]];}if(ok){cout<<"YES"<<endl;return;}}while(next_permutation(a+1,a+1+n));cout<<"NO"<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

5.接龙数列

问最少删除几个，也就是说最多保留几个

其实可以先求最长接龙子序列的长度，再用总长度减去它

从前往后枚举每个数，当以这个数作为接龙子序列的结尾时，它前面一个数的尾必须是它的头，所以dp[尾]=max(dp[尾],dp[头]+1)

dp[x]表示x作为尾的接龙子序列的最长长度

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N];
int n;
void solve() {cin>>n;int ans=0;for(int i=1;i<=n;i++){string s;cin>>s;int len=s.size()-1;int x=s[0]-'0';int y=s[len-1]-'0';dp[y]=max(dp[y],dp[x]+1);ans=max(ans,dp[y]);}cout<<n-ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

6.岛屿个数

和外海接触的岛屿肯定不是子岛屿

先将外围一圈标记为外海，从(0,0)开始搜，将所有的外海搜出来（8方向），标记为2

然后对于那些内海，仍为0，将它们都标记为陆地

最后搜陆地一共有几个连通块即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=55;
char s[N][N];
int m,n;
int dx1[8]={0,0,1,-1,1,1,-1,-1},dy1[8]={1,-1,0,0,-1,1,-1,1};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void dfs1(int x,int y){//找和外海相连的海,将所有外海标记为2s[x][y]='2';for(int i=0;i<8;i++){int tx=x+dx1[i],ty=y+dy1[i];if(tx<0||tx>m+1||ty<0||ty>n+1||s[tx][ty]!='0') continue;dfs1(tx,ty);}
}
void dfs2(int x,int y){//对于找到的所有外海,去找和外海接壤的陆地s[x][y]='3';for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<0||tx>m+1||ty<0||ty>n+1||s[tx][ty]!='1') continue;dfs2(tx,ty);}
}
void solve() {cin>>m>>n;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>s[i][j];}}//外海一圈,朝8个方向搜,搜到所有的外海for(int i=0;i<=m+1;i++){for(int j=0;j<=n+1;j++){if(s[i][j]=='1'||s[i][j]=='0') continue;s[i][j]='0';}}dfs1(0,0);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(s[i][j]=='0') s[i][j]='1';//将内海变成陆地}}int ans=0;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i][j]=='1'){dfs2(i,j);ans++;}}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

7.子串简写

将字符为c1的位置都存储下来，然后枚举到字符为c2时，二分到最大的满足以c2结尾，c1开头的长度大于等于k的位置，然后该位置以及前面的c1都满足，作为对答案的贡献

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int k;
string s;
char c1,c2;
void solve() {cin>>k;cin>>s;cin>>c1>>c2;map<char,int>mp;vector<int>a;int ans=0;for(int i=0;i<(int)s.size();i++){if(s[i]==c1) a.push_back(i);else if(s[i]==c2){if(!a.size()) continue;int l=0,r=a.size()-1;while(l<r){int mid=(l+r+1)>>1;if(i-a[mid]+1>=k) l=mid;else r=mid-1;}if(i-a[l]+1>=k) ans+=l+1;}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

8.整数删除

线性存储结构进行删除操作时间复杂度为O（n），使用链式存储结构更适合

用双链表，这里用数组模拟

利用优先队列（小根堆），方便取出值最小的元素

这里我们删除一个元素时，需要将它左右两边的元素都加上它的值，但是我们无法在优先队列随意修改元素，所以这里有一个技巧，先记录下来下标为x的元素更新后的值，先不急着更新优先队列，类似于线段树的懒标记，等到用到了才更新优先队列，当队头的值是最新的值的时候，那么说明更新过了，那么执行删除操作，否则，需要在优先队列中更新它的值

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=5e5+10;
int a[N];
int l[N],r[N];//用数组模拟双链表
int n,k;
void del(int x){l[r[x]]=l[x],r[l[x]]=r[x];a[l[x]]+=a[x],a[r[x]]+=a[x];
}
void solve() {cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) l[i]=i-1;r[0]=1;for(int i=n;i>=1;i--) r[i]=i+1;priority_queue<PII,vector<PII>,greater<PII>>q;for(int i=1;i<=n;i++) q.push({a[i],i});while(k--){auto t=q.top();q.pop();if(t.first!=a[t.second]){q.push({a[t.second],t.second});k++;}else del(t.second);}for(int i=r[0];i<=n;i=r[i]) cout<<a[i]<<' ';cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

这篇关于第十四届蓝桥杯c++b组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...
C++中assign函数的使用

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2