2023-09-10 腾讯后台开发笔试

牛牛的服务器怎么炸了啊。。。。

最后的结果 100, 未知, 100, 100, 未知

1. 二叉树dfs找节点（100分）
2. multiset维护中位数（没出结果）

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<i64> a(n), b(n - 1);
    std::multiset<i64> S;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        S.insert(a[i]);
    }
    for (int i = 0; i < n - 1; i++) {
        std::cin >> b[i];
        b[i]--;
    }

    for (int i = 0; i < n; i++) {
        auto mid = S.begin();
        std::advance(mid, (n - i) / 2);
        std::cout << (*mid + *prev(mid, (1 - (n - i) % 2))) / 2;
        if ((*mid + *prev(mid, (1 - (n - i) % 2))) % 2) std::cout << ".5";
        std::cout << " \n"[i == n - 1];
        if (i < n - 1) {
            S.erase(S.find(a[b[i]]));
        }
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

3. 贪心，先找最大，然后找最小（100分）

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;
    std::vector<i64> a(n);
    for (int i = 0; i < n; i++) {
    	std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    i64 ans = 0, cur = 0;
    int i = 0, j = n - 1;
    int flag = 0;
    while (i <= j) {
    	if (!flag) {
    		ans += a[j] - cur;
    		cur = a[j];
    		j--;
    	} else {
    		cur = a[i];
    		i++;
    	}
    	flag ^= 1;
    }

    std::cout << ans << "\n";
    
    return 0;
}

4. 结论题，可能的序列有个，可能的校验和有种，需要找到不同与S的个数，答案的就是 (100分)

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1e9 + 7;

i64 power(i64 a, i64 b) {
    i64 res = 1;
    for (; b; b /= 2, a = a * a % P) {
        if (b % 2) {
            res = res * a % P;
        }
    }
    return res % P;
}

void solve() {
	i64 n, m;
	std::cin >> n >> m;
	std::cout << (power(2, n - m) - 1 + P) % P << "\n";
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int T;
    std::cin >> T;
    while (T--) {
    	solve();
    }
    
    return 0;
}

5. 背包，维护最大能消去的dp状态(没出结果)

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, k;
    std::cin >> n >> k;
    std::vector<i64> dp(k + 10, 0);
    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        std::vector<i64> v;
        v.push_back(0);

    	int x;
    	std::cin >> x;
        sum += x;

        while (x) {
            v.push_back(v.back() + (1 << __builtin_ctz(x)));
            x ^= (1 << __builtin_ctz(x));
        }

        auto tmp = dp;

        for (int j = 0; j <= v.size(); j++) {
            for (int u = 0; u <= k; u++) {
                if (u >= j) tmp[u] = std::max(tmp[u], dp[u - j] + v[j]);
            }
        }
        dp = tmp;
    }

    std::cout << std::max(0ll, sum - dp[k]) << "\n";

    
    return 0;
}