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

第一题

题目：正直者与欺诈者

有n个人，其中一些人是正直者，另外—些人是欺诈者。已知正直者永远说真话，欺诈者永远说假话。现在你已经知道了每个人是正直者还是欺诈者。有q次询问，每次询问你需要回答x指证y是正直者还是欺诈者。

输入描述

第一行输入一个正整数n，代表人数。

第二行输入一个长度为n的字符串，第i个字符为'H'代表第i个人是正直者，'L'代表欺诈者。

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

接下来的行，每行输入两个正整数a和y，代表一次询问。

1 ≤n,q≤ 104

1 ≤x, y ≤n

x≠y

输出描述

输出q行，分别代表每次指证的结果。

若x指证y是正直者，则输出"honester"。如果是欺诈者，则输出"liar" 。

样例输入

5

HLHHL

3

1 2

2 3

3 4

样例输出

liar

liar

honester

第一个人是正直者，他会说真话，因此他指证第二个人是欺诈者。

第二个人是欺诈者，他会说假话，因此他指证第三个人是欺诈者。

第三个人是正直者，他会说真话，因此他指证第四个人是正直者。

参考题解

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

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

int main() {
    int n;
    cin >> n;
    string people;
    cin >> people;
    int q;
    cin >> q;

    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        if (people[x - 1] == 'H') {
            if (people[y - 1] == 'H') {
                cout << "honester" << endl;
            } else {
                cout << "liar" << endl;
            }
        } else {
            if (people[y - 1] == 'H') {
                cout << "liar" << endl;
            } else {
                cout << "honester" << endl;
            }
        }
    }

    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 people = scanner.next();
        int q = scanner.nextInt();

        for (int i = 0; i < q; ++i) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            if (people.charAt(x - 1) == 'H') {
                if (people.charAt(y - 1) == 'H') {
                    System.out.println("honester");
                } else {
                    System.out.println("liar");
                }
            } else {
                if (people.charAt(y - 1) == 'H') {
                    System.out.println("liar");
                } else {
                    System.out.println("honester");
                }
            }
        }
    }
}

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

n = int(input())
people = [c for c in input()]
q = int(input())
for _ in range(q):
    x, y = map(int, input().split(" "))
    if people[x - 1] == 'H':
        if people[y - 1] == 'H':
            print("honester")
        else:
            print("liar")
    else:
        if people[y - 1] == 'H':
            print("liar")
        else:
            print("honester")

第二题

题目：小红的红子树

小红拿到了—棵有根树，树的根节点为1号节点。小红将一些节点染成了红色。她想知道有多少子树满足子树所有节点均为红色？

输入描述

第一行输入一个正整数n，代表节点的数量；

第二行输入一个长度为n的字符串，第i个字符为'R'代表第i个节点被染成红色，为'w'代表未被染色；

接下来的n ― 1行，每行输入两个正整数x和y，代表x和y有一条边连接；

1<n≤10^5

1 ≤x, y ≤n

输出描述

输出一个整数，代表节点均为红色的子树数量。

样例输入

3

WRR

1 2

1 3

样例输出

2

节点2和节点3均合法

参考题解

dfs遍历树，向上返回的是以当前节点为根的子树是否满足全部节点为红色即可。

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

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

int n;
unordered_map<int, vector<int>> nxs;
vector<char> colors;
int cnt = 0;

bool dfs(int node, int pre) {
    bool cur = (colors[node] == 'R');
    if (nxs.count(node)) {
        for (int nx : nxs[node]) {
            if (nx != pre) {
                cur = dfs(nx, node) && cur;
            }
        }
    }
    if (cur) cnt++;
    return cur;
}

int main() {
    cin >> n;
    colors.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> colors[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        nxs[u].push_back(v);
        nxs[v].push_back(u);
    }
    dfs(1, -1);
    cout << cnt << endl;
    return 0;
}

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

n = int(input())
nxs = {}
colors = [0] + [c for c in input()]
for _ in range(n-1):
    u,v = map(int, input().split(" "))
    if u not in nxs: nxs[u] = []
    if v not in nxs: nxs[v] = []
    nxs[u].append(v