笔试时间：2023年3月22日 春招实习

第一题

题目：满二叉树的染色

给定一个n层的满二叉树,一共2^n -1个节点,编号从1到2^n—1。对于编号为i(1<i<2^n-1-1)的节点,它的左儿子为2i,它的右儿子为2i＋1。有q次操作,每次操作我们选择一个节点,将该节点的子树的所有节点全部染红。每次操作后,你需要输出当前二叉树红色节点的数量。我们定义一棵二叉树是满二叉树,当且仅当每一层的节点数量都达到了最大值(即无法在这一层添加新节点)。

输入描述

第一行输入两个正整数n和q,代表二叉树的层数和操作次数。接下来的q行,每行输入一个正整数Q，代表染色的节点编号。

1<n <40

1<q<10000

1<ai<2^n

输出描述

输出q行,每行输入一个正整数,代表当前操作结束后二叉树的红色节点数量。

示例输入

2 3

2

1

3

示例输出

1

3

3

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    vector<vector<int>> merged;
    for (const vector<int>& interval : intervals) {
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = max(merged.back()[1], interval[1]);
        }
    }

    return merged;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> intervals;

    for (int i = 0; i < q; ++i) {
        int Q;
        cin >> Q;
        intervals.push_back({Q, Q});
        int l = Q, r = Q;
        while (r * 2 + 1 <= ((1 << n) - 1)) {
            l = l * 2;
            r = 2 * r + 1;
            intervals.push_back({l, r});
        }
        intervals = mergeIntervals(intervals);
        int cnt = 0;
        for (const vector<int>& interval : intervals) {
            cnt += interval[1] - interval[0] + 1;
        }
        cout << cnt << endl;
    }