笔试时间：2023年04月15日第一题题目：字符串的前缀现在有两个字符串S和T，你需要对S进行若干次操作，使得S是T的一个前缀（空串也是一个前缀）。每次操作可以修改S的一个字符，或者删除一个S末尾的字符。小团需要写一段程序，输出最少需要操作的次数。输入描述第一行一个正整数C，表示数据组数；对于每一组数据输入两行仅包含小写字母的字符串S和T。输出描述对于每一组数据，输出一个整数，表示最少需要操作的次数。样例输入2abaabbabcdefg样例输出14提示：第一组数据，可以修改最后一个字母，使得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输出描述对于每一组数据，输出仅一行一个整数，表示答案。样例输入25 2 34 7 10样例输出13提示：第一组数据，每个小朋友都恰好分得一个糖果；第二组数据，可以分成：（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”：表示编号为 x 的城市与其右边的城市之间修建一条铁路。如果 x 右边没有城市或者已经修建了铁路，则无视该操作；- “Q x”：表示查询 x 往左边和往右边最远能到达的城市编号。你的任务是模拟以上操作，并对于每一条“Q x”操作，输出对应的答案。输入描述第一行输入两个正整数 n , T ；接下来T行，每行输入形如题面中的其中一种。1≤n≤10000, 1≤T≤200， 1≤x≤n输出描述对于每一个"Q x”操作，输出一行两个正整数，分别表示 x 往左边和往右边最远能到达的城市编号，中间用空格隔开。样例输入3 5Q 2L 2Q 2R 2Q 2样例输出2 21 21 3提示：“Q 2”：一开始城市2没有与左边和右边联通，故最左和最右都是城市2；“L 2”：城市2与城市1联通；“Q 2”：此时最左能够到达城市1，最右能到达城市2；“R 2”：城市2与城市3联通：“Q 2”：此时最左能够到达城市1，最右能到达城市3；参考题解结合并查集+二分查找做法。C++：[此代码未进行大量数据的测试，仅供参考]#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;vector<int> fa;int find(int x) {    if (x == fa[x]) return x;    fa[x] = find(fa[x]);    return fa[x];}void unite(int x, int y) {    fa[find(x)] = find(y);}int main() {    int n, T;    cin >> n >> T;    fa.resize(n + 2);    for (int i = 1; i <= n; i++) {        fa[i] = i;    }    for (int i = 0; i < T; i++) {        string op;        int pos;        cin >> op >> pos;        if (op == "L") {            unite(pos, pos - 1);        } else if (op == "R") {            unite(pos, pos + 1);        } else {            int l = 1, r = pos;            while (l < r) {                int mid = (l + r) >> 1;                if (find(pos) == find(mid)) {                    r = mid;                } else {                    l = mid + 1;                }            }            int res1 = r;            l = pos, r = n;            while (l < r) {                int mid = (l + r + 1) >> 1;                if (find(pos) == find(mid)) {                    l = mid;                } else {                    r = mid - 1;                }            }            cout << res1 << " " << r << endl;        }    }    return 0;}Java：[此代码未进行大量数据的测试，仅供参考]import java.util.Scanner;public class Main {    static int[] fa;    public static int find(int x) {        if (x == fa[x]) return x;        fa[x] = find(fa[x]);        return fa[x];    }    public static void unite(int x, int y) {        fa[find(x)] = find(y);    }    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int T = scanner.nextInt();        fa = new int[n + 2];        for (int i = 1; i <= n; i++) {            fa[i] = i;        }        for (int i = 0; i < T; i++) {            String op = scanner.next();            int pos = scanner.nextInt();            if (op.equals("L")) {                unite(pos, pos - 1);            } else if (op.equals("R")) {                unite(pos, pos + 1);            } else {                int l = 1, r = pos;                while (l < r) {                    int mid = (l + r) >> 1;                    if (find(pos) == find(mid)) {                        r = mid;                    } else {                        l = mid + 1;                    }                }                int res1 = r;                l = pos;                r = n;                while (l < r) {                    int mid = (l + r + 1) >> 1;                    if (find(pos) == find(mid)) {                        l = mid;                    } else {                        r = mid - 1;                    }                }                System.out.println(res1 + " " + r);            }        }    }}Python：[此代码未进行大量数据的测试，仅供参考]n, T = map(int, input().split(" "))fa = [i for i in range(n+2)]def find(x):    if x == fa[x]: return x    fa[x] = find(fa[x])    return fa[x]def union(x, y):    fa[find(x)] = find(y)for _ in range(T):    line = input().strip().split(" ")    op, pos = line[0], int(line[1])    if op == 'L':        union(pos, pos - 1)    elif op == 'R':        union(pos, pos + 1)    else:        '''左边二分找到连通的最小值'''        l, r = 1,pos        while l < r:            mid = (l + r) >> 1            if find(pos) == find(mid): r = mid            else: l = mid + 1        res1 = r        l, r = pos, n        while l < r:            mid = (l + r + 1) >> 1            if find(pos) == find(mid): l = mid            else: r = mid - 1        print(str(res1) + " " + str(r))第四题题目：小美玩套娃小美最近喜欢上了玩套娃。具体的，小美有 n 个套娃，第 i 个套娃的大小为 ai，内部空间为 bi(bi≤ai)。对于两个套娃x,y， x能放入y中当且仅当ax≤by ，且放入后会占据 y 大小为 ax 的内部空间，即 y 的内部空间剩下 by-ax，每个套娃只能放在另外的一个套娃内，每个套娃内部也只能放一个套娃（当然内部放的这个套娃可以内部还有套娃）。显然套娃是套的越多越好，于是小美给每个套娃定义了一个价值 ci，如果套完之后套娃 i 还剩 k 的内部空间，小美需要付出ci*k 的花费，总花费为所有套娃的花费之和，现在小美想知道最小的花费为多少。输入描述第一行一个正整数 n ，表示套娃的个数接下来三行每行 n 个整数，分别为a1,a2,...anb1,b2,...bnc1,c2,...,cn1≤n,ai,bi,ci,≤100000，bi≤ai输出描述输出一个整数表示最小的花费样例输入35 4 34 2 23 2 1样例输出6提示：将第二个套娃放在第一个里面，第三个不动，这样第一个套娃剩 0 的空间，第二个剩 2，第三个剩 2。总花费为0*3+2*2+2*1=6 。可以证明这是花费最小的方案。参考题解C++：[此代码未进行大量数据的测试，仅供参考]#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {    int n;    cin >> n;    vector<int> a(n);    vector<int> b(n);    vector<int> c(n);    for (int i = 0; i < n; i++) {        cin >> a[i];    }    for (int i = 0; i < n; i++) {        cin >> b[i];    }    for (int i = 0; i < n; i++) {        cin >> c[i];    }    vector<vector<int>> taos1(n, vector<int>(4, 0));    vector<vector<int>> taos2(n, vector<int>(4, 0));    for (int i = 0; i < n; i++) {        taos1[i][0] = a[i];        taos1[i][1] = b[i];        taos1[i][2] = c[i];        taos1[i][3] = i;        taos2[i][0] = a[i];        taos2[i][1] = b[i];        taos2[i][2] = c[i];        taos2[i][3] = i;    }    sort(taos1.begin(), taos1.end(), [](vector<int>& x, vector<int>& y) {        return x[0] < y[0];    });    sort(taos2.begin(), taos2.end(), [](vector<int>& x, vector<int>& y) {        return x[2] < y[2];    });    long long res = 0;    int rborder = n - 1;    for (int i = n - 1; i >= 0; i--) {        int l = 0, r = rborder;        while (l < r) {            int mid = (l + r + 1) >> 1;            if (taos2[i][1] >= taos1[mid][0]) {                l = mid;            } else {                l = mid + 1;            }        }        if (taos1[r][3] == taos2[i][3]) {            r--;        }        if (taos2[i][1] < taos1[r][0]) {            break;        }        taos2[i][1] -= taos1[r][0];        rborder = r - 1;    }    for (int i = 0; i < n; i++) {        res += static_cast<long long>(taos2[i][1]) * taos2[i][2];    }    cout << res << endl;    return 0;}Java：[此代码未进行大量数据的测试，仅供参考]import java.util.Arrays;import java.util.Comparator;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];        int[] c = new int[n];        for (int i = 0; i < n; i++) {            a[i] = scanner.nextInt();        }        for (int i = 0; i < n; i++) {            b[i] = scanner.nextInt();        }        for (int i = 0; i < n; i++) {            c[i] = scanner.nextInt();        }        int[][] taos1 = new int[n][4];        int[][] taos2 = new int[n][4];        for (int i = 0; i < n; i++) {            taos1[i][0] = a[i];            taos1[i][1] = b[i];            taos1[i][2] = c[i];            taos1[i][3] = i;            taos2[i][0] = a[i];            taos2[i][1] = b[i];            taos2[i][2] = c[i];            taos2[i][3] = i;        }        Arrays.sort(taos1, Comparator.comparingInt(x -> x[0]));        Arrays.sort(taos2, Comparator.comparingInt(x -> x[2]));        long res = 0;        int rborder = n - 1;        for (int i = n - 1; i >= 0; i--) {            int l = 0;            int r = rborder;            while (l < r) {                int mid = (l + r + 1) >> 1;                if (taos2[i][1] >= taos1[mid][0]) {                    l = mid;                } else {                    l = mid + 1;                }            }            if (taos1[r][3] == taos2[i][3]) {                r--;            }            if (taos2[i][1] < taos1[r][0]) {                break;            }            taos2[i][1] -= taos1[r][0];            rborder = r - 1;        }        for (int i = 0; i < n; i++) {            res += (long) taos2[i][1] * taos2[i][2];        }        System.out.println(res);    }}