序
比赛时长: 四个小时
比赛规则:
蓝桥杯比赛跟天梯赛、ACM还不太一样,比赛中提交的答案并没有反馈机制,也就是说你提交了答案以后,自己并不知道是对是错,就像考试一样,只有交了卷,成绩下来以后才能知道自己的奖项。
满分150
T1-T5答案提交共45分,分值分别是5,5,10,10,15
T6-T10为程序提交共105分,分值分别是15,20,20,25,25
T6-T10开放补题
提交链接:https://lx.lanqiao.cn/problemset.page
搜索【第十二届】【省赛】【B组】
一般来说,蓝桥杯=暴力杯
前六题都做对共60分,后面四题嫖一半45分,105以上感觉一般能合格。
T1,T2很裸的暴力
T3,T4需要set优化或者思考一下枚举方案的暴力
T5,T6很裸的暴力,但是要能写一点点基本的代码,题目细节看仔细
T7,T8背包dp与找规律递推。很裸的暴力可以打一半。
T9,T10一般是思维题或dp。稍微思考一下的很裸的暴力可以打一半。
T1-T5
T1 空间
- 小蓝准备用256MB 的内存空间开一个数组,数组的每个元素都是32 位
二进制整数,如果不考虑程序占用的空间和维护内存需要的辅助空间,请问
256MB 的空间可以存储多少个32 位二进制整数? - 已知1MB=1024KB,1KB=1024B,1B=8b
- 所以答案 67108864
T2 卡片
- 小蓝有很多数字卡片,每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数,他想从 1 开始拼出正整数,每拼一个,就保存起来,卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。
例如,当小蓝有 30 张卡片,其中 0 到 9 各 3张,则小蓝可以拼出 1 到 10, 但是拼 11 时卡片 1 已经只有一张了,不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各2021 张,共 20210 张,请问小蓝可以从 1 拼到多少? 提示:建议使用计算机编程解决问题。 - 创个数组表示卡片张数,枚举一下就行
- 3181
T3 直线
- 在平面直角坐标系中,两点可以确定一条直线。如果有多点在一条直线上,那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点> {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z},即横坐标是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。
给定平面上 20 × 21个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z},即横坐标是 0 到 19 (包含 0 和> 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。 - 四层for循环枚举(x1,y1)(x2,y2),根据y=kx+b和k=(y1-y2)/(x1-x2)分别得出k和b的值,注意斜率不存在的情况。依次遍历每个点,用set储存k、b的值用于查重,如果k、b不在map中,则结果加一。注意所有变量都要设为double值,不然计算就会出错。
- 47753
T4 货物摆放
-
小蓝有一个超大的仓库,可以摆放很多货物。 现在,小蓝有 n 箱货物要摆放在仓库,每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向,每箱货物的边都必须严格平行于长、宽、高。
小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上 分别堆 L、W、H 的货物,满足 n = L × W × H。给定n,请问有多少种堆放货物的方案满足要求。 例如,当 n = 4 时,有以下 6 种方案:1×1×4、1×2×2、1×4×1、2×1×2、 2× 2 × 1、4 × 1 × 1。
请问,当 n = 2021041820210418 (注意有 16 位数字)时,总共有多少种方案? -
求n=三个数相乘有多少种方案,16位不超过ll,可以暴力。
考虑优化,长宽高和面积显然是n的因数。对于该性质,那么枚举长宽高的时候只需要枚举n的因数即可(虽然枚举n的所有因数也会超时),但是可以set一下,n/a也是n的因数,那么复杂度就降低了。
再遍历这个集合**(作为一条边a),可以用n/a计算出另外两条边相乘的面积S,另外两条边显然也在初始集合之内,且是S的因数,所以再枚举S的因数(即第二条边)**,就可以计算出第三条边,统计答案,就不会超时了。 -
2430
#include<bits/stdc++.h> using namespace std; typedef long long LL; int main(){ LL n = 2021041820210418; set<LL>se; for(LL a = 1; a <= n; a++){//枚举n的因数 if(n%a==0){ if(se.find(a)!=se.end())break; //存在重复值就结束 se.insert(a); se.insert(n/a); //n/a优化 } } LL res = 0; for(LL a : se){//枚举所有可行的第一条边 LL s = n/a; set<LL>se2; for(LL b = 1; b <= s; b++){//枚举S的因数(枚举第二条边) if(s%b==0){ //可以计算出第三条边h=s/b if(se2.find(b)!=se2.end())break; se2.insert(b); se2.insert(s/b); if(b==s/b)res++; //b和h相同 else res+=2; //212,221是不同方案 } } } cout<<res<<"\n"; return 0; }
T5 路径
-
小蓝学习了最短路径之后特别高兴,他定义了一个特别的图,希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成,依次编号 1 至2021。 对于两个不同的结点 a, b,如果 a 和 b 的差的绝对值大于 21,则两个结点 之间没有边相连;如果 a 和 b的差的绝对值小于等于 21,则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如:结点 1 和结点 23之间没有边相连;结点 3 和结点 24 之间有一条无 向边,长度为 24;结点 15 和结点 25 之间有一条无向边,长度为 75。
请计算,结点 1 和结点 2021 之间的最短路径长度是多少。 提示:建议使用计算机编程解决问题。 -
暴力建图跑Dijkstra即可,板子题毫无思维含量,仔细点别写错了就行
-
10266837
#include<bits/stdc++.h> using namespace std; typedef long long LL; int gcd(int a, int b){ return !b ? a: gcd(b,a%b); } const int maxn = 2050; int e[maxn][maxn]; int dist[maxn], vis[maxn]; int main(){ //建图 memset(e,0x3f,sizeof(e)); for(int i = 1; i <= 2021; i++)e[i][i]= 0; int n = 2021; for(int i = 1; i <= 2021; i++){ for(int j = 1; j <= 2021; j++){ if(abs(i-j)<=21){ e[i][j] = e[j][i] = i/gcd(i,j)*j; } } } //Dijkstra memset(dist,0x3f,sizeof(dist)); dist[1] = 0; for(int i = 1; i <= n; i++){ int v=-1, t = e[0][0]; for(int j = 1; j <= n; j++){ if(!vis[j] && dist[j]<t){ t = dist[j]; v = j; } } if(v==-1)break; vis[v] = 1; //dist[v] = t; for(int j = 1; j <= n; j++){ if(dist[j]>dist[v]+e[v][j]){ dist[j] = dist[v]+e[v][j]; } } } //cout<<e[0][0]<<"\n"; cout<<dist[2021]; return 0; }
T6-T10
T6 时间显示
-
小蓝要和朋友合作开发一个时间显示的网站。在服务器上,朋友已经获取了当前的时间,用一个整数表示,值为从 1970 年 1 月 1 日00:00:00 到当前时刻经过的毫秒数。
现在,小蓝要在客户端显示出这个时间。小蓝不用显示出年月日,只需要显示出时分秒即可,毫秒也不用显示,直接舍去即可。
给定一个用整数表示的时间,请将这个时间对应的时分秒输出。 -
不用显示年月日,只要时分秒,所以不难想到很傻比的做法是对获得的时间戳每次减去60累加即可,注意开longlong,非常简单。(暴力也能过哦)
然后优化一下很显然的做法是,直接取模。
需要注意题目给的是毫秒,不是秒!!!。#include<bits/stdc++.h> using namespace std; typedef long long LL; int main(){ LL ms; cin>>ms; LL h= 0, m=0, s=ms/1000; while(s >= 60){ s -= 60; m++; if(m==60){ m = 0; h++; if(h==24)h = 0; } } printf("%02d:%02d:%02d",h,m,s); return 0; } #include<bits/stdc++.h> using namespace std; typedef long long LL; int main(){ LL ms; cin>>ms; LL s = ms/1000; LL h = (s/3600)%24; LL m = (s/60)%60; s %= 60; printf("%02d:%02d:%02d",h,m,s); return 0; }
T7 砝码称重
- 你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量?注意砝码可以放在天平两边。
- 放左边为正数,放右边为负数,不放为0,每种砝码三种选择。本质为有限制选择的背包问题。
记f[i][j]表示,只从前i个物品中选,总重量为j的所有方案的是否存在。
转移的时候,对于第i个物品,可以放左边+w[i],放右边-w[i],以及不放。
最后答案就是遍历总重量m,累加f[n][i]即可。#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 2e5+10,maxx=1e5; int w[maxn]; int f[110][maxn]; int main(){ int n, m=0; cin>>n; for(int i = 1; i <= n; i++){ cin>>w[i]; m+=w[i]; } f[0][0+maxx] = 1; //前0个物品中选,重量为0的方案数 for(int i = 1; i <= n; i++){ for(int j = -m; j <= m; j++){ f[i][j+maxx] = f[i-1][j+maxx];//不放 if(j-w[i]>=-m)f[i][j+maxx] |= f[i-1][j-w[i]+maxx];//放左边 if(j+w[i]<=m)f[i][j+maxx] |= f[i-1][j+w[i]+maxx];//放右边 } } int res = 0; for(int i = 1; i <= m; i++){ if(f[n][i+maxx])res++; } cout<<res<<"\n"; return 0; }
T8 杨辉三角形
- 如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列: 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
给定一个正整数 N,请你输出数列中第一次出现 N 是在第几个数? - 滚动数组暴力出杨辉三角,特判第几个数出现,对于前面的部分可以打表.
//TLE-30分 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1010; LL f[maxn][maxn]; int main(){ LL n; cin>>n; f[1][1] = 1; f[2][1] = f[2][2] = 1; LL cnt = 3; for(int i = 3; ; i++){ for(int j = 1; j <= i; j++){ f[i][j] = f[i-1][j-1]+f[i-1][j]; cnt++; if(f[i][j]==n){ cout<<cnt<<"\n"; return 0; } } } return 0; } //TLE-40分 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e7+10; LL f[2][maxn]; int main(){ LL n; cin>>n; f[1][1] = 1; f[0][1] = f[0][2] = 1;//2%2==0 LL cnt = 3; for(int i = 3; ; i++){ for(int j = 1; j <= i; j++){ f[(i+2)%2][j] = f[(i-1+2)%2][j-1]+f[(i-1+2)%2][j]; cnt++; if(f[i%2][j]==n){ cout<<cnt<<"\n"; return 0; } } } return 0; }
T9 双向排序
-
给定序列 (a1, a2, · · · , an) = (1, 2, · · · , n),即 ai = i。
小蓝将对这个序列进行 m次操作,每次可能是将 a1, a2, · · · , aqi 降序排列,或者将 aqi, aqi+1, · · · , an升序排列。
请求出操作完成后的序列 -
来个简单粗暴的写法,就是对于每个输入均以sort处理,垃圾数据表示可以给你60分hhh。
//TLE-60分 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5+10; int a[maxn]; bool cmp(int x, int y){ return x>y; } int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++)a[i] = i; for(int i = 1; i <= m; i++){ int p, q; cin>>p>>q; if(p==0)sort(a+1,a+q+1,cmp); else sort(a+q,a+n+1); } for(int i = 1; i <= n; i++){ cout<<a[i]<<" "; } return 0; }
-
一共两个操作(1-n)的排列,将某前缀降序排列,将某后缀升序。共m个操作。
(1)我们本来输入的序列就是升序的,第一个有效操作必然是降序操作
(2)对于连续的降序或升序操作,我们保留最长的一个操作即可。有效操作必然是左右交替的
(3)当左侧区间长度大于上一个对左端操作时,含重复操作的区间了,我们只需要操作后一个(长度范围更大的)左区间操作即可。//RE-60分 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5+10; int a[maxn]; int main(){ int n, m; cin>>n>>m; //化简操作 stack<pair<int,int> >st; for(int i = 1; i <= m; i++){ int p, q; cin>>p>>q; if(p==0){//左边前缀降序 //删除前面比当前操作小的左操作 while(!st.empty() && st.top().first==0){ q = max(q, st.top().second); st.pop(); } //删掉前边比当前操作小的左端操作及其对应的右端操作 if(st.size()>=2){ pair<int,int> t = st.top(); st.pop(); if(st.top().second>q)st.push(t); else{ while(st.size()>=1 && st.top().second<=q){ st.pop(); t=st.top(); if(st.size()>=1)st.pop(); } st.push(t); } } st.push(make_pair(0,q)); } else if(!st.empty()){ //右边后缀升序(不需要操作第一个右操作) while(!st.empty() && st.top().first==1){ q = min(q,st.top().second); st.pop(); } if(st.size()>=2){ pair<int,int> t = st.top(); st.pop(); if(st.top().second<q)st.push(t); else{ while(st.size()>=1 && st.top().second>=q){ st.pop(); t=st.top(); if(st.size()>=1)st.pop(); } st.push(t); } } st.push(make_pair(1,q)); } } //处理操作 vector<pair<int,int> >vc; while(st.size()){vc.push_back(st.top()); st.pop(); } reverse(vc.begin(),vc.end()); int k = n, l = 1, r = n; for(int i = 0; i < vc.size(); i++){ if(vc[i].first==0){ while(r>vc[i].second && l<=r)a[r--]=k--; }else{ while(l<vc[i].second && l<=r)a[l++]=k--; } if(l>r)break; } if(vc.size()%2==1){ while(l<=r)a[l++]=k--; }else{ while(l<=r)a[r--]=k--; } for(int i = 1; i <= n; i++){ cout<<a[i]<<" "; } return 0; }
T10 括号序列
-
给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。
例如,对于括号序列(((),只需要添加两个括号就能让其合法,有以下几 种不同的添加结果:()()()、()(())、(())()、(()()) 和((()))。文章来源:https://www.toymoban.com/news/detail-407948.html -
暴力dfs大约可以打40分,正解是类似于完全背包的dp
一个合法括号序列满足2个条件:左右括号数量相同。任何一个前缀中,左括号数量不小于右括号数。
记f[i][j] 表示只考虑前i个括号,左括号比右括号多j个的方案数。
对于转移,遇到左括号时显然有f[i][j] = f[i - 1][j - 1]。遇到有括号时,可以考虑往这个右括号前面加左括号,可以是0-j+1个(因为左括号比右括号多j个,且当前位置是右括号所以需要+1),所以f[i][j] = f[i][j-1] + f[i - 1][j+1]。文章来源地址https://www.toymoban.com/news/detail-407948.html//100分 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 5050, mod = 1e9+7; string s; int f[maxn][maxn], n; LL dp(){ memset(f,0,sizeof(f)); f[0][0] = 1; for(int i = 1; i <= n; i++){ if(s[i]=='('){ for(int j = 1; j <= n; j++){ f[i][j] = f[i-1][j-1]; } }else{ f[i][0] = (f[i-1][0]+f[i-1][1])%mod; for(int j = 1; j <= n; j++){ f[i][j] = (f[i-1][j+1]+f[i][j-1])%mod; } } } for(int i = 0; i <= n; i++){ if(f[n][i])return f[n][i]; } return -1; } int main(){ cin>>s; s="0"+s; n = s.size()-1; LL l = dp();//左括号的做法 reverse(s.begin()+1,s.end());//右括号的做法,将整个序列反转,调用函数即可 for(int i = 1; i <= n; i++){ if(s[i]=='(')s[i]=')'; else s[i]='('; } LL r = dp(); //cout<<l<<" "<<r<<"\n"; cout<<(l*r%mod)<<"\n"; return 0; }
到了这里,关于2021 第十二届蓝桥杯大赛软件赛省赛,C/C++ 大学B组题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!