【蓝桥杯备赛】2021年第十二届蓝桥杯省赛第一场(5月9日)真题C++ B组 未完待续……
文章目录题目结构第一题 空间第二题 卡片第三题 直线第四题 货物摆放第五题 路径第六题 时间显示题目结构项目题型分值题型第一题结果填空5空间(单位换算)第二题结果填空5卡片(模拟)第三题结果填空10直线(数学)第四题结果填空10货物摆放(数学)第五题结果填空15路径(最短路径)第六题程序设计15时间显示(时间换算/取位数)第七题程序设计20砝码称重(DP)第八题程序设计20杨辉三角第九
·
题目结构
项目 | 题型 | 分值 | 题型 |
---|---|---|---|
第一题 | 结果填空 | 5 | 空间(单位换算) |
第二题 | 结果填空 | 5 | 卡片(模拟) |
第三题 | 结果填空 | 10 | 直线(数学) |
第四题 | 结果填空 | 10 | 货物摆放(数学) |
第五题 | 结果填空 | 15 | 路径(最短路径) |
第六题 | 程序设计 | 15 | 时间显示(时间换算/取位数) |
第七题 | 程序设计 | 20 | 砝码称重(DP) |
第八题 | 程序设计 | 20 | 杨辉三角 (二分答案) |
第九题 | 程序设计 | 25 | 双向排序 |
第十题 | 程序设计 | 25 | 括号序列 |
第一题 空间
小蓝准备用 256MB 的内存空间开一个数组,数组的每个元素都是 32 位 二进制整数,如果不考虑程序占用的空间和维护内存需要的辅助空间,请问 256MB 的空间可以存储多少个 32 位二进制整数?
进值转换:1MB=1024KB 1KB=1024B 1B=8位
cout<<256*1024*1024/4<<endl;
第二题 卡片
- 用数组计数,从2021减
- 枚举取位数
- excel+word检验
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int cnt[10]={0};
int main(){
for(int i=0;i<=9;i++) cnt[i]=2021;
for(int i=1;;i++){
int t=i;
while(t){
if(cnt[t%10]==0) {
cout<<i-1;
return 0;
};
cnt[t%10]--;
t/=10;
}
}
return 0;
}
第三题 直线
- 确定直线用两点式:(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0
- 枚举所有的直线
- 使用set去重
- pair存放坐标
#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
vector<PII> v;
set<PIII> s;
int x,y;
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
cin>>x>>y;
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){
v.push_back({i,j});
}
}
for(int i=0;i<v.size();i++){
for(int j=i+1;j<v.size();j++){
int x1=v[i].first;
int y1=v[i].second;
int x2=v[j].first;
int y2=v[j].second;
int A=y1-y2,B=x2-x1,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;
//答案40257
}
第四题 货物摆放
- 找到因子数组(平方循环技巧)
- 遍历因子数组判断乘积是否为n并计数
#include<iostream>
using namespace std;
typedef long long ll;
ll a[5000];
ll len=0,cnt=0;
int main()
{
ll n=2021041820210418;
for(ll i=1;i*i<=n;i++){
if(n%i==0){
a[len++]=i;
if(i!=n/i){
a[len++]=n/i;
}
}
}
for(ll i=0;i<len;i++){
for(ll j=0;j<len;j++){
for(ll k=0;k<len;k++){
if(a[i]*a[j]*a[k]==n){
cnt++;
}
}
}
}
cout<<cnt<<endl;
} // namespace std;
第五题 路径
- 首先确定使用弗洛伊德算法求解最短路径(三个循环)
- 使用邻接矩阵构造图
- 弗洛伊德求最短路径得到结果
- 注意邻接矩阵的数据类型应该为long long 因为无穷大设置的为1e18
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 1e18;
ll mp[3000][3000];
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}
void Floyd(int n){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
}
}
}
int main()
{
int n=2021;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) mp[i][j]=0;
else if(abs(i-j)<=21) mp[i][j]=mp[j][i]=i*j/gcd(i,j);
else mp[i][j]=mp[j][i]=INF;
}
}
Floyd(n);
cout<<mp[1][2021]<<endl;
return 0;
} // namespace std;
答案:10266837
第六题 时间显示
所有数据不超过10^18
#include <iostream>
#include <stdio.h>
using namespace std;
long long t,h,m,s,ms;
int main()
{
cin>>t;
t=t/1000;
h=t/3600%24;
m=t/60%60;
s=t%60;
printf("%02lld:%02lld:%02lld",h,m,s);
return 0;
}
第八题 杨辉三角
部分得分(20%)
- 把杨辉三角存在一个数组,后用二分法找
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 10100;
LL dp[N][N];//用来存入杨辉三角形的每一个数
LL sk[N];//记入每个数是第几个数
int s = 1;
int n;
int main() {
cin >> n;
dp[0][0] = 1;
for (int i = 1; i <= 50; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];//杨辉三角形的规律
sk[s++] = dp[i][j];
}
}
for (int i = 1; i <= 10000; i++) {
if (sk[i] == n) {//第一次相等即为该数第一次出现的位置
cout << i;
break;
}
}
return 0;
}
正解
- 发现杨辉三角是对称的,所以可只找左半部分,而查找的有效部分是C2i,i,即行数为列数的二倍
- 题目数据范围在1e10,而C34,17大于1e10,所以只需要查找前十六列,从十六列往前查找
- 使用二分查找,设列为i,那么左边界为2i,右边界只要比n大即可,可取max(n,2i)
#include <iostream>
#define int long long
using namespace std;
int n;
int C(int a , int b){
int res = 1;
for(int i = a , j = 1 ; j <= b ; i -- , j ++){
res = res * i / j;
if(res > n) return res;
}
return res;
}
signed main()
{
cin >> n;
for(int k = 16 ; ~k ; k --){
int l = 2 * k , r = max(n , l) , res = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(C(mid , k) >= n) res = mid , r = mid - 1;
else l = mid + 1;
}
if(C(res , k) == n) return cout << (res + 1) * res / 2 + k + 1 << '\n' , 0;
}
return 0;
}
组合数
long long C(int n,int m){
if(m<n-m) m=n-m;
long long ans=1;
for(int i=m+1;i<=n;i++) ans*=i;
for(int i=1;i<=n-m;i++) ans/=i;
return ans;
}
排列数
long long fact(int n){
long long ans=1;
for(int i=1;i<=n;i++){
ans*=i;
}
return ans;
}
更多推荐
所有评论(0)