华为（留学）秋招 2023.09.06 编程题目与题解

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

1、设备按秩序组网的最大拓扑长度

在设备组网方法中，有一种按照一定秩序的组网方式，即设备的组网按照设备优先级顺序进行，最后组成一个线性拓扑。

给定一组设备，设备包含组网优先级和时延，进行秩序组网后（按照优先级从小到大排序），输出线性拓扑中时延累加和小于等于目标值 delay 的最长子拓扑的长度。

概念约束：

子拓扑指线性拓扑连续的一段
最长子拓扑指的是拓扑中的设备数量最多的子拓扑
累加和是子拓扑中每个设备的时延之和
优先按照优先级升序排序，其次按照时延升序排序

输入

第一行是一个数组，第一个数字是数组长度，后面跟的是设备优先级数组元素，用整数表示，数组长度范围是 $[1, 100000]$ ，优先级范围是 $[1, 100000]$ 。

第二行是一个数组，第一个数字是数组长度，后面跟的是设备时延数组元素，用整数表示，和第一行一一对应，时延范围是 $[1, 100000]$ 。

第三行是目标值。

输出

最长子拓扑长度，如果没有满足条件的，则返回 $0$ 。

样例

输入：
6 1 3 2 5 4 6
6 12 19 15 17 13 22
50

输出：
3

提示：
最长子拓扑12 15 19，因为其是满足条件的最长子拓扑，且和46最小，所以最长子拓扑是3。
排序后的数组：
1 2 3 4 5 6
12 15 19 13 17 22

输入：
4 1008 1005 1005 1000
4 32 33 33 25
16

输出：
0

提示：
没有满足条件的子拓扑。
排序后的数组:
1000 1005 1005 1008
25 33 33 32

解答

对每台设备以优先级为第一关键字，时延为第二关键字进行排序后，假设第 $i$ 台设备的时延为 $a_{i}$ ，那么问题的意思就转换成求数组 $a$ 和不超过 delay 值 $d$ 的最长子数组。

令 $s$ 为 $a$ 的前缀和，即 $s_{0} = 0, s_{i} = s_{i - 1} + a_{i}$ 。那么对于所有 $r \in [1, n]$ ，只需要找到最小的 $l$ 使得 $s_{r} - s_{l} \leq d$ 即可。由于 $a$ 是正整数，因此 $s$ 是单调递增的。可以通过双指针找到最小的 $l$ 。最终 $r - l$ 的最大值即为答案。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
# define X first
# define Y second
typedef long long ll;
using namespace std;

const int N=100004;
pi pa[N];
ll s[N];
int n,d;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&pa[i].X);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&pa[i].Y);
    scanf("%d",&d);
    sort(pa+1,pa+n+1);
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+pa[i].Y;
    int ans=0;
    for(int r=1,l=0;r<=n;r++){
        while(s[r]-s[l]>d) ++l;
        ans=max(ans,r-l);
    }
    printf("%d\n",ans);
}

2、套碗游戏

有一套塑料套碗的玩具，碗中间有个洞，可以从大到小套到一个固定在桌子的木棍上，对这些套碗编号 $1, 2, \dots, n$ 。我们把碗套到木棍后可以随时取出，但是取出的方式，只能是从木棍的上方取出，一次只能取出一个碗。那么就有可能会有多种套碗和取碗的顺序组合。现在问题是，给定套碗的个数，计算取碗的所有排列组合数，并且，对于某一个给定的取碗顺序，确定是否可行。

输入

第一行：一个正整数，表示套碗的个数 $M, M$ 的取值范围是 $[2, 100]$ 。

第二行：取碗的序列，用空格分隔。

输出

第一行：总共有多少种取碗方式。第二行：取碗的序列是否可行，是输出 $1$ ，否输出 $0$ 。

样例

输入：
2
1 2

输出：
2
1

提示：
共有如下2种取碗方式：
2 1
1 2

输入：
3
3 1 2

输出：
5
0

提示：
共有如下5种取碗方式：
3 2 1
1 2 3
2 1 3
1 3 2
2 3 1

解答

这道题其实就两个问题。

出栈序列个数

$n$ 个不同元素进栈，有多少种不同出栈序列的个数？

答案是第 $n$ 个卡特兰数，其值为 $\frac{C_{2 n}^{n}}{n + 1}$ 。

当然如果不知道这个数，我们也可以使用动态规划来求出这个值。

令 $f (i, j) (0 \leq j \leq i \leq n)$ 表示当前已经有 $i$ 个元素已经进栈，并且已经有 $j$ 个元素出栈的不同序列个数，那么我们可以写出 $f (i, j)$ 的状态转移方程为

