笔试时间：2024年09月29日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小红拿到了两个长度为n的、仅由小写字母组成的字符串s和t，她可以进行若干次操作：选择第一个字符串s的两个下标i和j满足|i-j|=k ，交换si和sj。小红想知道，自己能否在有限次数的操作内，使得s和t相等？

输入描述

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

每组询问输入三行：第一行是两个正整数n，k，代表字符串的长度和交换字符的距离，接下来的两行分别输入一个长度为n的、仅由小写字母组成的字符串，分别代表s和t。

50%的数据满足：1 ≤ q,n,k ≤ 100

100%的数据满足：1 ≤ q,n,k ≤ 2000

输出描述

对于每组询问，如果可以把s变成t，则输出"Yes”；否则输出"No"。

样例输入

2

2 1

ab

ba

3 2

abc

acb

样例输出

Yes

No

参考题解

简单题。检查 s 和 t 中相同下标组内的字符计数是否相同。如果所有组的字符计数相同，那么可以通过交换将 s 转换为 t，否则不行。

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

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

bool canTransform(string s, string t, int n, int k) {
    if (s.length() != t.length()) {
        return false;
    }

    vector<unordered_map<char, int>> sGroups(k);
    vector<unordered_map<char, int>> tGroups(k);

    for (int i = 0; i < n; i++) {
        sGroups[i % k][s[i]]++;
        tGroups[i % k][t[i]]++;
    }

    for (int i = 0; i < k; i++) {
        if (sGroups[i] != tGroups[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    int q;
    cin >> q;

    for (int query = 0; query < q; query++) {
        int n, k;
        cin >> n >> k;
        string s, t;
        cin >> s >> t;

        if (canTransform(s, t, n, k)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

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

import java.util.Scanner;
import java.util.HashMap;

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

        for (int query = 0; query < q; query++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            String s = scanner.next();
            String t = scanner.next();

            if (canTransform(s, t, n, k)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        scanner.close();
    }

    private static boolean canTransform(String s, String t, int n, int k) {
 
        if (s.length() != t.length()) {
            return false;
        }

        HashMap<Character, Integer>[] sGroups = new HashMap[k];
        HashMap<Character, Integer>[] tGroups = new HashMap[k];

        for (int i = 0; i < k; i++) {
            sGroups[i] = new HashMap<>();
            tGroups[i] = new HashMap<>();
        }

        for (int i = 0; i < n; i++) {
            sGroups[i % k].put(s.charAt(i), sGroups[i % k].getOrDefault(s.charAt(i), 0) + 1);
            tGroups[i % k].put(t.charAt(i), tGroups[i % k].getOrDefault(t.charAt(i), 0) + 1);
        }

        for (int i = 0; i < k; i++) {
            if (!sGroups[i].equals(tGroups[i])) {
                return false; 
            }
        }

        return true;
    }
}

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

def can_transform(s, t, n, k):
    if len(s) != len(t):
        return False

    s_groups = [{} for _ in range(k)]
    t_groups = [{} for _ in range(k)]

    for i in range(n):
        s_groups[i % k][s[i]] = s_groups[i % k].get(s[i], 0) + 1
        t_groups[i % k][t[i]] = t_groups[i % k].get(t[i], 0) + 1

    for i in range(k):
        if s_groups[i] != t_groups[i]:
            return False

    return True


def main():
    q = int(input())

    for _ in range(q):
        n, k = map(int, input().split())
        s = input().strip()
        t = input().strip()

        if can_transform(s, t, n, k):
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()

第二题

题目

小红准备进行一番基金操作来赚钱，她找到了一支基金，准备对这支基金进行一些操作。已知该基金每天的价格都会变化，小红每天可以花费当天的价格买入一笔基金，或者以当天的价格卖出一笔基金（前提是手上至少持有一笔基金）。小红有一个超能力，她可以直接预测到接下来的n天，每天基金价格的变化，但小红为了避免打草惊蛇，她的基金买卖有以下限制：每天最多买入/卖出一笔基金（例如手上如果有2笔基金，那么最多只能卖出1笔，另一笔只能等到以后再卖）。手上最多持有2笔基金。由于小红没有得知n天以后的情况，所以她计划在第n天时，手上为未持有基金的状态。小红想知道，自己在这n天中最多可以赚多少钱？假设小红的本金是足够多的，且初始状态是未购买基金。

输入描述

第一行输入一个正整数n，代表小红内幕消息得知的天数。

第二行输入n个正整数ai。代表第i天基金的价格。

1 ≤ n ≤ 100000

1 ≤ ai ≤ 10^9

输出描述

一个整数，代表最终小红能赚的最大钱数。

样例输入一

5

1 2 3 4 5

样例输出一

6

说明：第一天买入一笔，第二天买入一笔，第三天不操作，第四天卖出一笔，第五天卖出一笔，总共赚了6元。

样例输入二

4

4 2 3 1

样例输出二

1

说明：第一天不操作，第二天买入一笔，第三天卖出，第四天不操作。

参考题解

动态规划，买卖股票变体。f[i][j]：表示前 i 天，在手头上持有 j 笔基金的最大收益。j = 0：不持有基金。j = 1：持有1笔基金。j = 2：持有2笔基金。状态转移：如果选择买入基金，则状态从 j-1 转移到 j，收益减少当天的价格。如果选择卖出基金，则状态从 j+1 转移到 j，收益增加当天的价格。或者保持当前状态不变。

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

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10 ;
int n ;
int a[N] , f[N][3] ;

signed main()
{  
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
    
    memset(f , -0x3f , sizeof f) ;
    f[0][0] = 0 ;
    
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 0 ; j <= 2 ; j ++)
        {
            if(j - 1 >= 0)
                f[i][j] = max(f[i - 1][j - 1] - a[i] , f[i][j]) ;
            
            if(j + 1 <= 2)
                f[i][j] = max(f[i - 1][j + 1] + a[i] , f[i][j]) ;
            
            f[i][j] = max(f[i - 1][j] , f[i][j]) ;
        }
    }
    
    cout << f[n][0] ;
    
    return 0 ;
}

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

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner