笔试时间：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”：表示编号为 x 的城市与其右边的城市之间修建一条铁路。如果 x 右边没有城市或者已经修建了铁路，则无视该操作；- “Q x”：表示查询 x 往左边和往右边最远能到达的城市编号。你的任务是模拟以上操作，并对于每一条“Q x”操作，输出对应的答案。

输入描述

第一行输入两个正整数 n , T ；

接下来T行，每行输入形如题面中的其中一种。

1≤n≤10000, 1≤T≤200， 1≤x≤n

输出描述

对于每一个"Q x”操作，输出一行两个正整数，分别表示 x 往左边和往右边最远能到达的城市编号，中间用空格隔开。

样例输入

3 5

Q 2

L 2

Q 2

R 2

Q 2

样例输出

2 2

1 2

1 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,...an

b1,b2,...bn

c1,c2,...,cn

1≤n,ai,bi,ci,≤100000，bi≤ai

输出描述

输出一个整数表示最小的花费

样例输入

3

5 4 3

4 2 2

3 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);
    }
}