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

发表于 2023-09-07 更新于 2023-11-11 分类于笔试阅读次数：本文字数： 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\le 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\)个卡特兰数，其值为\(\dfrac{C_{2n}^n}{n+1}\)。

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

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

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad j=0 \\ &f(i,j-1) & & \text{if}\quad i>0\land j=i \\ &f(i-1,j)+f(i,j-1) & & \text{if}\quad i>0\land0<j<i\\ \end{aligned}\right.\)

其中方程最后一行有两种决策：让这个栈得到一个新元素，从\(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(nm)\)时间复杂度的做法。

首先先将所有依赖进行预处理，直接得到依赖被增加或删除后的结果，并处理成一个图。如果\(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");
}