笔试时间：2023年04月15日

第一题

题目：字符串的前缀

现在有两个字符串S和T，你需要对S进行若干次操作，使得S是T的一个前缀（空串也是一个前缀）。每次操作可以修改S的一个字符，或者删除一个S末尾的字符。小团需要写一段程序，输出最少需要操作的次数。

输入描述

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

对于每一组数据输入两行仅包含小写字母的字符串S和T。

输出描述

对于每一组数据，输出一个整数，表示最少需要操作的次数。

样例输入

2

aba

abb

abcd

efg

样例输出

1

4

提示：

第一组数据，可以修改最后一个字母，使得S=abb，是T的一个前缀；第二组数据，需要将S整个串删除，操作次数为4。

参考题解

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    int C;
    cin >> C;
    cin.ignore(); // Ignore the newline after reading C

    for (int i = 0; i < C; ++i) {
        string S, T;
        getline(cin, S);
        getline(cin, T);

        int res = 0;
        int pos = 0;

        if (S.length() > T.length()) {
            res = S.length() - T.length();
            pos = T.length() - 1;
        } else {
            pos = S.length() - 1;
        }

        bool flag = false;

        while (pos >= 0) {
            if (!flag) {
                if (S[pos] == T[pos]) {
                    flag = true;
                } else {
                    res++;
                }
            } else {
                if (S[pos] != T[pos]) {
                    res++;
                }
            }

            pos--;
        }

        cout << res << endl;
    }

    return 0;
}

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

import java.util.Scanner;

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

        for (int i = 0; i < C; ++i) {
            String S = scanner.nextLine();
            String T = scanner.nextLine();

            int res = 0;
            int pos = 0;

            if (S.length() > T.length()) {
                res = S.length() - T.length();
                pos = T.length() - 1;
            } else {
                pos = S.length() - 1;
            }

            boolean flag = false;

            while (pos >= 0) {
                if (!flag) {
                    if (S.charAt(pos) == T.charAt(pos)) {
                        flag = true;
                    } else {
                        res++;
                    }
                } else {
                    if (S.charAt(pos) != T.charAt(pos)) {
                        res++;
                    }
                }

                pos--;
            }

            System.out.println(res);
        }
    }
}

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

C = int(input())
for _ in range(C):
    S = input()
    T = input()
    res, pos = 0, 0
    if len(S) > len(T):
        res = len(S) - len(T)
        pos = len(T) - 1
    else:
        pos = len(S) - 1 
    flag = False
    while pos >= 0:
        if not flag:
            if S[pos] == T[pos]:
                flag = True
            else:
                res += 1
        else:
            if S[pos] != T[pos]: res += 1
        pos -= 1
    print(res)

第二题

题目：小美分糖

某一天，小美从商店买了两种糖果，分别买了a个和b个，要分给班上n个小朋友。为了不浪费，每块糖果都得恰好分到一个小朋友。另外，两种糖果一起吃的话味道其实并不好，所以每一个小朋友都只能得到其中一种糖果。小美希望分得最少糖果的那个小朋友能得到尽量多的糖果。小美的任务是求得这个数量是多少。

输入描述

第一行一个正整数T，表示有T组数据。

对于每一组数据，输入一行n,a,b，中间用空格隔开。

1≤a,b≤10000,  2≤n≤a+b, 1≤T≤100

输出描述

对于每一组数据，输出仅一行一个整数，表示答案。

样例输入

2

5 2 3

4 7 10

样例输出

1

3

提示：

第一组数据，每个小朋友都恰好分得一个糖果；第二组数据，可以分成：（3个第一种，4个第一种，5个第二种，5个第二种），这样第一个小朋友分得最少，没有其他方案使得分得最少的那个小朋友的糖果数量更大。

参考题解

二分答案。

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

#include <iostream>
using namespace std;

bool check(long long x, long long n, long long a, long long b) {
    long long r1 = min(a, b);
    long long r2 = max(a, b);
    long long cnt = 1;
    r2 -= x;
    cnt += (r2 / x) + (r1 / x);
    return cnt >= n;
}

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

    for (int t = 0; t < T; ++t) {
        long long n, a, b;
        cin >> n >> a >> b;

        long long l = 0;
        long long r = max(a, b);

        while (l < r) {
            long long mid = (l + r + 1) >> 1;
            if (check(mid, n, a, b)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        cout << r << endl;
    }

    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static boolean check(long x, long n, long a, long b) {
        long r1 = Math.min(a, b);
        long r2 = Math.max(a, b);
        long cnt = 1;
        r2 -= x;
        cnt += (r2 / x) + (r1 / x);
        return cnt >= n;
    }

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

        for (int t = 0; t < T; ++t) {
            long n = scanner.nextLong();
            long a = scanner.nextLong();
            long b = scanner.nextLong();

            long l = 0;
            long r = Math.max(a, b);

            while (l < r) {
                long mid = (l + r + 1) >> 1;
                if (check(mid, n, a, b)) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }

            System.out.println(r);
        }
    }
}

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

T = int(input())

for _ in range(T):
    n, a, b = map(int, input().strip().split(" "))
    def check(x):
        r1, r2 = min(a,b), max(a,b)
        cnt = 1
        r2 -= x
        cnt += (r2 //x) + (r1 //x) 
        '''一个人分x  其他人x+1， 如果可以就ok'''
        return cnt >= n
        
            
    l, r = 0, max(a,b)
    while l < r:
        mid = (l + r + 1) >> 1
        if check(mid):l = mid
        else:  r = mid - 1
    print(r)

第三题

题目：交通规则

A国有n个城市，这n个城市排成一列，依次编号为1,2,3,...,n。一开始，这n座城市之间都没有任何交通路线，于是政府打算修建一些铁路来进行交通规划。接下来T天，每一天会进行如下操作的其中一种：- “L x”：表示编号为 x 的城市与其左边的城市之间修建一条铁路。如果 x 左边没有城市或者已经修建了铁路，则无视该操作；- “R x”：表示编号为