2021年第十二届C/C++ B组蓝桥杯省赛真题
发布时间
阅读量：
阅读量
2021年第十二届C/C++ B组蓝桥杯省赛真题
真 题
第一部分
空间 相关 问 题
卡片 类 问 题
直线 问 题
货物 摆放 相关 问 题
路径 相关 问 题
时间 显示 相关 问 题
砝码 称重 相关 问 题
杨辉 三角 形 相关 问 题
双向 排序 相关 问 题
括号 序列 相关 问 题
解答 题目
真题
这是我最早接触的蓝桥题目，在初期对蓝桥独特的解题思路并不太适应这篇题解的质量稍显一般见谅
第一题：空间
题目描述
小蓝计划利用256MB的存储容量创建一个数组，并将每个元素设置为32位二进制整数；那么，在不考虑程序占用的空间和其他辅助内存管理需求的情况下，请问该存储容量最多可以容纳多少个这样的32位二进制整数？
第二题：卡片
题目描述
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少？
提示：建议使用计算机编程解决问题。
第三题：直线
在平面直角坐标系中，在二维空间内任意选取两个不同点即可唯一地决定一条直线。
当存在多个共线点时，则这些任意两点所确定的直线必然是相同的。
考虑平面上由所有整数坐标构成的网格点集合：{(x, y) | x为0到1之间的整数（含），y为0到2之间的整数（含）}。
这样的网格点集合一共能定义出11条独特的直线。
类似地，在更大的网格规模下，
即当x取值范围扩大至0到19（含），y取值范围扩大至0到20（含）时，
我们面对的是一个包含20×21个整数坐标的更大网格。
那么这样的网格点总共能确定多少条独特的直线呢？
第四题：货物摆放
题目描述
第五题：路径
题目描述
第六题：时间显示
输入格式
第七题：砝码称重
样例输入
题目描述
输入格式
输出格式
样例输入
样例输出
样例说明
评测用例规模与约定
第八题：杨辉三角形
题目描述
该图形被视为杨辉三角形的经典实例：
当我们按照从上至下、由左及右的方式将所有数字依次排列成一列时...
第0行： 1
第1行： 1 1
第2行： 1 2 1
第3行： 1 3 3 1
第4行： 1 4 6 4 1输入格式
样例输入
第九题：双向排序
输入格式
第十题：括号序列
题目描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
题解
第一题：空间
分析
计算机基础知识
256 1024 1024*8/32=67108864
代码
ans 67108864
c第二题：卡片
分析
枚举
代码
class Solution {
public:
int fun(int x){
vector<int> re(10,x);
int n = 1;
while (1){
if (!jian(n, re)){
return n-1;
}
n++;
}
return -1;
}
bool jian(int n,vector<int>& re){
while (n){
if(--re[n % 10]<0)return false;
n /= 10;
}
return true;
}
};
ans： 3181
c
第三题：直线
分析
两点式直线方程：
(y1-y2) * x +(x2-x1) * y +( x1 * y2 - x2 * y1)=0
思路：先存储所有的坐标 ，遍历所有的坐标组获得直线Ax+By+C=0的A,B,C并使用gcd约分最后再利用set去重。
摘自这里
代码
#include<iostream>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
set<PIII> s;
vector<PII>vec;
int gcd(int a, int b){
if (b == 0) return a;
return gcd(b, a % b);
}
int main(){
int x, y;
cin >> x >> y;
for (int i = 0; i < x; i++)
for (int j = 0; j < y; j++)
vec.push_back({ i, j });
for (int i = 0; i < vec.size(); i++){
for (int j = i + 1; j < vec.size(); j++){
int x1 = vec[i].first, y1 = vec[i].second;
int x2 = vec[j].first, y2 = vec[j].second;
int A = x2 - x1, B = y1 - y2, C = x1*y2 - x2*y1;
int gcdd = gcd(gcd(A, B), C);
s.insert({ { B / gcdd, A / gcdd }, C / gcdd });
}
}
cout << s.size();
return 0;
}
ans 40257
c
第四题：货物摆放
分析
先找出因子，再将枚举因子
代码
ans： 2430
class Solution {
public:
int fun(long long n){
int ans = 0;
vector<long long> re;
for (int i = 1; i <= sqrt(n); i++)
{
if (n % i == 0)
{
re.push_back(i);
re.push_back(n / i);
}
}
int l = re.size();
for (int i = 0; i < l; i++)
for (int j = 0; j < l; j++)
for (int k = 0; k < l; k++)
{
if (re[i] * re[j] * re[k] == n)
ans++;
}
return ans;
}
};
c
第五题：路径
分析
动态规划
dp dp[i]代表从起点至第i个节点所需的最短路径长度 对于每一个特定的i值 需要遍历所有可能的可达点 在这些可到达点中寻找使总路径长度最小的那个点 最终结果即为dp[2021]的值
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//最小公倍数
int gcd(int a, int b){
return a == 0 ? b : gcd(b%a, a);
}
//最大公因子
int lcm(int a, int b){
return a*b / gcd(a, b);
}
int main(){
vector<int> dp(2030);
dp[1] = 0;
for (int i = 2; i <= 2021; i++){
dp[i] = dp[i - 1] + (i - 1)*i;
for (int j = 1; j <= 21&&i-j>0; j++)
dp[i] = min(dp[i], dp[i - j] + lcm(i - j, i));
}
cout << dp[2021] << endl;
return 0;
}
ans :10266837
c
第六题：时间显示
分析
模拟
1秒 == 1000毫秒
代码
试题F 时间显示
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
void fun(long long n){
long long oneDaySS = 24 * 60 * 60 * 1000;
int HH, MM, SS;
n %= oneDaySS;
n /= 1000;//s
SS = n % 60;
n /= 60;//m
MM = n % 60;
n /= 60;//h
HH = n;
if (HH < 10){
cout << '0' << HH;
}
else{
cout << HH;
}
cout << ':';
if (MM < 10){
cout << '0' << MM;
}
else{
cout << MM;
}
cout << ':';
if (SS < 10){
cout << '0' << SS;
}
else{
cout << SS;
}
cout << endl;
}
int main(){
long long n;
cin >> n;
fun(n);
return 0;
}
c
第七题：砝码称重
分析
动态规划
dp[i][j]表示前 i 个砝码能否称出 j 的重量
代码
#include <iostream>
#define N 102
#define MAX_WEIGHT 100005
using namespace std;
int n, m, k, w[N], sum_weight, ans;
bool dp[N][MAX_WEIGHT << 2];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
sum_weight += w[i];
}
dp[0][sum_weight * 2] = true;
for (int i = 1; i <= n; ++i) {
for (int j = sum_weight; j <= sum_weight * 3; ++j) {
dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - w[i]] || dp[i - 1][j + w[i]];
}
}
for (int i = 1; i <= sum_weight; ++i) {
if (dp[n][sum_weight + i] ) {
++ans;
}
}
cout << ans;
return 0;
}
c
第八题：杨辉三角形
分析
摘自
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL C(int a, int b) //计算C（a，b）
{
LL res = 1;
for(int i = a, j = 1; j <= b; i --, j ++)
{
res = res * i / j;
if(res > n)
return res; // 大于n已无意义，且防止爆LL
}
return res;
}
bool check(int k)
{
// 二分该斜行,找到大于等于该值的第一个数
// 左边界2k，右边界为max(l, n)取二者最大，避免右边界小于左边界
int l = 2 * k, r = max(n,l);
while(l < r)
{
int mid = l + r >> 1;
if(C(mid, k) >= n) r = mid;
else l = mid + 1;
}
if(C(r, k) != n)
return false;
cout << 1ll*(r + 1) * r / 2 + k + 1 << endl;
return true;
}
int main()
{
cin >> n;
// 从第16斜行枚举
for(int i = 16; ; i--)
if(check(i))
break;
return 0;
}
c
第九题：双向排序
分析
很好的思路啊，自己怎么也没想到可以先处理操作数，就想到了连续的情况可以取最大，当时我也觉得应该有一部分是固定的，但是我发现如果边读取边操作的话是没有固定地方的！tql
摘自
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII stk[N];
int ans[N];
int main()
{
scanf("%d%d", &n, &m);
int top = 0;
while (m -- )
{
int p, q;
scanf("%d%d", &p, &q);
if (!p)//操作1
{
while (top && stk[top].x == 0)
q = max(q, stk[top -- ].y);//出现连续的操作1，我们取最大
while (top >= 2 && stk[top - 1].y <= q)
//如果当前的操作1比上一次的操作1范围大，则将上一次操作1和操作2删除
top -= 2;
stk[ ++ top] = {0, q};//存本次最佳操作
}
else if (top)//操作2 &&且操作1已经进行过（操作二第一个用没效果）
{
while (top && stk[top].x == 1) q = min(q, stk[top -- ].y);
while (top >= 2 && stk[top - 1].y >= q) top -= 2;
stk[ ++ top] = {1, q};
}
}
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++ )
{
if (stk[i].x == 0)//如果是操作1
while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;//移动r值 ，并赋值
else
while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;
if (l > r) break;
}
if (top % 2)
while (l <= r) ans[l ++ ] = k -- ;
else
while (l <= r) ans[r -- ] = k -- ;
for (int i = 1; i <= n; i ++ )
printf("%d ", ans[i]);
return 0;
}
c
第十题：括号序列
分析
该动态规划（DP）问题的定义具有一定的创新性。这一思路展示了其独特的优势！
进一步地，在第i个元素的基础上考虑比它多j个的情况，则可以得出相应的结论。
摘自
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5000 + 5;
const int mod = 1e9 + 7;
int n;
int dp[maxn][maxn];
string a ;
ll calc ()
{
memset(dp , 0 , sizeof dp);
dp[0][0] = 1;
for (int i = 1 ; i <= n ; i++){
if (a[i - 1] == '('){
for (int j = 1 ; j <= n ; j++)
dp[i][j] = dp[i - 1][j - 1];
}else {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
for (int j = 1 ; j <= n ; j++)
dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % mod;
}
}
for (int i = 0 ; i <= n ; i++) if (dp[n][i]) return dp[n][i];
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin >> a;
n = a.size();
ll l = calc();
reverse(a.begin() , a.end());
for (auto &g : a) if (g == '(') g = ')'; else g = '(';
ll r = calc();
cout << l * r % mod << endl;
return 0;
}
c
全部评论 (0)
还没有任何评论哟~