蓝桥杯2024国赛--备赛刷题题单

2024-06-01 02:04

本文主要是介绍蓝桥杯2024国赛--备赛刷题题单,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.游戏(单调队列)

注意如果结果是分数,直接设置变量为double,最好不要使用把int类型乘1.0变成分数来计算。

#include <iostream>
#include <queue>
using namespace std;
const int N=1e5+10;
//滑动窗口大小为k,最大值为P,最小值为Q,K=P-Q
//窗口个数为cnt=n-k+1
//所有情况为all=cnt*cnt
//期望值为(K1+K2+...+Kall)/all
//由于熊大选框和熊二选框的情况是一样的,因此只需要
//(K1+K2+...+Kcnt)/cnt
int a[N];
int wd[N];
deque<int>q;//双端队列
int main()
{int n,k;scanf("%d %d\n",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}double sump=0;//窗口最大值加和for(int i=1;i<=n;i++){while(!q.empty()&&a[q.back()]<a[i])q.pop_back();q.push_back(i);//4 3 2 1...(从大到小的窗口)a[i]<=a[q.back()]才加入if(i>=k)//大于等于窗口大小才开始计算答案{ //不在窗口内的下标pop掉while(!q.empty()&&q.front()<=i-k)q.pop_front();sump+=a[q.front()];}}q.clear();//注意要把队列清空!double sumq=0;//窗口最小值加和for(int i=1;i<=n;i++){while(!q.empty()&&a[q.back()]>a[i])q.pop_back();q.push_back(i);//1 2 3 4...(从小到大的窗口)a[i]>=a[q.back()]才加入if(i>=k)//大于等于窗口大小才开始计算答案{ //不在窗口内的下标pop掉while(!q.empty()&&q.front()<=i-k)q.pop_front();sumq+=a[q.front()];}}printf("%.2lf\n",(sump-sumq)/(n-k+1));return 0;
}

2.01游戏(DFS剪枝)

#include<iostream>
using namespace std;
char a[15][15];
bool flag=0;
int n;
bool check()
{//判断行for(int i=0;i<n;i++){int cnt0=0,cnt1=0;//记录连续出现int sum0=0,sum1=0;for(int j=0;j<n;j++){if(a[i][j]=='_')cnt1=0,cnt0=0;//连续中断else if(a[i][j]=='1'){cnt1++;sum1++;cnt0=0;}else if(a[i][j]=='0'){cnt0++;sum0++;cnt1=0;}if(cnt1>2||cnt0>2)return 0;if(sum1>n/2||sum0>n/2) return false;//超过一半就无法保证数量相等}}//判断列for(int i=0;i<n;i++){int cnt0=0,cnt1=0;//记录连续出现int sum0=0,sum1=0;for(int j=0;j<n;j++){if(a[j][i]=='_')cnt1=0,cnt0=0;//连续中断else if(a[j][i]=='1'){cnt1++;sum1++;cnt0=0;}else if(a[j][i]=='0'){cnt0++;sum0++;cnt1=0;}if(cnt1>2||cnt0>2)return 0;if(sum1>n/2||sum0>n/2) return false;//超过一半就无法保证数量相等}}return 1;
}
void dfs(int x,int y)//默认是先向右走再向下走
{if(flag)return;if(y==n){x++;//再向下y=0;//再从左边起始开始}if(x==n){//到达右下角了可以输出答案flag=1;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cout<<a[i][j];}cout<<endl;}return;}if(a[x][y]=='_'){a[x][y]='1';if(check())dfs(x,y+1);//合法才继续往下搜if(flag)return;a[x][y]='0';if(check())dfs(x,y+1);//合法才继续往下搜if(flag)return;a[x][y]='_';//复原}else dfs(x,y+1);
}
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}dfs(0,0);return 0;
}

3.子2023(动态规划)

