笔试时间：2023年3月26日 春招实习

第一题

题目：层序遍历二叉树

小红拿到一棵满二叉树，她通过层序遍历的顺序把每个节点的权值都告诉了你，保证每个节点的权值都不相同。现在小红有q次询问，每次询问一个权值，小红想知道：

1、这个节点是否存在？

2、这个节点的左儿子和右儿子的权值是多少？

输入描述

第一行输入一个正整数n，代表二叉树的层数;

第二行输入 2n-1个正整数ai，代表这个完全二叉树的层序遍历;

第三行输入一个正整数q，代表询问次数。

接下来q行，每一行输入一个x，代表一次询问。

1≤n≤20，1≤q≤10^5，1≤x≤10^9，1≤ai≤10^9

输出描述

如果存在权值为x的节点，则先输出一个字符串“Yes”。若该节点为叶子节点，则下一行输出一个字符串“LEAF”。若该节点不是叶子节点，则下一行输出两个正整数，分别代表该节点的左儿子和右儿子的权值。如果不存在权值为x的节点，则直接输出一个字符串“No”。

样例输入

2

1 2 3

3

1

3

5

样例输出

Yes

2 3

Yes

LEAF

No

参考题解

满二叉树的层序遍历下标满足以下关系：i的左孩子为：i*2+1；i的右孩子为：i*2+2

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(2 * n - 1);
    unordered_map<int, int> mp;

    for (int i = 0; i < 2 * n - 1; i++) {
        cin >> a[i];
        mp[a[i]] = i;
    }

    int q;
    cin >> q;
    
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;

        if (mp.find(x) == mp.end()) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
            int index = mp[x];
            
            if (index * 2 + 1 < 2 * n - 1) {
                int l = index * 2 + 1;
                int r = index * 2 + 2;
                cout << a[l] << " " << a[r] << endl;
            } else {
                cout << "LEAF" << endl;
            }
        }
    }

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[2 * n - 1];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < 2 * n - 1; i++) {
            a[i] = scanner.nextInt();
            map.put(a[i], i);
        }

        int q = scanner.nextInt();

        for (int i = 0; i < q; i++) {
            int x = scanner.nextInt();

            if (!map.containsKey(x)) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
                int index = map.get(x);

                if (index * 2 + 1 < 2 * n - 1) {
                    int l = index * 2 + 1;
                    int r = index * 2 + 2;
                    System.out.println(a[l] + " " + a[r]);
                } else {
                    System.out.println("LEAF");
                }
            }
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
a = [int(c) for c in input().split(" ")]
map = {a[i]:i for i in range(2**n - 1)}
q = int(input())
for _ in range(q):
    x = int(input())
    if x not in map:
        print("No")
    else:
        print("Yes")
        index = map[x]
        if index * 2 + 1 < n:
            l, r = index * 2 + 1, index * 2 + 2
            print(a[l],end=" ")
            print(a[r])
        else:
            print("LEAF")

第二题

题目：折叠回文串

给出一个长度为n的字符串串s，你可以进行折叠字符串的回文子串操作任意次(可以0次），如abba折叠后可以为ab (字符串向左折叠)或ba(字符串向右折叠);baaab折叠后可以为baa(字符串向左折叠）或aab(字符串向右折叠)。通过执行上述操作可以得到多少种不同的字符串?

1.子串必须是连续的，比如abc的子串有a,b,c,ab,bc,abc，但是ac不是子串

2.回文是从头到尾读和从尾到头读是一样的

输入描述

第一行输入一个整数n(1<=n<=18)。

第二行一个长度为n的字符串s，字符串仅包含小写字母。

输出描述

输出一个整数表示答案。

样例输入

3

aba

样例输出

3

折叠0次，可以得到aba。

折叠1次，可以得到ab或ba

一共可以得到三种不同的字符串。

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

vector<vector<bool>> getDp(int n, string s) {
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
        }
    }

    for (int gap = 2; gap < n; gap++) {
        for (int i = 0; i < n - gap; i++) {
            int j = i + gap;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
            }
        }
    }

    return dp;
}

unordered_set<string> res;

