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

第一题

题目：小红的回文博弈

小红和朋友玩游戏，初始有一个字符串s，两个人轮流操作:

1、先将字符串重新排列；

2、如果可以通过重新排列得到一个回文串，则游戏结束，当前操作的人获胜；

3、否则，当前操作的人必须删除字符串中的一个字符；

小红先手，两人都采用最优策略，问最后谁能获胜。

输入描述

第一行一个整数t，表示数据组数；

接下来t行，每行一个字符串s，仅包含小写学母，长度不超过100000。(1<t< 20)

输出描述

输出t行，每行一个字符串，小红获胜输出“red”，朋友获胜输出“friend”。

样例输入

3

aab

abc

abcd

样例输出

red

red

friend

提示:

第一组，小红可以重新排列得到回文串"aba"，获胜。

第二组，小红删除后，朋友无法获胜，朋友删除后只剩下一个字符，是回文串，小红获胜。

参考题解

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        scanner.nextLine(); // Consume the newline character

        while (T-- > 0) {
            String s = scanner.nextLine();
            int bs = 0;

            for (char ch : s.toCharArray()) {
                bs ^= 1 << (ch - 'a');
            }

            int m = Integer.bitCount(bs);

            if (m == 0 || (m & 1) == 1) {
                System.out.println("red");
            } else {
                System.out.println("friend");
            }
        }
    }
}

Python：

T = int(input())

for _ in range(T):
    s = input()
    bs = 0

    for ch in s:
        bs ^= 1 << (ord(ch) - ord('a'))

    m = bin(bs).count('1')

    if m == 0 or m % 2 == 1:
        print("red")
    else:
        print("friend")

第二题

题目：小红的二叉树

小红拿到一个奇怪的二叉树，如下图所示：

输入描述

第一层从左往右赋值，第二层从右往左赋值，第三层从左往右赋值.....以此类推。这个二叉树有无穷多层。

小红有t次询问，每次询问输入两个正整数x,y，她想知道x和y在二叉树上的路径长度是多少。你能帮帮她吗?

第一行输入一个正整数q，代表询问次数。接下来的q行，每行输入两个正整数x,y，代表一次询问。

输出描述

输出q行，每行输出一个整数，代表该次询问的答案。

样例输入

3

11 4

2 5

7 7

样例输出

5

3

0

参考题解

Java:

import java.util.Scanner;

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

        while (q-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            x = originId(x);
            y = originId(y);

            int result = solve(x, y);
            System.out.println(result);
        }
    }

    public static int bitCount(int x) {
        int cnt = 0;
        while (x != 0) {
            cnt++;
            x >>= 1;
        }
        return cnt;
    }

    public static int originId(int x) {
        int k = bitCount(x) - 1;
        if ((k & 1) == 0) {
            return x;
        } else {
            retu