阿里大文娱秋招 2023.10.15 编程题目与题解

发表于 2023-10-20 分类于笔试阅读次数：本文字数： 2.1k 阅读时长 ≈ 2 分钟

1、小红一家人

小红拿到了一棵二叉树。小红定义，如果一个节点既有左孩子又有右孩子，那么这三个节点被称为“一家人”。

小红想知道，在这个二叉树中，一共能找到多少“一家人”？ (每个节点最多被计算一次)

设节点个数为$n,n\le 2\cdot 10^5$。$1$节点权值$n$，且任意两点权值互不相同。

样例

输入：
{1,2,3,4,5,6,7}

输出：
2

提示：
若选择了[1,2,3]这一家人，那么2,3节点就无法选取为父亲，最终就只有一组“一家人”。

上面样例对应的树为：

graph TD
  1((1));
    subgraph A2
    3((3));6((6));7((7));
  end
  subgraph A1
    2((2));4((4));5((5));
  end
  1---2;1---3;2---4;2---5;
  3---6;3---7;

解答

本题是一道树形动态规划。令状态$f_{u,0}$表示以$u$为根的子树中，最大的一家人个数是多少个，其中节点$u$不被作为一家人的父亲节点使用，令状态$f_{u,1}$表示以$u$为根的子树中，最大的一家人个数是多少个，其中节点$u$被作为一家人的父亲节点使用。

那么对于树上的一个节点$u$，它分别有如下三种情况：

$u$是一个叶子节点，这时$f_{u,0}=f_{u,1}=0$是显而易见的。
$u$只有一个儿子，假设这个儿子为$v$。可见，$u$不可能作为一个父亲节点被使用，因此$f_{u,1}=0$。如果不使用$u$，那么方案数并不会增加，无论子节点有没有被选上都没所谓，因此有$f_{u,0}=\max\{f_{v,0},f_{v,1}\}$。
$u$有两个儿子，假设两个儿子分别为$l,r$。如果$u$被作为父亲节点被使用，那么$l,r$都不能作为父亲节点被使用，因此有$f_{u,1}=f_{l,0}+f_{r,0}+1$。如果$u$不被作为父亲节点被使用，那么$l,r$是否作为父亲节点并没有所谓，因此有$f_{u,1}=\max\{f_{l,0},f_{l,1}\}+\max\{f_{r,0},f_{r,1}\}$。

对于这棵树的根节点$r$，最终答案为$\max\{f_{r,0},f_{r,1}\}$。

代码

class Solution {
public:
    vector<int> dfs(TreeNode *r){
        if(r->left==nullptr&&r->right==nullptr) return {0,0};
        if(r->left==nullptr){
            vector<int>v=dfs(r->right);
            return {max(v[0],v[1]),0};
        }
        else if(r->right==nullptr){
            vector<int>v=dfs(r->left);
            return {max(v[0],v[1]),0};
        }
        else{
            vector<int> vl=dfs(r->left),vr=dfs(r->right);
            return {max(vl[0],vl[1])+max(vr[0],vr[1]),vl[0]+vr[0]+1};
        }
    }
    int maxDepth(TreeNode* root) {
        vector<int>v=dfs(root);
        return max(v[0],v[1]);
    }
};

2、小红点菜

小红来到了一家餐馆，准备点一些菜。

已知该餐馆有$n$道菜，第$i$道菜的售价为$a_i$。

小红准备点一些价格相同的菜，但小红不会点单价超过$m$的菜。

小红想知道，自己最多可以点多少道菜？

输入

第一行输入两个正整数。

$n, m(1 \le n \le 10^6,1 \le m \le 100)$，分别表示菜单上的菜品数量以及小红准备点的最大单价。

第二行输入$n$个正整数$w_1,w_2,\dots,w_n(1\le w_i\le100)$，分别表示每道菜的售价。

输出

输出仅一行一个整数，表示小红最多可以点的菜的数量。

样例

输入：
9 6
2 3 3 6 6 6 9 9 23

输出：
3

提示：
小红点单价6元的菜，共可以点3份菜。

解答

只需要统计所有单价的出现次数，然后在不超过$m$的单价中，取一个最大的出现次数即可。

代码

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

const int N=104;
int c[N];
int main(){
    int n,k,x;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        ++c[x];
    }
    printf("%d\n",*max_element(c+1,c+k+1));
}

3、牛牛的连通器

牛牛最近学习了连通器原理：在连通器中装有同种液体，当连通器中液体不流动时，各容器中液面总保持相平。

牛牛有$n$支规格相同的试管，这些试管中有一些底部是相互连通的。为了避免混淆试管之间的连通性，牛牛给每支试管做了标记，第$i$支试管的标记为$tab_i$。如果两支试管标记相同，那么它们就是联通的。

初始时，每支试管中都没有水，并且视试管的容积为无穷大，现在牛牛有三种操作：

$1\ a\ b$: $1$表示这是个注水操作，表示牛牛向第$a$支试管中注入$b$毫升水。
$2\ a\ b$：$2$表示这是个抽水操作，表示牛牛从第$a$支试管中抽出$b$毫升水，该操作保证第$a$支试管所在的连通器中至少有$b$毫升水。
$3\ a$：$3$表示这是个询问操作，牛牛想知道第$a$支试管中有多水毫升水。

他会进行$m$个操作，你能帮牛牛完成这些操作吗？由于试管的规格相同，因此忽略掉底部连通部分的体积，我们可以进一步简化连通器原理：在连通器中装有同种液体，当连通器中液体不流动时，各容器中的液体体积相同。

输入

第一行给出两个整数$n$和$m$，分别表示试管数量和操作数量。

第二行给出$n$个整数，第$i$个整数表示第$i$试管的标签$tab_i$。

接下来$m$行，每行都是一个操作，其格式如题目所述。

$1 \le n, m \le 10^5$
$1 \le tab_i \le n$
$1\le a\le n$
$1\le b\le 10000$

输出

对于每个$3$操作，输出一个浮点数，表示询问的试管中水的体积。

假设正确答案为$a$，你输出的答案为$b$，当$\dfrac{|a-b|}{\max(a,1)}<10^{-5}$时视为答案正确。

样例

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

输出：
2.500000
3.500000
1.500000

提示：
由tab值我们知道：第1支试管和第3支试管连通，第2支试管和第4支试管连通。第一个操作我们向第1支试管中注入5毫升水，根据连通器原理，最终第1支试管和第3支试管中的水是一样的，即5/2 = 2.5毫升。
同理，第三个操作最终会使得第2支试管和第4支试管中的水都是7/2=3.5毫升。抽水操作也是相同的道理。
需要注意的是，虽然直观地看第4支试管中此时只有3.5毫升水，但是第4支试管所在的整个连通器中有7毫升水，因此牛牛是可以抽取4毫升水的。

输入：
6 8
1 2 2 2 3 1
1 3 10
3 2
2 3 2
3 3
1 1 9
1 5 10
3 5
3 6

输出：
3.333333
2.666667
10.000000
4.500000

解答

本题直接模拟即可解决。我们只需要将所有试管的编号映射成连通器的编号后，再同一进行处理即可。对于每一次输出，相当于是输出水量和试管个数的比值。

代码

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

const int N=100004;
int sz[N],tg[N];
ll s[N];
int main(){
    int n,m,o,a,b;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&tg[i]);
        ++sz[tg[i]];
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d",&o,&a);
        if(o<=2){
            scanf("%d",&b);
            s[tg[a]]+=(o==1?b:-b);
        }
        else{
            a=tg[a];
            printf("%.10f\n",1.0*s[a]/sz[a]);
        }
    }
}