笔试时间：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++) {