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

第一题

题目：小红判断相等

小红现在有一个长度为n的字符串s和长度为n的数组 a，如果满足对于ai = aj，都有si = sj，并对于ai != aj，都有si != sj，则字符串和数组相等，请你告诉小红她的字符串和数组是否相等。

输入描述

一行一个整数t，表示有t组数据，对于每组数据：一行一个整数n，表示字符串和数组的长度；一行一个数组a，表示小红的数组；一行一个字符串s，表示小红的字符串，字符串只包含小写字母。

1<= t <= 100

1 <= n <= 1000

1 <= ai <= 50

输出描述

如果字符串和数组相等，输出”YES”，否则输出“NO"。

样例输入

2

3

1 2 2

acc

4

1 2 3 4

abcc

样例输出

YES

NO

参考题解

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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

bool check(const std::vector<int>& u, const std::vector<int>& v) {
    std::unordered_map<int, std::vector<int>> g;
    for (int i = 0; i < v.size(); ++i) {
        g[v[i]].push_back(i);
    }
    for (const auto& entry : g) {
        std::unordered_set<int> st;
        for (int x : entry.second) {
            st.insert(u[x]);
        }
        if (st.size() > 1) {
            return false;
        }
    }
    return true;
}

int main() {
    int T;
    std::cin >> T;
    for (int t = 0; t < T; ++t) {
        int n;
        std::cin >> n;
        std::vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> a[i];
        }
        std::string s;
        std::cin >> s;
        if (check(std::vector<int>(s.begin(), s.end()), a) && check(a, std::vector<int>(s.begin(), s.end()))) {
            std::cout << "YES" << std::endl;
        } else {
            std::cout << "NO" << std::endl;
        }
    }
    return 0;
}

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

import java.util.*;

public class Main {
    public static boolean check(List<Integer> u, List<Integer> v) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i = 0; i < v.size(); i++) {
            int x = v.get(i);
            if (!g.containsKey(x)) {
                g.put(x, new ArrayList<>());
            }
            g.get(x).add(i);
        }
        for (List<Integer> vertices : g.values()) {
            Set<Integer> st = new HashSet<>();
            for (int x : vertices) {
                st.add(u.get(x));
            }
            if (st.size() > 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        scanner.nextLine(); // Consume newline
        for (int t = 0; t < T; t++) {
            scanner.nextLine(); // Consume input line
            String[] aInput = scanner.nextLine().split(" ");
            List<Integer> a = new ArrayList<>();
            for (String num : aInput) {
                a.add(Integer.parseInt(num));
            }
            String s = scanner.nextLine();
            List<Integer> sList = new ArrayList<>();