腾讯秋招 2023.09.10 编程题目与题解（研发岗）

发表于 2023-09-11 更新于 2023-09-12 分类于笔试阅读次数：本文字数： 3k 阅读时长 ≈ 3 分钟

1、路径偏差数量

牛牛有一棵二叉树，该二叉树节点的权值为\(0/1\)。

牛牛给你这棵二叉树，想让你告诉他该二叉树从根节点到叶子节点的所有路径中，节点"权值\(1\)的个数"比"权值\(0\)的个数"多\(1\)的路径有多少条呢。

返回路径数目。

样例

输入：
{1,0,0,1,0,#,1}

输出：
2

提示：
树的结构如下，根节点到叶子节点的路径中，1的个数比0的个数多一的路径有两条。

输入：
{0,1,1,0,1,1,0}

输出：
2

第一个样例如下图所示：

graph TD
    A((1));B((0));C((0));D((1));
    E((0));F((1));X(( ));
    A---B;A---C;B---D;B---E;
    C---X;C---F;
    style X fill:#f100,stroke-width:0px
    linkStyle 4 stroke:#0ff,stroke-width:0px

解答

直接通过深度优先搜索遍历每个叶子节点，然后判断当前路径下权值\(1\)的节点个数是否恰好比节点\(0\)的个数多\(1\)即可。

代码

class Solution{
    int ans=0;
    void dfs(TreeNode*r,int c0,int c1){
        if(r==nullptr) return;
        r->val==0?++c0:++c1;
        if(r->left==nullptr&&r->right==nullptr&&c1==c0+1) ++ans;
        dfs(r->left,c0,c1);
        dfs(r->right,c0,c1);
    }
    int solve(TreeNode* root){
        dfs(root,0,0);
        return ans;
    }
};

2、删除中位数

牛牛有一个长度为\(n\)的序列\(a\)，以及一个长度为\(n-1\)的序列\(b\)，序列\(b\)中的元素不重复。

对于这个序列\(a\)牛牛会先求出他的中位数，然后再根据序列\(b\)的顺序依次删除原序列\(a\)中对应下标的元素，即删除\(a[b[i]],0\le i<n-1\)。

每次删除完一个数后，牛牛会统计序列\(a\)中剩下的数的中位数是什么，若剩下的数为奇数牛牛会取中间数（排序后），若为偶数牛牛会取中间两个数的平均值（排序后）。

牛牛把每次的结果都记录下来了，但是他怕出错，给你初始的序列\(a\)和\(b\)，希望你能帮他验证一下。

输入

第一行为一个\(t\)，表示有\(t\)组数据。

接下来有\(3 \times t\)行，每组数据的第一行为\(n\)表示序列长度。

第二行为\(n\)个整数，表示序列\(a\)的元素。

第三行为\(n-1\)个整数，表示序列\(b\)的元素。

输出

输出为\(t\)行，每行有\(n\)个整数，表示每组数据的答案，其中输出若是浮点数保留小数点后一位，否则按整数输出。

样例

输入：
2
5
2 2 1 3 5
3 1 2 5
4
1 1 1 1
1 2 3

输出：
2 2.5 3 4 3
1 1 1 1

提示：
第一组数据中，初始序列a的中位数为2，输出2。
第一次要删掉a[b[0]]=a[3]=1后，中位数变为2.5，输出2.5，序列变为[2, 2, 3, 5]。
第二次删掉a[b[1]]=2后，中位数变为3，输出3，序列变为[2,3,5]。
第三次删掉a[b[2]]=2后，中位数变为4，输出4，序列变为[3,5]。
第四次删掉a[b[3]]=5后，中位数变为3，输出3，序列变为[3]。

解答

我们可以考虑使用对顶堆来完成这个过程的求解。它的具体过程是：用一个最大堆维护目前拥有的较小数，用一个最小堆维护目前拥有的较大数。并且这两个堆的大小相差不超过\(1\)。此时，如果两个堆如果元素总和是奇数，那么取较多元素的那个堆的堆顶即为中位数，否则取两个堆的元素作为平均值。

但是呢，这题是将数组中的元素逐个删去，用对顶堆似乎不行。解决方法是：对整个操作逆向，从而整个过程都是在添加数，这时使用对顶堆可以完成。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1000004;
int a[N],b[N],vis[N],n;
int ans[N];
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        vis[i]=0;
    }
    for(int i=1;i<n;i++){
        scanf("%d",&b[i]);
        vis[b[i]]=1;
    }
    b[n]=min_element(vis+1,vis+n+1)-vis;
    priority_queue<int>ql;
    priority_queue<int,vector<int>,greater<int>>qr;
    for(int i=n;i>=1;i--){
        int x=a[b[i]];
        if(qr.empty()||x>=qr.top()) qr.push(x);
        else ql.push(x);
        while(ql.size()+1<qr.size()){
            ql.push(qr.top());qr.pop();
        }
        while(ql.size()>qr.size()){
            qr.push(ql.top());ql.pop();
        }
        if(qr.size()>ql.size()) ans[i]=qr.top()*2;
        else ans[i]=ql.top()+qr.top();
    }
    for(int i=1;i<=n;i++){
        printf((ans[i]&1?"%d.5%c":"%d%c"),ans[i]>>1, " \n"[i==n]);
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
}

