25届秋招-科大讯飞研发岗笔试真题卷（4）

整场笔试难度不高，考点分别为：模拟、模拟、DFS
大家可以在后台私信ak机加入25届校招交流群哦，也可以添加ak机的微信号：ak_coding加入校招交流群。可以在群里面讨论求职等相关内容，包括但不限于笔试算法的内容。
给大家安利一波ak机制作的大厂笔试基础课，全文共22万字，200+笔试算法题，并且根据考点对题目进行了汇总和梳理，并包含大量的算法讲解、文字、视频题解内容。含金量巨高，秋招将至，使用该题单进行刷题试用版链接：https://t6qoa9k7sz.feishu.cn/docx/PNn9dnWXeo04zYxEe9hc6bP4nIe
在线刷题网站：https://www.sspnote.com/ak
AK机决战大厂笔面试：https://t.zsxq.com/Lhjjb
第一题：金字塔
在线测评链接：https://www.sspnote.com/oj/10/378
题目描述
给出正整数$n$，输出由$n$组成的倒立金字塔。倒立金字塔的形状请参考样例。
输入描述
第一行给出一个正整数$n(1\le n\le 100)$。
输出描述
输出倒立金字塔。
样例 1
输入
5
输出
55555
5555
555
55
5
样例 2
输入
10
输出
10101010101010101010
101010101010101010
1010101010101010
10101010101010
101010101010
1010101010
10101010
101010
1010
10
题解：模拟
直接使用 for 循环模拟即可，根据样例 2 我们可以发现，当$n\ge 10$的时候，每一行输出的基本单位的长度是$n$的位数，因此我们可以将$n$转为字符串，方便输出。
C++
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin >> n;
    string s = to_string(n);
    int len = s.size();
    for (int i = n; i >= 1; i--)
    {
        for (int j = 0; j < i; j++)
        {
            cout << s;
        }
        puts("");
    }
    return 0;
}
Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = Integer.toString(n); // 转为字符串
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j < i; j++) {
                System.out.print(s);
            }
            System.out.println();
        }
    }
}
Python
n = int(input())
s = str(n)  # 转为字符串
for i in range(n, 0, -1):
    print(s * i)
第二题：合并数字
在线测评链接：https://www.sspnote.com/oj/10/379
题目描述
给定一个栈，初始时栈中为空。有$m$次操作，每次操作向栈口压入一个数字。在一次操作之后，如果栈中有两个连续的相同数字$x$，则它们会合并成数字$x+1$。如果仍有，则重复此过程（可以证明同一时刻最多只有一组两个连续的相同数字）。
问$m$次操作之后栈中的数字自底向上是多少？
输入描述
第一行正整数$m(1\le m\le 10^5)$，表示压入数字的个数。
接下来一行$m$个正整数$a_1,a_2...a_m(1\le a_i\le m)$，表示按顺序压入的数字。
输出描述
一行若干个数字，表示最后剩下的数字（自栈底至栈顶）
样例 1
输入
6
1 1 2 3 4 5
输出
6
样例解释
在这个样例中，每次压入的数字都和栈中唯一的数字相间，故会合并成$x+1$
样例 2
输入
7
1 1 2 2 3 2 1
输出
3 2 3 2 1
题解：模拟
本题题目描述的很明确了，其实就是一个栈的模拟，只不过这个栈比较特殊：当栈顶有两个相同元素$x$，需要将其合并为$x+1$。
因此，我们可以使用数组来按照题意进行模拟，C++同学也可以选用vector这种数据结构来进行模拟。
C++
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin >> n;
    vector<int> res; // 数组模拟栈
    int m = 0;       // 栈的大小
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        res.push_back(x);
        m++;
        while (m >= 2 && res[m - 1] == res[m - 2])
        {
            res.pop_back();
            res.back() += 1;
            m--;
        }
    }
    for (int &x : res)
    {
        cout << x << " ";
    }
    return 0;
}
Java
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> res = new ArrayList<>(); // 数组模拟栈
        scanner.nextLine(); // consume newline
        String[] input = scanner.nextLine().split(" ");
        for (String x : input) {
            int num = Integer.parseInt(x);
            res.add(num);
            while (res.size() >= 2 && res.get(res.size() - 1).equals(res.get(res.size() - 2))) {
                res.remove(res.size() - 1);
                res.set(res.size() - 1, res.get(res.size() - 1) + 1);
            }
        }
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(res.get(i));
        }
    }
}
Python
n = int(input())
res = []  # 数组模拟栈
w= list(map(int,input().split()))
for x in w:
    res.append(x)
    while len(res) >= 2 and res[-1] == res[-2]:
        res.pop()
        res[-1] += 1

print(" ".join(map(str, res)))
第三题：拓展数组
在线测评链接：https://www.sspnote.com/oj/10/380
题目描述
给出一个长度为$n$的数组$a_1,a_2,...,a_n$，假如你从$x$点出发(初始区间为$[x,x]$，初始价值为$a_x$)。
每到达一个点就把这个点加入到区间内并获得当前点的价值，每次能将当前所拥有的区间向右或者向左扩展一个（不能超过边界），且被拓展的位置的值一定要大于当前所拥有的价值之和。
输出对于起点$x=1,2,...,n$，答案分别是多少。
输入描述
第一行正整数$n(1\le n\le 10^5)$，表示数组的长度。
接下来一行$n$个正整数代表$a_1,a_2,...,a_n(1\le a_i\le 10^9)$。
输出描述
输出一行$n$个数字代表答案。
样例
输入
3
2 1 4
输出
2 7 4
样例解释
从$1,3$出发只能在自己，从$2$出发先变成$[2,1]$，再变成$[2,1,4]$
样例 2
输入
5
2 3 6 1 4
输出
11 9 6 11 4
题解：DFS
每个点我们都需要计算可以拓展的最大权值，乍一看似乎时间复杂度最坏为$O(n^2)$
但是我们仔细分析会发现，由于拓展的严格条件限制：只能拓展的点比当前区间和还要大，假设初始数字为 1，那么每一次拓展，都可以使得它的权值至少翻倍，也就是说，当拓展到 30 次的时候，它的权值一定严格大于$2^{30}>10^9$，因此对于每一个位置，最多只能拓展 30 次。因此我们直接使用 DFS 暴搜是不会超时的，时间复杂度为$O(30n)$
在进行 DFS 暴搜的时候，我们需要维护当前区间的左端点$l$和右端点$r$，以及区间和$sum$
然后根据题目的拓展条件搜索即可。
其他语言（C++、Java）可以参考AK机网站的题解哦~
Python
n = int(input())
a = [0]+ list(map(int, input().split()))
res = 0

def dfs(l, r, sum):  # 当前维护的区间是[l,r], 区间和为sum
    global res
    res = max(res, sum)
    if l < 1 or r > n:  # 越界
        return
    if l > 1 and a[l - 1] > sum:  # 尝试拓展左区间
        dfs(l - 1, r, sum + a[l - 1])
    if r < n and a[r + 1] > sum:  # 尝试拓展右区间
        dfs(l, r + 1, sum + a[r + 1])


for i in range(1, n + 1):
    res = 0
    dfs(i, i, a[i])
    print(res, end=" ")