#include <iostream>
#include <string>
using namespace std;
long long dp[4];//注意开longlong!!
//dp[0]:以2结尾的序列数量
//dp[1]:以20结尾的序列数量
//dp[2]:以202结尾的序列数量
//dp[3]:以2023结尾的序列数量
int main()
{string s;for(int i=1;i<=2023;i++){string str=to_string(i);s+=str;}for(int i=0;i<s.size();i++){if(s[i]=='2'){dp[0]++;dp[2]=dp[2]+dp[1];}else if(s[i]=='0'){dp[1]=dp[1]+dp[0];}else if(s[i]=='3'){dp[3]=dp[3]+dp[2];}}cout<<dp[3];return 0;
}

4.双子数(质因数分解,线性筛)

#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
const ll N=1e7+9;//N*N>23333333333333(2.3*10^13)
ll prime[N];
ll ans;
bool st[N];
//线性筛O(n)
ll getPrime()
{ll cnt=0;for(ll i=2;i<=N;i++){if(!st[i])prime[cnt++]=i;for(ll j=0;prime[j]*i<=N;j++){st[prime[j]*i]=1;if(i%prime[j]==0)break;}}return cnt;
}
int main()
{ll idx=getPrime();//预处理得到素数for(ll i=0;i<idx;i++)//遍历所有素数{ll p2=prime[i]*prime[i];//p^2if(p2*p2>23333333333333)break;for(ll j=i+1;j<idx;j++){ll q2=prime[j]*prime[j];//q^2if(p2*q2>23333333333333)break;if(p2*q2<2333)continue;ans++;//在区间内}}cout<<ans<<endl;return 0;
}

5.合并数列(双指针)

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int n,m;
int ans;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];int i=0,j=0;//从0开始//采用前缀和的思想int cnta=0,cntb=0;while(i<=n&&j<=m){if(cnta==cntb)//注意相等是等号!{cnta=a[++i];cntb=b[++j];}else if(cnta<cntb){cnta+=a[++i];ans++;}else if(cntb<cnta){cntb+=b[++j];ans++;}}cout<<ans<<endl;return 0;
}

6.数三角形(枚举,STL)

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
#define ll long long
#define pii pair<int,int>
int main()
{int n;cin>>n;vector<pii>a(n+2);map<pii,int>m;//表示坐标(x,y)点一共出现了几次for(int i=1;i<=n;i++){cin>>a[i].first>>a[i].second;m[{a[i].first,a[i].second}]++;}int ans=0;for(int i=1;i<=n;i++)//枚举每个点作为顶点{map<ll,vector<int>>st;//距离到达为ll时有多少个点for(int j=1;j<=n;j++){ll dist=(a[i].first-a[j].first)*(a[i].first-a[j].first)+(a[i].second-a[j].second)*(a[i].second-a[j].second);if(dist!=0)st[dist].push_back(j);//已经保证了i!=j}//计算合法数量for(auto &x:st)//st为map类型{vector<int>&v=x.second;int cnt=v.size();ans+=cnt*(cnt-1)/2;//两两组合可以作为答案//保证三点不共线int del=0;//不合法的点的数量for(int j=0;j<v.size();j++){int x1=a[i].first,y1=a[i].second;int x2=a[v[j]].first,y2=a[v[j]].second;int x3=2*x1-x2,y3=2*y1-y2;//三点共线,都在一个圆内//x1=(x3+x2)/2,y1=(y3+y2)/2del+=m[{x3,y3}];}ans-=(del/2);//三点共线 两点的情况多计算了一次}}cout<<ans<<endl;return 0;
}

7.AB路线(BFS)

