C++蓝桥杯比赛历年真题–第14届蓝桥杯省赛真题
一、选择题
答案：A
解析： C++中 bool 类型与 char 类型一样，都需要1 byte。一些其他类型的占用字节数:short:2 byte，int:4byte，long long:8 byte，double:8byte，故答案为A。
答案：C
解析：
A中结构体中可以定义成员变量，也可以定义只有该结构体类型变量可调用的成员函数；
B中所谓结构体的继承特性，指的是在一个已经定义好的旧结构体的基础上，创建一个新结构体，并且新结构体可以复用旧结构体的成员和函数；
C正确，D中构造函数可以在创建结构体变量时，按照函数预设的构造规则将对应成员变量赋值，并执行其他操作。构造函数在创建结构体类型的对象时自动执行，因此无法由用户主动调用，也没有返回值，故答案为C。
答案：C
解析：由等比数列的求和可知:一个高度为 h的满二叉树含有 2h-1 个结点。
本题的 62 个结点，相当于高度为6 的满二叉树的 2^6 -1=63个结点中，再去掉最底层最右端的一个结点，故答案为C。
答案：C
解析：数组的索引是从0开始的，所以如果一个数组有n个元素，第一个元素的索引是0，最后一个元素的索引是n-1，而不是数组的长度故答案为C。
答案：A
解析：代码功能是计算一个递归函数 f(k) 的值，其中 f(1) = 3，且当 k > 1 时，f(k) = 2*f(k-1) + 1。对于 n = 6 的情况，计算过程如下：
f(6) = 2*f(5) + 1
f(5) = 2*f(4) + 1
f(4) = 2*f(3) + 1
f(3) = 2*f(2) + 1
f(2) = 2*f(1) + 1
已知 f(1) = 3
反向代入已知值得到：
f(2) = 2*3 + 1 = 7
f(3) = 2*7 + 1 = 15
f(4) = 2*15 + 1 = 31
f(5) = 2*31 + 1 = 63
f(6) = 2*63 + 1 = 127
所以，修正并执行代码后，输出的结果是 127，故答案为A。
二、编程题
【参考程序】
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
cout<<(n-n/10);
return 0;
}
【参考程序】
#include <bits/stdc++.h>
using namespace std;
bool is_T(int n){
int t=n,s=0;
for(int i=1;i<=4;i++){
s+=pow(t%10,4);
t/=10;
}
if(s==n) return true;
else return false;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=n;i<=m;i++)
if (is_T(i)) cout<<i<<" ";
return 0;
}
【参考程序】
#include <bits/stdc++.h>
using namespace std;
// 声明常量及变量
const int N = 1e7 + 5; // N表示可能的质数的上限
int primes[N], p; // primes数组保存已知的质数列表，p表示质数个数
bool sign[N]; // sign数组用来标记某个数是否是质数
int s[N]; // s数组用来记录每个数的最大质因子个数
// 埃氏筛法初始化质数表
void init_Primes(int n) {
for (int i = 2; i <= n; i++) {
if (!sign[i]) primes[p++] = i; // i是质数，加入质数表中
for (int j = 0; primes[j] <= n / i; j++) {
sign[primes[j] * i] = true; // 将i和质数表中所有不大于n/i的数的积标记为合数
if (i % primes[j] == 0) break; // 如果primes[j]是i的因子，则退出循环
}
}
}
// 计算数n的最大质因子个数
int tj_(int n) {
int tj = 0; // tj表示n的最大质因子个数
for (int i = 0; i < p; i++) { // 枚举质数表中所有质数
while (n % primes[i] == 0) { // 如果当前质数是n的因子
tj++; // 更新最大质因子个数
n /= primes[i]; // 去掉该质因子
if (n == 1) return tj; // 如果n变为了1，则说明所有质因子均被枚举完毕
}
}
}
int main() {
int n, m;
cin >> n >> m;
init_Primes(m); // 初始化质数表
int res = 0; // res表示区间内最大质因子个数
for (int i = n; i <= m; i++) { // 枚举每个数，计算其最大质因子个数，更新res
res = max(res, tj_(i));
}
cout << res; // 输出结果
return 0;
}
【参考程序】
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e6+5;
long long n,a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
long long ans=0,min_n=0; // ans 记录最大的面积，min_n 记录当前区间中的最小值
for(int i=1;i<=n;i++){
min_n=N;
for(int j=i;j<=n;j++){
min_n=min(min_n,a[j]); // 更新当前区间中的最小值
ans=max(ans,(j-i+1)*min_n); // 根据更新后的最小值来计算当前区间的面积，并记录最大值
}
}
cout<<ans; // 输出最大面积
return 0;
}
【参考程序1】
#include <bits/stdc++.h>
using namespace std;
int n,ans;
map<int,int> mp; // 定义map容器mp用于计数,map容器会根据键自动进行排序
int main()
{
cin>>n; // 数的个数
for(int i=1,x;i<=n;i++){
cin>>x;mp[x]++; // 如果x已经存在，则val+1；否则新建一个键值对(x,1)
}
// 当mp中至少存在三个不同的数字时
while(mp.size()>2){
if(ans%2==0){ // 如果ans为偶数
auto t=mp.begin(); // 获取mp中第一个键值对的迭代器
(t->second)--; // 将出现次数最少的数x减去1
(next(t)->second)++; // 将出现次数比x大的数y加上1
if(!t->second) mp.erase(t); // 如果x的出现次数为0，则从mp中删除该键值对
}else{ // 如果ans为奇数
auto t=prev(mp.end()); // 获取mp中最后一个键值对的迭代器
(t->second)--; // 将出现次数最多的数x减去1
(prev(t)->second)++; // 将出现次数比x小的数y加上1
if(!t->second) mp.erase(t); // 如果x的出现次数为0，则从mp中删除该键值对
}
ans++;
}
int max_num = prev(mp.end())->first;
int min_num = mp.begin()->first;
cout<<ans<<" "<<min_num<<" "<<max_num<<endl;
return 0;
}
【参考程序2】
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, pail[N],cnt;
list<int> ls;
int main(){
scanf("%d", &n);
for(int i = 1,x; i <= n; ++i) {
cin>>x;pail[x]++;
}
for(int i=N-1;i>=1;i--)
if(pail[i]) ls.push_back(i);
while(ls.size()>2){
auto it_f=ls.begin();
auto it_s=ls.begin();it_s++;
int id_f=*it_f,id_s=*it_s;
pail[id_f]--;
if(!pail[id_f])ls.pop_front();
pail[id_s]++;
cnt++;
if(ls.size()<=2) break;
it_f=ls.end();it_f--;it_f--;
it_s=ls.end();it_s--;
id_f=*it_f,id_s=*it_s;
pail[id_s]--;
if(!pail[id_s])ls.pop_back();
pail[id_f]++;
cnt++;
}
auto it_f=ls.begin();
auto it_s=ls.begin();it_s++;
if(ls.size()==1) cout<<cnt<<" "<<*it_f<<" "<<*it_f;
else cout<<cnt<<" "<<*it_s<<" "<<*it_f;
return 0;
}
【参考程序】
//树图+深搜+动规
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, root;//n储存所有部门的数量 root储存根节点
int a[N];// a数组表示每个节点的权值
int f[N][2]; // f[i][0/1]表示不选/选i节点时的最大价值
vector<int> G[N]; // 存储树的图结构
void dfs(int u){
f[u][1] = a[u]; // 初始化选u节点的最大价值为它本身的权值
for (int v : G[u]){//相当于for(int v=0;v<G[u].size();v++)
dfs(v); // 遍历v节点
f[u][1] += f[v][0]; // 如果选择了u节点，则不能选择v节点，所以累加 f[v][0]
f[u][0] += max(f[v][0],f[v][1]); // 如果不选择u节点，则可以选择v节点
// 所以取 f[v][0] 和 f[v][1] 的较大值累加起来
}
}
int main()
{
cin >> n;
for (int i = 1, f, s; i <= n; i++){
cin >> f >> s >> a[s]; // 输入父节点、子节点和子节点权值
if (f) G[f].push_back(s); // 如果有父亲节点则建立G[f] -> [s]的边
else root = s; // 否则当前节点为根节点
}
dfs(root);
cout << max(f[root][0],f[root][1]);
return 0;
}