void dfs(string cur) {
    if (cur == "b") {
        // Handle 'b' case if needed
    }
    if (cur.length() >= 1) {
        res.insert(cur);
    }

    vector<vector<bool>> dp = getDp(cur.length(), cur);

    for (int i = 0; i < cur.length(); i++) {
        for (int j = i + 1; j < cur.length(); j++) {
            if (dp[i][j]) {
                int l = j - i + 1;
                if (l % 2 == 0) {
                    dfs(cur.substr(0, i + l / 2) + cur.substr(j + 1));
                    dfs(cur.substr(0, i) + cur.substr(i + l / 2));
                } else {
                    dfs(cur.substr(0, i + 1 + l / 2) + cur.substr(j + 1));
                    dfs(cur.substr(0, i) + cur.substr((i + j) / 2));
                }
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    string input;
    cin >> input;
    dfs(input);
    cout << res.size() << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    static Set<String> res = new HashSet<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String input = scanner.nextLine();
        dfs(input);
        System.out.println(res.size());
    }

    static boolean[][] getDp(int n, String s) {
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
            }
        }

        for (int gap = 2; gap < n; gap++) {
            for (int i = 0; i < n - gap; i++) {
                int j = i + gap;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }

        return dp;
    }

    static void dfs(String cur) {
        if (cur.equals("b")) {
            // Handle 'b' case if needed
        }
        if (cur.length() >= 1) {
            res.add(cur);
        }

        boolean[][] dp = getDp(cur.length(), cur);

        for (int i = 0; i < cur.length(); i++) {
            for (int j = i + 1; j < cur.length(); j++) {
                if (dp[i][j]) {
                    int l = j - i + 1;
                    if (l % 2 == 0) {
                        dfs(cur.substring(0, i + l / 2) + cur.substring(j + 1));
                        dfs(cur.substring(0, i) + cur.substring(i + l / 2));
                    } else {
                        dfs(cur.substring(0, i + 1 + l / 2) + cur.substring(j + 1));
                        dfs(cur.substring(0, i) + cur.substring((i + j) / 2));
                    }
                }
            }
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

import functools


@functools.lru_cache(maxsize=None)
def get_dp(n, s):
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True

    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True

    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True

    return dp

res = set()
@functools.lru_cache(maxsize=None)
def dfs(cur):
    if cur == 'b':
        pass
    if len(cur) >= 1:
        res.add(cur)
    dp = get_dp(len(cur),cur)
    for i in range(len(cur)):
        for j in range(i+1, len(cur)):
            if dp[i][j]:
                ''' baaaab   (i+j)//2'''
                l = j - i + 1
                if l % 2 == 0:
                    dfs(cur[:i+(l//2)] + cur[j+1::])
                    dfs(cur[:i] + cur[i+(l//2) ::])
                else:
                    dfs(cur[:i+1+(l//2)] + cur[j+1::])
                    dfs(cur[:i] + cur[(i+j)//2::])

n = int(input())
dfs(input())
print(len(res))

第三题

题目：最小的权值排序数组

给定2个整数数组A，B，数组长度都为N，数组B为权值数组，权值数据范围为[0,2]，请构造一个数组C，满足以下条件：

1、长度为N；

2、数组元素范围为[1,N]，且元素值不能重复，即为N的一个排列；

3、如果数组下标为i<j，且有B[i]>B[j]，那么一定要保证C[i]>C[j]；

4、数组C与数组A每个元素之差的和的绝对值最小，即x=Σ|Ci-Ai|，x最小，其中i∈[1,n]。

请你输出这个x的最小值。

输入描述

第一行输入一个正整数N。

第二行输入N个正整数，每个数代表数组A的元素。

第三行输入N个整数，每个数代表数字B的元素，范围为[0,2]

1≤N≤10^5

1≤Ai≤10^9

1≤Bi≤2

输出描述

输出x

样例输入

4

2 1 4 2

2 2 2 2

样例输出

1

C数组可以为2 1 4 3

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

int solution(int n, std::vector<int>& a, std::vector<int>& b) {
    std::vector<std::pair<int, int>> zeros, ones, twos;
    for (int i = 0; i < n; ++i) {
        if (b[i] == 0) {
            zeros.push_back(std::make_pair(a[i], i));
        } else if (b[i] == 1) {
            ones.push_back(std::make_pair(a[i], i));
        } else {
            twos.push_back(std::make_pair(a[i], i));
        }
    }

    std::sort(zeros.begin(), zeros.end());
    std::sort(ones.begin(), ones.end());
    std::sort(twos.begin(), twos.end());

    std::vector<int> sortedArray;
    for (auto& p : zeros) {
        sortedArray.push_back(p.second);
    }
    for (auto& p : ones) {
        sortedArray.push_back(p.second);
    }
    for (auto& p : twos) {
        sortedArray.push_back(p.second);
    }

    std::vector<int> c(n, 0);
    for (int i = 0; i < n; ++i) {
        c[sortedArray[i]] = i + 1;
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += abs(c[i] - a[i]);
    }

    return ans;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<int> b(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    int result = solution(n, a, b);
    std::cout << result << std::endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static int solution(int n, int[] a, int[] b) {
        List<Integer> zeros = new ArrayList<>();
        List<Integer> ones = new ArrayList<>();
        List<Integer> twos = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (b[i] == 0) {
                zeros.add(i);
            } else if (b[i] == 1) {
                ones.add(i);
            } else {
                twos.add(i);
            }
        }

        Collections.sort(zeros, (i1, i2) -> Integer.compare(a[i1], a[i2]));
        Collections.sort(ones, (i1, i2) -> Integer.compare(a[i1], a[i2]));
        Collections.sort(twos, (i1, i2) -> Integer.compare(a[i1], a[i2]));

        List<Integer> sortedArray = new ArrayList<>(zeros);
        sortedArray.addAll(ones);
        sortedArray.addAll(twos);

        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[sortedArray.get(i)] = i + 1;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.abs(c[i] - a[i]);
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }

        int result = solution(n, a, b);
        System.out.println(result);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solution(n, a, b):
    zeros = []
    ones = []
    twos = []
    for i in range(n):
        if b[i] == 0:
            zeros.append((a[i], i))
        elif b[i] == 1:
            ones.append((a[i], i))
        else:
            twos.append((a[i], i))

    zeros.sort()
    ones.sort()
    twos.sort()

    sortedArray = [i for _, i in zeros + ones + twos]

    c = [0] * n
    for i, idx in enumerate(sortedArray):
        c[idx] = i + 1

    ans = sum(abs(c[i] - a[i]) for i in range(n))

    return ans


n = int(input())
a = [int(c) for c in input().split(" ")]
b = [int(c) for c in input().split(" ")]

print(solution(n,a,b))

第四题

题目：车

在一个由n*m个格子组成的矩形棋盘maze上，第i行第j列的格子编号为(i,j)，maze的格子只可能是障碍或者道路，牛牛初始在(1,1)处，他每一步可以沿道路水平方向向右或者垂直方向向下移动若干格子（至少需要移动一格），但是不能越过障碍，现在牛牛想知道他又多少种方案从(1,1)到达(n,m)，由于答案可能会很大，因此你只需要输出答案对10^9+7取模的结果即可。

输入描述

第一行输入2个正整数n，m代表棋盘的大小。

接下来n行每行输入一个长度为m的字符串。若为"#"，则表示障碍物；为"."，则表示为道路。

2≤n,m≤2000，mazei,j∈{.,#}。

输出描述

输出一个数字表示方案数对10^9+7取模的结果。

样例输入

示例1:

2 3

...

#..

示例2:

5 5

.....

#....

#....

.....

.....

样例输出

示例1:

3

示例2：

419

参考题解

dp+前缀和。

Python：[此代码未进行大量数据的测试，仅供参考]

n,m = map(int, input().split(" "))
maze = []
for i in range(n): maze.append([c for c in input()])

pres_row = [[0 for _ in range(m)] for _ in range(n)]
pres_col = [[0 for _ in range(m)] for _ in range(n)]

dp = [[0 for _ in range(m)] for _ in range(n)]

dp[0][0] = pres_col[0][0] = pres_row[0][0] = 1

for j in range(1,m):
    if maze[0][j] == '#':break
    dp[0][j] = pres_row[0][j-1]
    pres_row[0][j] = pres_row[0][j-1] + dp[0][j]
    pres_col[0][j] = dp[0][j]

for i in range(1,n):
    for j in range(m):
        if maze[i][j] == '#':continue
        dp[i][j] = pres_col[i-1][j]
        if j > 0:
            dp[i][j] += pres_row[i][j-1]
        pres_col[i][j] = pres_col[i-1][j] + dp[i][j]
        pres_row[i][j] = pres_row[i][j-1] + dp[i][j]

print(dp[-1][-1])