#include <iostream>
#include <queue>
using namespace std;
#define ll long long
const int N=1000+500;
char a[N][N];
int n,m,k;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
ll vis[N][N][11],dis[N][N][11];
//因为一个位置可以重复走多次,
//再加一维(到这个位置是第几个字母)
struct node
{int x,y,cnt;//cnt为当前为第cnt个相同字母node(int x=0,int y=0,int cnt=0):x(x),y(y),cnt(cnt){}
};
queue<node>q;//用于bfs
int main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}q.push(node(1,1,1));//cnt=1,为第一个相同字母vis[1][1][1]=1;if(n==1&&m==1)//特判{cout<<0<<endl;return 0;} //开始BFSwhile(!q.empty()){node t=q.front();q.pop();for(int i=0;i<4;i++){int xx=t.x+dx[i];int yy=t.y+dy[i];int cc=t.cnt+1;if(xx<1||xx>n||yy<1||yy>m)continue;if(cc>k)//需要变{if(a[t.x][t.y]==a[xx][yy])continue;else cc=1;}else //不需要变{if(a[t.x][t.y]!=a[xx][yy])continue;}if(vis[xx][yy][cc]!=0)continue;vis[xx][yy][cc]++;dis[xx][yy][cc]=dis[t.x][t.y][t.cnt]+1;if(xx==n&&yy==m)//BFS先找到的一定是最小的,直接输出{cout<<dis[xx][yy][cc]<<endl;return 0;}q.push(node{xx,yy,cc});}}return 0;
}

8.跑步计划(日期问题)

#include <iostream>
#include <string>
using namespace std;
int main()
{int ans=0;int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};if((2023%400==0)||(2023%4==0&&2023%100!=0))a[2]++;int days=0;for(int i=1;i<=12;i++){for(int j=1;j<=a[i];j++){days++;string s1=to_string(i);string s2=to_string(j);   //2023年1月1日是周日if(s1.find('1')!=-1||s2.find('1')!=-1||days%7==2)ans+=5;else ans++;}}cout<<ans<<endl;return 0;
}

9.火车运输(动态规划背包问题)

#include <iostream>
using namespace std;
const int N=1000+10;
int dp[N][N];
int w[N];
int n,a,b;
int main()
{cin>>n>>a>>b;for(int i=1;i<=n;i++)cin>>w[i];// 三种情况:不选,放A,放Bfor(int i=1;i<=n;i++){for(int j=a;j>=0;j--){for(int k=b;k>=0;k--){if(j-w[i]>=0)dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);if(k-w[i]>=0)dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]); }}}cout<<dp[a][b]<<endl;return 0;
}

10.走方格(动态规划图论)

#include <iostream>
using namespace std;
const int N=1000+100;
int a[N][N];
int dp[N][N];
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}for(int i=0;i<n;i++){dp[i][0]=i;//表示走到此步需要的时间//因为连续的跳步只发生在水平方向}for(int i=0;i<n;i++){for(int j=1;j<n;j++){dp[i][j]=1e9;//初始为大值// 从上面下来if(i>0)dp[i][j]=min(dp[i][j],dp[i-1][j]+1);// 向左到达最远的地方(即最小的地方)// 因为是从上到下,从左到右枚举,所以是向左(因为左边已是更新好的值)int temp=j;//临时变量while(a[i][temp]<a[i][temp-1]&&temp>=1)//严格小于{dp[i][j]=min(dp[i][j],dp[i][temp-1]+1);temp--;}//从左边一个过来dp[i][j]=min(dp[i][j],dp[i][j-1]+1);}}cout<<dp[n-1][n-1]<<endl;return 0;
}

