A. 字符串前缀

题意：

$T$ 组数据，每组数据给定两个串 $s$ 和 $t$。

有两种形式的操作：

  • 将 $s$ 串的末尾删除
  • 将 $s$ 串中任意一个字符修改为其他字符

问至少执行多少次操作，才能使得 $s$ 串是 $t$ 串的前缀。

数据范围：$1\leq T\leq 10, 1\leq |s|, |t|\leq 5\times 10^4$

题解：

本质上好像选择很多，其实没有多少选择。

  • 要么就将 $s[i]$ 修改成 $t[i]$ 。
  • 要么就将 s[|s|] 删除。

但是删除和修改的都是一次操作，不如将全部操作都设置为修改。

什么时候会有删除操作呢，当 $|s| > |t|$ 时，必须要删除 s 的末尾才能使得 s 的长度不大于 t ，从而 s 为 t 的前缀。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;
char s[N], t[N];
int ns, nt;
int n;

void solve() {
    scanf("%s%s", s + 1, t + 1);
    ns = strlen(s + 1), nt = strlen(t + 1);

    int ans = 0;
    if (ns > nt) ans += ns - nt, ns = nt;

    for (int i = 1; i <= ns; ++i)
        if (s[i] != t[i]) ans += 1;
    printf("%d\n", ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        solve();
    }
    return 0;
}

B. 分糖果

题意：

$T$ 组数据，每组数据有 $a$ 个口味 $A$ 的糖果和 $b$ 个口味 $B$ 的糖果，要分给 $n$ 个小朋友。

每个小朋友只能分到一种口味的糖果，为了公平，要尽可能使得每个小朋友获得的糖果都差不多，即希望获得最少糖果的小朋友获得的糖果尽可能多。

问获得最少糖果的小朋友获得的糖果数，最多是多少？

数据范围：$1\leq a, b\leq 10000, 2\leq n\leq a+b, 1\leq T\leq 100$

题解：

二分答案，O(1) check。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

T = int(input())
while T > 0:
    n, a, b = list(map(int, input().split()))

    def check(cnt):
        return a // cnt + b // 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(l)
    T -= 1

C. 交通规划

题意：

$m$ 次操作，$n$ 个城市。$n$ 个城市按照序号从左往右，即 $1$ 号城市是最左边，$n$ 号城市是最右边。

有如下三种操作：

  • L x 表示在编号为 x-1 和编号为 x 的城市之间建一条铁路。如果两者之间已经存在铁路，或者 x = 1 ，则此操作忽略。
  • R x 表示在编号为 x 和编号为 x + 1 的城市之间建一条铁路。如果两者之间已经存在铁路，或者 x = n ，则此操作忽略。
  • Q x 表示查询从 x 出发，可以到达的最左边的城市和最右边的城市。

数据范围：$1\leq n\leq 20000, 1\leq m\leq 200, 1\leq x\leq n$

题解： 并查集，两个城市建一条铁路相当于这两个城市处于同一个集合。这里需要构建两个合并数组，一个在合并时父节点总是编号更小的，一个在合并时父节点总是编号更大的。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int pL[N], pR[N];
int n, m;
char op[2];
int num;

int find(int p[], int x) {
    int root = x;
    while (root != p[root]) root = p[root];
    while (x != p[x]) {
        int nx = p[x];
        p[x] = root;
        x = nx;
    }
    return root;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) pL[i] = pR[i] = i;

    for (int i = 1; i <= m; ++i) {
        scanf("%s%d", op, &num);
        if (*op == 'L') {
            if (num == 1) continue;
            int pa = find(pL, num - 1), pb = find(pL, num);
            if (pa == pb) continue ;
            pL[pb] = pa;

            pa = find(pR, num - 1), pb = find(pR, num);
            pR[pa] = pb;
        } else if (*op == 'R') {
            if (num == n) continue ;
            int pa = find(pL, num), pb = find(pL, num + 1);
            if (pa == pb) continue ;
            pL[pb] = pa;

            pa = find(pR, num), pb = find(pR, num + 1);
            pR[pa] = pb;
        } else {
            printf("%d %d\n", find(pL, num), find(pR, num));
        }
    }

    return 0;
}

D. 俄罗斯套娃

题意： 有 $n$ 个俄罗斯套娃，第 $i$ 个俄罗斯套娃的大小为 $a_i$ ，内部空间为 $b_i$ ，有一个价值 $c_i$。 每个俄罗斯套娃的花费是 $c_i \times k$ ，其中 $k$ 是其内部空间的剩余大小。如果第 $j$ 个套娃的大小 $a_j$ 可以放在第 $k$ 个套娃内部，要求是 $a_j\leq b_k$。每个俄罗斯套娃内只能有放一个其他的俄罗斯套娃。问将 $n$ 个俄罗斯套娃都套上的总花费多少。

数据范围：$1\leq n, a_i, b_i, c_i\leq 100000, b_i\leq a_i$

题解： 刚开始看错题，发现这笔试题怎么出个NPC的。后来发现每个俄罗斯套娃内部至多只能放一个其他的俄罗斯套娃。 贪心考虑，因为剩余的俄罗斯套娃的价值 $c_i$ 越小，花费也就越少。因此按照 $c_i$ 对每个俄罗斯套娃从大到小排序，考虑排序后的俄罗斯套娃，第 $i$ 个俄罗斯套娃的内部空间为 $b_i$ ，故找到最大的，大小 $a_j$ 小于等于 $b_i$ 的俄罗斯套娃 $j$ 放到$i$ 的内部即可。

这里需要注意到，自己不能套进自己。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

struct Node {
    int a, b, c, id;
}q[N];

struct Val {
    int a, id;
    bool operator< (const Val& A) const {
        return a < A.a;
    }
};
multiset<Val> A;

int n;

int main()
{
    long long ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &q[i].a), q[i].id = i;
    for (int i = 1; i <= n; ++i) scanf("%d", &q[i].b);
    for (int i = 1; i <= n; ++i) scanf("%d", &q[i].c), ans += 1ll * q[i].c * q[i].b;

    sort(q + 1, q + n + 1, [](const Node& A, const Node& B) {
        return A.c > B.c;
    });

    // 按照 c 从大到小去考虑，对于每个 c ，去考虑小于等于其 space 的还可以使用的套娃最大是多少
    for (int i = 1; i <= n; ++i) A.insert({q[i].a, q[i].id});

    for (int i = 1; i <= n; ++i) {
        // 找到小于等于 q[i].b 的最大的 q[j].a，但是 j != i
        auto it = A.upper_bound({q[i].b, 0});
        if (it == A.begin()) continue ;
        it--;
        if (it->id == q[i].id) {
            if (it == A.begin()) continue ;
            it--;
        }

        ans -= 1ll * q[i].c * (it->a);
        A.erase(it);
    }

    printf("%lld\n", ans);

    return 0;
}