$f (i, j) = {\begin{aligned} 1 & if j = 0 \\ f (i, j - 1) & if i > 0 \land j = i \\ f (i - 1, j) + f (i, j - 1) & if i > 0 \land 0 < j < i \end{aligned}$

其中方程最后一行有两种决策：让这个栈得到一个新元素，从 $f (i - 1, j)$ 转移而来，或者是从栈中弹一个元素出去，从 $f (i, j - 1)$ 转移而来。

因此，不同的出栈序列一共有 $f (n, n)$ 个。

需要注意的是， $f (n, n)$ 的值会超过 $2^{64}$ ，因此建议使用支持大数计算的语言做这题。

合法出栈序列

给定一个出栈序列，判断这个出栈序列是否是一个合法的出栈序列？

注意，这里的入栈序列默认了从 $1$ 到 $n$ 。

这题不难使用贪心去想，基本思想是贪心地模拟整个入栈出栈过程。我们首先枚举每个出栈序列中的元素 $x$ ，如果 $x$ 恰好在栈顶，那么选择弹出。否则，将后面的所有未入栈元素尝试入栈，直到找到 $x$ 。如果未能找到 $x$ ，那么说明当前出栈序列不是合法的；否则，找到 $x$ ，让它先进栈，再出栈即可。

最终，如果出栈的行为成功被模拟，那么这就是一个合法的出栈序列。

代码

from math import comb

n = int(input())
a = list(map(int, input().split()))
st = []
ok = 1
k = 1
for x in a:
    if len(st) > 0 and st[-1] == x:
        st.pop()
    else:
        if k > x:
            ok = 0
            break
        while k < x:
            st.append(k)
            k += 1
        k += 1

print(comb(n * 2, n) // (n + 1))
print(ok)

3、统计对象被引用次数

软件开发过程中，对象之间的引用关系非常关键。设计一个功能，实现引用次数分析，并按照对象出现的时序，逐一输出所有对象的引用次数。

1、对象的引用次数为直接引用次数 + 间接引用次数。直接引用: B 对象内部使用到了 A 对象，即 B 直接引用了 A；间接引用：B 对象内部使了 A 对象，但 C 对象未使用 A 对象，而是使用了 B 对象，这样的关系我们称 C 间接引用了 A；

2、将对象抽象为数字表示，不同的正整数代表不同的对象；

输入

第 $1$ 行： $n$ ，代表引用关系的组数。

第 $2$ 行: $a b c$ ，代表第 $1$ 个引用关系三元组。

第 $n + 1$ 行: $x y z$ ，代表第 $n$ 个引用关系三元组。

说明：

对象引用关系元组的组成为: 第一位，被引用对象，第二位，引用对象，第三位， $+$ 为引用， $-$ 为去引用。如：
$1 2 +$ （ $+$ 表示添加引用， $1$ 为被引用对象， $2$ 为引用对象，即 $2$ 引用了对象 $1$ ）。
$1 2 -$ （ $-$ 表示删除引用， $1$ 为被引用对象， $2$ 为引用对象，即 $2$ 引用了对象 $1$ ）。
$1 3 +$ （ $+$ 表示添加引用， $1$ 为被引用对象， $3$ 为引用对象，即 $3$ 引用了对象 $1$ ）。
引用对象用正整数表示，取值范围为 $[1, 65535]$ 。
设定对象不存在循环引用，也不存在引用次数为负数的情况。

输出

输出对象及对象引用次数（每行一组），最后一行以 $0$ 结束。

说明：

输出结果按照对象生成的时间先后排列；
引用次数为 $0$ 的对象不输出；

样例

输入：
4
1 2 +
1 3 +
1 4 +
1 2 -

输出：
1 2
0

提示：
1被2，3，4直接引用，然后2去除引用，因此1最终只被引用2次，其他对象引用次数为0，不输出；
其中对象生成的时间先后为1，2，3，4

输入：
6
1 2 +
1 3 +
1 4 +
1 2 -
3 5 +
4 6 +

输出：
1 4
3 1
4 1

提示：
1被2，3，4直接引用，被5，6间接引用，然后2去除引用，因此1最终只被引用4次；3被5直接引用，因此3最终只被引用1次；4被6直接引用，因此4最终只被引用1次；
其中对象生成的时间先后为1，2，3，4，5，6

解答

本题的数据范围不确定，以下提供一种 $O (n m)$ 时间复杂度的做法。

首先先将所有依赖进行预处理，直接得到依赖被增加或删除后的结果，并处理成一个图。如果 $x$ 引用了 $y$ ，那么就需要添加一条有向边 $(x, y)$ 。此外，还需要预处理出每个对象的出现次序，以便以后输出。

接下来维护每个节点的计数值。枚举每个出现的对象，并对其进行广度优先搜索，对所有被遍历到的节点计数值都增加 $1$ （除了自己）。

接下来只需要按照时序枚举每个节点，并输出其出现次数即可。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
# define X first
# define Y second
typedef long long ll;
using namespace std;

const int N=100004;
char s[N];
map<pi,int>mp;
int cnt[N],t[N],m=0;
int n,d;
vector<int>g[N],nd;
bool vis[N];
void bfs(int s){
    for(int x:nd) vis[x]=0;
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        ++cnt[u];
        for(int v:g[u]){
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
            }
        }
    }
    --cnt[s];
}
int main(){
    int x,y;
    scanf("%d",&n);
    memset(t,0x3f,sizeof(t));
    for(int i=1;i<=n;i++){
        scanf("%d %d %s",&x,&y,s);
        int w=(s[0]=='+'?1:-1);
        mp[pi(y,x)]+=w;
        if(t[x]>n+n) t[x]=++m,nd.push_back(x);
        if(t[y]>n+n) t[y]=++m,nd.push_back(y);
    }
    for(auto &[e,w]:mp){
        if(w>0){
            g[e.X].push_back(e.Y);
        }
    }
    for(int x:nd){
        bfs(x);
    }
    sort(nd.begin(),nd.end(),[&](int x,int y){return t[x]<t[y];});
    for(int x:nd){
        if(cnt[x]>0){
            printf("%d %d\n",x,cnt[x]);
        }
    }
    puts("0");
}