11.选段排序(堆,贪心)

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm> 
using namespace std;
const int N=2e5+10;
int a[N];
priority_queue<int,vector<int>>q1;//大顶堆
priority_queue<int,vector<int>,greater<int>>q2;//小顶堆 
int main()
{int n,p,q;cin>>n>>p>>q;for(int i=1;i<=n;i++)cin>>a[i];sort(a+p,a+1+q);//注意sort的区间!!for(int i=p;i<=q;i++){//区间[p,q]先放入 q1.push(a[i]);//大 q2.push(a[i]);//小 } int ans=a[q]-a[p];//先得到初始的答案 //拓展右区间由[p,q]到[p,n]int maxx=a[q];int minn=a[p];for(int i=q+1;i<=n;i++){int t=q1.top();//先取堆顶 if(a[i]<minn)minn=a[i];//小的肯定可以排序到p if(a[i]<t)//t是拓展时用的 {q1.pop();//保证队列元素在[p,q]中q1.push(a[i]);ans=max(ans,q1.top()-minn);}	} //拓展左区间由[p,q]到[1,q],向左减法 for(int i=p-1;i>=1;i--){int t=q2.top();//先取堆顶 if(a[i]>maxx)maxx=a[i];//大的肯定可以排序到qif(a[i]>t){q2.pop();//保证队列元素在[p,q]中 q2.push(a[i]);ans=max(ans,maxx-q2.top());	} } cout<<ans<<endl;return 0;
}

12.混乘数字(数学,枚举)

#include <iostream>
#include <string>
#include <map>
#include <set>
using namespace std;
#define ll long long
set<ll>ans;//自动去重
bool check(ll n,ll a,ll b)
{int num[10]={0};string sn=to_string(n);string sa=to_string(a);string sb=to_string(b);for(int i=0;i<sn.size();i++){num[sn[i]-'0']++;}for(int i=0;i<sa.size();i++){num[sa[i]-'0']--;}for(int i=0;i<sb.size();i++){num[sb[i]-'0']--;}for(int i=0;i<=9;i++){if(num[i])return false;//通过相减}return true;
}
int main()
{for(ll i=1;i<=1000000;i++){ll kk=i*i;if(kk>1000000)break;if(check(kk,i,i))ans.insert(kk);for(ll j=i+1;j<=1000000;j++){kk=i*j;if(kk>1000000)break;if(check(kk,i,j))ans.insert(kk);}}cout<<ans.size()<<endl;return 0;
}

13.X质数(线性筛,二进制)

#include <iostream>
#include <string>
using namespace std;
const int N=1e6;
int idx=0;
int prime[N];
int st[N];
int ans=0;
void get()
{st[0]=st[1]=1;for(int i=2;i<=N;i++){if(!st[i])prime[++idx]=i;for(int j=1;j<=idx&&i*prime[j]<=N;j++)//从1开始{st[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
bool check(int x) {string num = to_string(x);int n = num.size();// n个数字,每个数字算不算进去两种选择for (int i = 0; i < (1 << n); ++i) { //n位数,有2^n种情况int cur = 0;for (int j = 0; j < n; ++j) { // 每种情况为一个二进制值if ((i >> j) & 1) cur = cur * 10 + num[j] - '0';}if (!st[cur]) return true;}return false;
}
int main()
{get();for(int i=1;i<=N;i++){if(check(i))ans++;}cout<<ans<<endl;return 0;
}

这篇关于蓝桥杯2024国赛--备赛刷题题单的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1019679

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

免费也能高质量!2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议,有时候说的内容比较广需要引用多份的数据,我记录起来有一定难度,所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职,这款录屏工具在录屏模式上提供了多种选项,可以选择屏幕录制、窗口

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

轻松录制每一刻:探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧?现在的市面上有不少免费录屏的软件了。别看如软件是免费的,它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单,打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦

梳理2024年,螺丝钉们爱用的3款剪辑软件

这年头,视频到处都是,就跟天上的星星一样数不清。不管你是公司里的新面孔,还是职场上的老狐狸,学会怎么剪视频,就好比找到了赢的秘诀。不管是给上司汇报工作,展示你的产品,还是自己搞点小视频记录生活,只要是剪辑得漂亮,肯定能一下子吸引大家的目光,让人记得你。咱们今天就来侃侃现在超火的三款视频剪辑工具,尤其是PR剪辑,你肯定听说过,这货在剪辑界可是大名鼎鼎,用它剪视频,既专业又麻利。 NO1. 福昕轻松