笔试时间：2023年9月8日 秋招

第一题

题目：寻找字符A

现在有n个人坐成一个圈，也就是说第n个人的下一个是第1个人。每个人背上贴了一个大写字母。这个字母可能是A也可能是B。你的任务是从第一个人开始，顺次向后计数，每遇到一个贴着字母A的人就计数一次。第k次计数到A后停止。现在河你总共需要数多少个人才能停止。保证至少有一个人背上贴的是A。

输入描述

第一行两个整数n,k，表示共有n个人，计数A的次数为k。

第二行n个大写字母，只能是A或者B，依次表示每个人背上所贴的字母。

1 <= n,k <= 100000

输出描述

一行，一个整数表示共需要数多少人。

样例输入

示例一：

3 3

AAB

示例二：

3 3

BBA

样例输出

示例一：

4

提示:

显然是数一圈后再数到第1个人时停止。总共数了4个人。

示例二：

9

提示:

数三圈后停在第3个人这里。

参考题解

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

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();

        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'A') {
                a.add(i + 1);
            }
        }

        int d = k / a.size();
        int r = k % a.size();
        if (r == 0) {
            d--;
            r = a.size();
        }

        long ans = 1L * d * n + a.get(r - 1);
        System.out.println(ans);
    }
}

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

n, k = map(int, input().split())
s = input()
a = []

for i in range(1, n + 1):
    if s[i - 1] == 'A':
        a.append(i)

d = k // len(a)
r = k % len(a)

if r == 0:
    d -= 1
    r = len(a)

ans = 1 * d * n + a[r - 1]
print(ans)

第二题

题目：树上运算

你想对一棵奇怪的二又树进行运算。这棵树每个节点要么有两个子节点，要么没有子节点。如果一个节点没有子节点，则这个节点的值为1。如果某个节点有两个子节点，这个节点的值就是它两个子节点的值做某种运算后的结果，某种运算取决于这个节点的颜色，如果为红色则是乘法，如果为蓝色则是加法。你想知道根节点的值。树，是一种无向无环联通图。

输入描述

第一行一个正整数n表示节点个数；

第二行n - 1个正整数p[2,3,...,n]，pi表示第i个节点的父节点。1号节点是根节点；

第三行n个整数c[1,2,...,n]，当c[i] = 1时表示第i个节点是蓝色，c[i]= 2则表示红色。

数据保证形成合法的树。

输出描述

输出一行一个整数表示根节点的值。考虑到值可能很大，输出它除以1000000007的余数。

样例输入

3

1 1

1 1 1

样例输出

2

提示:

因为2号节点和3号节点都没有子节点，因此值都为1因为1号节点的颜色是蓝色，因此1号节点的值是2号节点的值和3号节点的值的相加，即1+1=2

参考题解

模拟，从上到下计算即可。

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

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

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static long[] a;
    static ArrayList<Integer>[] g;
    static int[] c;
    static long mod = 1000000007;

    public static void dfs(int u) {
        if (g[u].isEmpty()) {
            a[u] = 1;
        } else {
            int v = g[u].get(0);
            int w = g[u].get(1);
            dfs(v);