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

第一题

题目

游游拿到了一个排列a。她希望你构造一个长度相等的排列b，满足ai≠bi且b的字典序尽可能小。你能帮帮她吗？所谓排列，即长度为n的数组，其中 1到n每个正整数都恰好出现了 1次。

输入描述

第一行输入一个正整数n，代表排列a的长度。

第二行输入几个正整数ai，代表游游拿到的排列。

2<=n<=10^5

输出描述

n个正整数bi，代表构造的排列。

样例输入

3

1 2 3

样例输出

2 3 1

参考题解

贪心。

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

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    std::vector<int> b(n);

    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        b[i] = i + 1;
    }

    for (int i = 0; i < n - 1; i++) {
        if (b[i] == a[i]) {
            std::swap(b[i], b[i + 1]);
        }
    }

    if (a[n - 1] == b[n - 1]) {
        std::swap(b[n - 1], b[n - 2]);
    }

    for (int i = 0; i < n; i++) {
        std::cout << b[i];
        if (i < n - 1) {
            std::cout << ' ';
        } else {
            std::cout << std::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();
        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            b[i] = i + 1;
        }

        for (int i = 0; i < n - 1; i++) {
            if (b[i] == a[i]) {
                int temp = b[i];
                b[i] = b[i + 1];
                b[i + 1] = temp;
            }
        }

        if (a[n - 1] == b[n - 1]) {
            int temp = b[n - 1];
            b[n - 1] = b[n - 2];
            b[n - 2] = temp;
        }

        for (int i = 0; i < n; i++) {
            System.out.print(b[i]);
            if (i < n - 1) {
                System.out.print(" ");
            } else {
                System.out.println();
            }
        }
    }
}

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

n = int(input())
a = list(map(int, input().split()))
b = list(range(1, n + 1))

for i in range(n - 1):
    if b[i] == a[i]:
        b[i], b[i + 1] = b[i + 1], b[i]

if a[-1] == b[-1]:
    b[-1], b[-2] = b[-2], b[-1]

print(*b)

第二题

题目

小红拿到了一个字符串s。她可以进行任意次以下操作：选择字符串中的一个字母ch1和任意一个字母ch2 (ch2可以不在字符串中出现)，将字符串S中的所有ch1变成ch2。小红想知道，自己能否通过一些操作将字符串s变成t？

输入描述

第一行输入一个正整数q，代表查询次数；

对于每次查询输入2行：第一行输入一个字符串s；第二行输入一个字符串t；

1<=q<=10，保证s和t的长度相同，且均由小写字母组成。长度不超过10000。

输出描述

输出q行，每行输出一个字符串代表答案。如果可以把s变成t，则输出Yes。否则输出No。

样例输入

3

ab

ba

abc

aaa

aaaa

abcd

样例输出

Yes

Yes

No

参考题解

字符串的转化，需要用到t不存在的那一个字符作为媒介才能够顺利进行各种转换。

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

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

bool isPossibleToTransform(string s, string t) {
    // Create a map to store the positions of each character in s
    map<char, vector<int> > charPositions;

    // Populate charPositions
    for (int i = 0; i < s.size(); i++) {
        charPositions[s[i]].push_back(i);
    }

    // Create a set of characters from string t
    set<char> uniqueChars(t.begin(), t.end());

    // If t contains all 26 letters, s must be equal to t
    if (uniqueChars.size() == 26) {
        return s == t;
    }

    // Check if characters in s can be transformed into t
    for (auto &[character, positions] : charPositions) {
        for (int i = 0; i + 1 < positions.size(); i++) {
            // If there are different characters at the same position in t, return false
            if (t[positions[i + 1]] != t[positions[i]]) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        cout << (isPossibleToTransform(s, t) ? "Yes" : "No") << endl;
    }
    return 0;
}

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

import java.util.*;
import java.io.*;

public class Main {
    public static boolean isPossibleToTransform(String s, String t) {
        Map<Character, List<Integer>> charPositions = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char character = s.charAt(i);
            charPositions.computeIfAbsent(character, k -> new ArrayList<>()).add(i);
        }

        Set<Character> uniqueChars = new Has