3、勇敢牛牛不怕困难

有\(n\)个怪物，第\(i\)个怪物的战斗力为\(a_i\)，初始时，牛牛的战斗力为\(0\)。

牛牛要与这\(n\)个怪物战斗，设牛牛与第\(i\)个怪物战斗时牛牛的战斗力为\(x\)，则：

若\(x<a_i\)，则牛牛触发被动技能"勇敢牛牛不怕困难"使得自己的战斗力提升至\(a_i\)并战胜这个怪物，这会让牛牛的勇气值提升\(a_i-x\) 。
若\(x\ge a_i\)，则牛牛会直接战胜这个怪物，并且本次战斗结束后，牛牛的战斗力会降低至\(a_i\)。

牛牛可以任意决定与怪物战斗的顺序，牛牛想知道打败完所有的\(n\)只怪物之后，牛牛累计提升的勇气值最大可能是多少。

输入

第一行一个整数\(n(1\le n\le 200000)\)。

第二行\(n\)个整数\(a_1,a_2,\dots, a_n(1 \le a_i\le 10^9)\)。

输出

输出一个整数表示牛牛可以得到的最大勇气值。

样例

输入：
2
1 2

输出：
2

输入：
2
1 2 2

输出：
3

提示：
牛牛先和编号为2的怪物战斗，此时牛牛的战斗力为0，牛牛获得a2-0=2-0=2的勇气值，之后牛牛的战斗力变为2。
牛牛再和编号为1的怪物战斗，此时牛牛的战斗力为2，牛牛获得0的勇气值，之后牛牛的战斗力变为1。
牛牛最后和编号为3的怪物战斗，此时牛牛的战斗力为1，牛牛获得a3-1=2-1=1的勇气值，之后牛牛的战斗力变为2。牛牛总共获得2+1=3的勇气值。

解答

为了获得更多的勇气值，我们最佳的做法是：

在自身战斗力最低的时候去击败战斗力最高的怪物，这样能够使自身的勇气值上升最快。在自身攻击力最高的时候击败攻击力最低的怪物，这样能够使自身的战斗力下降的最快。

因此最优的做法是先打最高战斗力的怪物，再打对低战斗力的怪物，反复如此即可达到最大勇气值。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int a[N],n,b[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int l=1,r=n,m=0;
    while(l<=r){
        b[++m]=a[r];
        --r;
        if(l>r) break;
        b[++m]=a[l];
        ++l;
    }
    ll ans=0;
    int x=0;
    for(int i=1;i<=n;i++){
        if(x<b[i]) ans+=b[i]-x,x=b[i];
        else x=b[i];
    }
    printf("%lld\n",ans);
}

4、校验和

差错控制是计算机网络数字传输中重要的一环。

假设传输的数据以一个长度为\(n\)的二进制位串\(S\)表示，牛牛定义了一种新的校验和，他将\(S\)中所有长度为的子串进行异或，得到的新串就是他定义的校验和。

例如，对于位串\(000111\)来说，当\(k\)为\(2\)时，所有的长度为\(2\)的子串为\(00,00,01,11,11\)，将他们对应的位异或，得到的校验和为\(01\)。

然而他定义的校验和实际上难以进行好的差错控制，为了验证，牛牛决定计算在上述定义的方式下，有多少个不同的"长度为\(n\)"且"与\(S\)不同的二进制位串"可以产生"与\(S\)相同"的校验和。

