单项选择题

第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;
}