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

1、小红一家人

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

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

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

样例

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

输出：
2

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

上面样例对应的树为：

解答

本题是一道树形动态规划。令状态 $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\le 100)$，分别表示每道菜的售价。

输出

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

样例

输入：
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$ 支试管的标记为 $ta{b}_i$。如果两支试管标记相同，那么它们就是联通的。

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

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

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

输入

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

第二行给出 $n$ 个整数，第 $i$ 个整数表示第 $i$ 试管的标签 $ta{b}_i$。

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

• $1\le n,m\le {10}^5$
• $1\le ta{b}_i\le n$
• $1\le a\le n$
• $1\le b\le 10000$

输出

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

假设正确答案为 $a$，你输出的答案为 $b$，当 ${\displaystyle \frac{|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]);
        }
    }
}