子串的定义：一个串中任意个连续的字符组成的子序列。显然最终的结果与\(S\)无关，由于答案可能过大，请输出结果对\(10^9+7\)取模后的结果。

输入

第一行一个正整数\(T\)，代表测试组数。

接下来\(T\)行每行以空格分隔的两个正整数\(n,k\)。

\(1\le T\le 10^5\)
\(1\le k\le n\le 10^6\)

输出

输出\(T\)行，每行一个整数代表答案。

样例

输入：
3
1 1
2 1
2 2

输出：
0
1
0

提示：

长度为1的S可能为0或者1，可以计算得到: 不存在长度为1的且和S校验和的相同的串；
长度为2的S可能为00,11,01,10，对他们长度为1的子串进行异或，比如S为00的时候，校验和为0，11的校验与它相同。比如S为01的时候，校验和为1，10的校验与它相同；
长度为2的S可能为00,11,01,10，对他们长度为2的子串进行异或，比如S为00的时候，校验和为00，不存在长度为2的且和S校验和的相同的串。

解答

由于题目已经讲明了结果和字符串\(S\)本身是无关的，因此每个检验结果都有相同的串对应它。由于检验结果只有\(2^k\)种，因此有\(2^{n-k}\)个不同的字符串对应着当前结果，也就是说对于字符串\(S\)而言，有\(2^{n-k}-1\)个不同字符串和它有着相同的检验结果。

代码

T = int(input())
mod = 10 ** 9 + 7
for _ in range(T):
    n, k = map(int, input().split())
    print((pow(2, n - k, mod) - 1) % mod)

5、牛妹的\(k\)次奇怪操作

牛妹有一个序列\(a_1,a_2,\dots,a_n\)，牛妹可以执行次操作。每次操作步骤如下：

牛妹选择一个\(pos(1\le pos\le n)\)
将\(a_{pos}\)在二进制下最低位的\(1\)变成\(0\)

牛妹想知道\(k\)次操作后序列之和的最小值为多少？

输入

第一行输入两个整整数\(n,k\)

接下来输入\(n\)个正整数，表示牛妹的序列

\(1\le n \le 10^5,1\le k\le 100,1 \le a_i \le 10^9\)

输出

输出一个数，代表答案。

样例

输入：
2 1
8 7

输出：
7

提示：
8的二进制为1000
7的二进制为111
牛妹若对8执行操作，则序列变成[0,7]，和为7
牛妹若对7执行操作，则序列变成[8,6]，和为14
所以最小值为7

输入：
2 2
9 6

输出：
6

提示：
将9的2个1变成0，只剩下6

解答

这题是一道动态规划题目，过程非常明显：令状态\(f(i,j)\)表示对前\(i\)个数执行了至多\(j\)次操作后，这前\(i\)个元素的最小和值。

我们假设\(b_{i,j}\)表示对数组元素\(a_i\)执行了\(j\)次操作后的值。不难发现：

\(b_{i,0}=a_i\)，如果\(b_{i,j-1}=0\)，那么\(b_{i,j}=0\)。此外，由于\(a_i\le 10^9\)，因此\(j\)必定存在一个上限\(m\)，我们设其为\(m=30\)。

因此，我们不难写出\(f(i,j)\)的状态转移方程为：

\(f(i,j)= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &\min_{0\le l\le j,0\le l\le m}\{f(i-1,j-l)+b_{i,l}\} & & \text{if}\quad i > 0 \end{aligned}\right.\)

其中方程第二行表示对数\(a_i\)执行了\(k\)次操作后，从\(f(i-1,j-l)\)转移而来，并得到了\(b_{i,l}\)的和。

因此本题的最终答案为\(f(n,k)\)。

代码

#include <bits/stdc++.h>
#define lb(x) ((x) & -(x))
using namespace std;
typedef long long ll;

const int M=104;
ll f[2][M];
int a[M],n,k,x;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1,p=1;i<=n;i++,p^=1){
        memset(f[p],0x3f,sizeof(f[p]));
        scanf("%d",&x);
        int m=0;
        for(;x;x-=lb(x))
            a[m++]=x;
        a[m++]=0;
        for(int j=0;j<=k;j++){
            for(int r=0;r<=j&&r<m;r++){
                f[p][j]=min(f[p][j],f[p^1][j-r]+a[r]);
            }
        }
    }
    printf("%lld\n",f[n&1][k]);
}