第1题
C++中，bool类型的变量占用字节数为（ ）。
A. 1
B. 2
C. 3
D. 4
答案：A
第2题
以下关于C++结构体的说法，正确的是（ ）。
A. 结构体中只能包含成员变量，不能包括成员函数
B. 结构体不能从另一个结构体继承
C. 结构体里面可以包含静态成员变量
D. 结构体里面不能包含构造函数
答案：C
解析：C++中的struct对C语言中的struct进行了扩充，可以包含成员函数、可以继承、可以实现多态，与class相比，最本质的区别是访问控制权限不同！
第3题
设只含根节点的二叉树高度为1，共有62个节点的完全二叉树的高度为（ ）。
A. 4
B. 5
C. 6
D. 7
答案：C
第4题
以下关于数组的说法，不正确的是（ ）。
A. 数组中所有元素的类型都必须相同
B. 数组中各个元素在内存中是顺序存放的
C. 数组最后一个元素的索引是数组的长度
D. 数组名的第一个字符可以是下划线
答案：C
第5题
执行以下代码，输出的结果是（ ）。
#include <iostream>
using namespace std;
int f(int k){
if(k == 1)
return 3;
return 2 * f(k - 1) + 1;
}
int main() {
int n = 6;
cout << f(n);
return 0;
}A. 127
B. 97
C. 63
D. 126
答案：A
第1题 特殊运算符
int n;
cin >> n;
cout << (n - n / 10) << endl;第2题 四叶玫瑰数
解析：先判断是否是四位数，如果是四位数，再进行各个位数字分离，这个部分也可以封装为一个函数，满足条件返回true。
#include <iostream>
#include <cmath>
using namespace std;
bool check(int n){
if(n < 1000 || n > 9999)
return false;
int nn = n;
int sum = 0;
while(n){
sum += pow(n % 10, 4);
n /= 10;
}
return nn == sum;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = n; i <= m; i++)
if(check(i))
cout << i << " ";
return 0;
}第3题 质因数的个数
解析：由于数据范围很大，需要使用O(n)的算法，借助于线性筛，使用cnt数组存储i的质因数个数，如果i是质数，那么cnt[i]=1。否则cnt[i * v[j]] = cnt[i] + 1。因为v[j]是一个质数，i*v[j]质因数的个数在i的质因数个数基础之上加1。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e7 + 10;
int n, m;
int cnt[N];
bool book[N];
vector<int> v;
int res = 0;
void work(int n){
for(int i = 2; i <= n; i++){
if(!book[i]) {
v.push_back(i);
cnt[i] = 1;
}
for(int j = 0; v[j] <= n / i; j++){
book[v[j] * i] = true;
cnt[i * v[j]] = cnt[i] + 1;
if(i % v[j] == 0) break;
}
}
}
int main() {
cin >> n >> m;
work(m);
for(int i = n; i <= m; i++)
res = max(res, cnt[i]);
cout << res << endl;
return 0;
}第4题 最大矩形纸片
解析：从第i列开始，向左右两侧进行，找到第一个小于第i列高度的列。但是时间复杂度较高。需要用单调栈进行优化。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
int h[N], L[N], R[N], q[N];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
h[0] = h[n + 1] = -1;
int tt = 0;
q[0] = 0;
// 找到左边第一个比我小的 单调递增栈
for(int i = 1; i <= n; i++){
while(h[i] <= h[q[tt]]) tt--;
L[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n + 1;
// 找到右边第一个比我小的
for(int i = n; i >= 1; i--){
while(h[i] <= h[q[tt]]) tt--;
R[i] = q[tt];
q[++tt] = i;
}
LL res = 0;
for(int i = 1; i <= n; i++)
res = max(res, (LL)h[i] * (R[i] - L[i] - 1));
cout << res << endl;
return 0;
}第5题 数字游戏
#include <iostream>
#include <map>
using namespace std;
int n;
int cnt = 0;
map<int, int> mp;
int main() {
cin >> n;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
mp[x]++;
}
while(mp.size() >= 3){
if(cnt % 2 == 0){
auto t = mp.begin();
(t->second)--;
(next(t)->second)++;
if(t->second == 0)
mp.erase(t);
}
else{
auto t = prev(mp.end());
(t->second)--;
(prev(t)->second)++;
if(t->second == 0)
mp.erase(t);
}
cnt++;
}
int maxv = prev(mp.end())->first;
int minv = mp.begin()->first;
cout << cnt << " " << minv << " " << maxv << endl;
return 0;
}第6题 活动人数
解析：深搜+dp。
状态表示：f[N][2]。
f[i][0]表示不选i时的最大价值，f[i][1]表示选i时的最大价值。
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n;
int root;
int a[N], f[N][2];
vector<int> h[N];
void dfs(int u){
f[u][1] = a[u];
for(auto v: h[u]){
dfs(v);
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++){
int f, s, c;
cin >> f >> s >> c;
a[s] = c;
if(f)
h[f].push_back(s);
else
root = s;
}
dfs(root);
cout << max(f[root][0], f[root][1]);
return 0;
}联系客服
