编程练习题集锦

第一章 · 语言基础

【1】小明和完美序列

【题目描述】

小明又新学了一个概念，叫做完美序列。一个仅包含数字序列被称为完美序列，当且仅当数字序列中每个数字出现的次数等于这个数字。比如(1)，(2 2 3 3 3)。空序列也算。现在小明得到了一个数字序列，他想知道最少要删除多少个数字才能使得这个数字序列成为一个完美序列。

【输入输出描述】

输入格式：两行输入，第一行一个数字整数 n，表示数字序列中数字的个数。第二行包括 n 个整数，是数字序列中的具体数字。

输出格式：一行输出，表示最小要删除的数字个数。

【题解】

首先我们先要清楚如果计算最小要删除的数字个数：当某个数 k，输入个数为 m 时，不难发现，若是 m 大于等于 k，则需删除 m-k 个数；反之若是 m 小于 k，则需删除 m 个数。

明白这一点后，我们考虑如何记录下这个数字序列的信息。这里我们给出两种做法，分别是 1、使用复合结构，在记录下数字的同时记录下该数字出现的次数；2、使用数组存储数字，全部存储后一次遍历根据每个不同的数的出现次数来决定输出的多少。

先看第一种想法：我们想到在 STL 中的 map 具有存储一对数的功能，我们使用 map<int,int>，第一个数表示数字的大小，第二个数表示该数出现的次数。每当输入一个数 x，我们就使用 mp[x]++ 将该数的出现次数自增。最终在输入结束后就同步记录下了数字和其出现次数。接着，根据之前的思路完成最小删除个数的计算即可。

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
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
vector<int> vc;
int main()
{
    int n = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        int x = 0;
        cin >> x;
        if(!mp.count(x)){
            mp.insert(make_pair(x, 1));
            vc.push_back(x);
        }
        else{
            mp[x]++;
        }
    }
    int ans = 0;
    for(auto it : vc){
        if(mp[it] < it){
            ans += mp[it];
        }
        else if(mp[it] > it){
            ans += mp[it] - it;
        }
    }
    cout << ans << '\n';
    return 0;
}

第二种想法：我们可以仅用最简单的数据结构数组来记录所有输入的数字，接着需要使用排序函数将其从小到大排序，这样就方便了之后我们统计每个数字的出现次数。然后，我们遍历整个数组，使用 count 记录每个不同的数的出现次数。如果当前遍历到的数和数组中下一个数不一样，证明它是这种数中的最后一个，此时我们就可以按照上面的计算方式计算该数对最终结果的贡献次数，计算后将 count 赋零。如果它和数组中下一个数一样，那么我们就可以将 count 加 1，并继续遍历下一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, res = 0;
    cin >> n;
    vector<int> num(n);
    for (int i = 0; i < n; ++i) cin >> num[i]; // 读入数据
    sort(num.begin(), num.end()); // 从小到大排序
    int number, i = 0, count = 0;
    while (i < num.size()) {
        number = num[i];
        count++;
        if (number != num[i+1]) {
        res += count >= number ? count - number : count;
        count = 0; // count归零
        }
        i++;
    } 
    cout << res;
    return 0;
}

【2】众数的最大数目

【题目描述】

小蓝有一个长度为 n 的数组 a，现在对于每一个 a[i]，小蓝可以选择下面三种操作之一：

  • a[i]=a[i-1]
  • a[i]=a[i+1]
  • a[i]=a[i]

小蓝想知道她如果把每一个 a[i] 都操作之后，数组众数的数目最大是多少。

【输入输出描述】

输入格式：第一行输入一个整数，代表 n；第二行输入 n 个整数，代表 a[1],a[2],a[3],...,a[n] 。

输出格式：输出一行一个整数，代表众数的最大数目。

【题解】

本题我们采用逆向思维。题干中要求我们找出众数的最大数目，实际上就是要求我们找出一个数，它可以由最多的数经过操作之后得到。用这种想法，我们就可以使用一个 map<int, int> 容器来记录下每个数可以由几个数操作得到。例如：若输入一行整数为 1,2,3，则 2 可以由3个数操作得到。剩下的就只是简单的实现上述思想的过程，这里不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	map<int, int> mp;
	int n; cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) cin >> nums[i];
	for (int i = 0; i < n; i++) {
		mp[nums[i]-1]++; mp[nums[i]]++; mp[nums[i]+1]++;
	}
	int maxn = 0;
	map<int, int>::iterator m;
	for (m = mp.begin(); m != mp.end(); ++m) maxn = max(maxn, m->second);
	cout << maxn << endl;
	return 0;
}

第二章 · 基础算法

【1】小蓝的漆房

【题目描述】

小蓝有一个漆房，其中有一条走廊需要油漆，走廊两旁有许多相邻的房子，每间房子最初被涂上一种颜色。现在希望将整个走廊涂成一种颜色，而小蓝每天只能涂一段长为 k 的区间。对于每个区间可以选择将其中的房子涂上任何一种颜色，或者保持原来的颜色不变。现在他想知道一共需要多少天才能将整个走廊涂好。

【输入输出描述】

输入格式：第一行包含一个整数 t(1<=t<=100)，表示测试用例的数量。每个测试用例的第一行包含两个整数 n 和 k ，第二行包含 n 个整数 a[1], a[2], ..., a[n]，分别表示每个房子最初的颜色。其中保证测试用例中 n 的总和不超过 10000。

输出格式：对于每个测试用例，输出一个整数，表示小蓝需要油漆的最少天数。

【题解】

本题使用基础算法中的枚举思想，其中最重要的一点是如何判断出最少的天数。我们可以考虑对每一种颜色进行枚举，假设当前枚举的颜色为 A。从走廊的一端开始，如果两旁的房子颜色为 A，那么不需要修改，继续判断下一个房子。如果两旁的房子颜色不是 A，那么需要修改，由于一次修改的区间范围固定，且在到此之前已经完成所有需要修改的部分，因此需要修改的天数加 1。最终，当到达走廊另一端时结束判断。用同样的方法将所有的颜色进行判断之后取其中需要天数最少的一种输出即可。

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int cnt; cin >> cnt;
  while (cnt--) {
    int number, len; cin >> number >> len;
    vector<int> por(number);
    set<int> s;
    for (int i = 0; i < number; ++i) {
      cin >> por[i];
      s.insert(por[i]);
    }
    int min_day = 10000;
    for (auto& x : s) {
      int day = 0;
      for (int j = 0; j < number; ++j) {
        if (por[j] == x) continue;
        day += 1;
        j += len - 1;
      }
      min_day = min(min_day, day);
    }
    cout << min_day << endl;
  }
  return 0;
}

【2】大石的搬运工

【题目描述】

在一次游戏中，玩家需要操作一排 n 堆石头，进行 n-1 轮游戏。每一轮，玩家可以选择一堆石头，并将其移动到任意位置。在 n-1 轮移动结束时，要求将所有的石头移动到一起即为成功。移动的费用为石头的重量乘以移动的距离，例如：如果一堆重量为 2 的石头从位置 3 移动到位置 5，那么费用为 2*(5-3)=4。请计算出所有合法方案中，将所有石头移动到一起的最小费用。可能有多堆石头在同一个位置上，但是一轮只能选择移动其中一堆。

【输入输出描述】

输入格式：第一行一个整数 n，表示石头的数量。接下来 n 行，每行两个整数 w[i] 和 p[i]，分别表示第 i 堆石头的重量和初始位置。

1
2
3
4
3
2 3
3 1
1 5

输出格式：输出一个整数，表示最小的总移动费用。

1
8

【题解】

在这个问题中，我们首先需要明确移动的费用总和与移动的顺序无关，因此只需要考虑最后的位置即可。接着我们需要分析如果放置石头才使费用总和最小。这里我们可以对于每堆石头，我们都计算它被移动到目标位置的费用，但由于数据范围较大，因此采用前缀和的思想。

我们可以先将所有石头按照位置排序，然后计算每个石头移动到任意位置的费用，再利用前缀和的思想将这些费用累加起来。具体地，我们可以定义两个数组 pre[] 和 nex[]，其中 pre[i] 表示前 i 个石头都移动到第 i 石头所在位置的总费用，nex[i] 表示第 i 个石头之后的所有石头都移动到第 i 个石头所在的位置的总费用。这样，对于石头，我们就可以在 O(1) 的时间内算出所有石头都移动到它的位置的总费用。

分析时间复杂度：排序算法时间复杂度为 O(nlogn)，计算 pre 和 nex 的时间复杂度为 O(n)，查找最小值的时间复杂度为 O(n)，所以总时间复杂度为 O(nlogn)。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n; cin >> n;
    pair<int, int> s[N];
    for (int i = 1; i <= n; ++i) {
        cin >> s[i].second >> s[i].first;
    }
    sort(s + 1, s + n + 1);
    // 前面的石头和
    ll pre[n + 2] = {0};
    ll wei = 0;
    for (ll i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1];
        pre[i] += wei * (s[i].first - s[i-1].first);
        wei += s[i].second;
    }
    // 后面的石头和
    ll nex[n + 1] = {0};
    ll iew = 0;
    for (ll i = n; i >= 1; --i) {
        nex[i] = nex[i + 1];
        nex[i] += iew * (s[i+1].first - s[i].first);
        iew += s[i].second;
    }
    // 计算总和
    ll min_dis = 1e18;
    for (ll i = 1; i <= n; ++i) {
        min_dis = min(min_dis, pre[i] + nex[i]);
    }
    cout << min_dis;
    return 0;
}

【3】最大数组和

【题目描述】

小明是一名勇敢的冒险家，现在他有一堆宝石。但是宝石会随着时间失去价值，因此他需要用规定次数对它们进行处理。他有两种处理方式：

  • 选出两个最小的宝石，并将它们从宝石组中删除。
  • 选出最大的宝石，并将它从宝石组中删除

现在，给你小明手上的宝石，请你告诉他在规定次数内，最大化宝石的总价值是多少。

【输入输出描述】

输入格式：第一行包含一个整数 t，表示数据组数。

对于每组数据，第一行包含两个整数 n 和 k，表示宝石的数量和规定的处理次数。

第二行包含 n 个整数 a[1], a[2], ..., a[n]，表示每个宝石的价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
6
5 1
2 5 1 10 6
5 2
2 5 1 10 6
3 1
1 2 3
6 1
15 22 12 10 13 11
6 2
15 22 12 10 13 11
5 1
999999996 999999999 999999997 999999998 999999995

输出格式：对于每组数据，输出一个整数，表示在规定次数内，最大化宝石的总和。

1
2
3
4
5
6
21
11
3
62
46
3999999986

【题解】

这道题目的题意具有一定迷惑性，我们需要仔细思考这个过程。我们总共需要处理 k 次，假如用贪心的想法，我们每次比较最小的两块宝石和与最大的宝石的价值，我们会发现对于如下情况：要求处理 2 次，数据为：10, 11, 14, 15, 22，我们会将 10, 11 以及 22 去除。但是实际上最好的处理方式是去除 15, 21 。因此这道题目不能用贪心的想法来解决。

我们应该对于这堆宝石升序排序后，对于规定次数 k 进行遍历，每次查看去除前 2 * i 个宝石和后 k - 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
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long a[N], prefix[N];

int main() {
    int t; cin >> t;
       for(int y=0;y<t;y++) {
        int n, k;
        cin >> n >> k;// 读取数组的长度 n 和选择的元素数量 k。
        for (int i = 1; i <= n; i++)
        cin >> a[i];// 读取数组 a 的元素。
        sort(a + 1, a + 1 + n);// 对数组 a 进行升序排序。
        
        for (int i = 1; i <= n; i++){
        prefix[i] = prefix[i - 1] + a[i];}// 计算数组 a 的前缀和，存储在数组 prefix 中

        long long ans = 0;

        for (int i = 0; i <= k; i++) {
            long long cha = (prefix[n - (k-i)] - prefix[2 * i]);
            // 计算选择了 k-i 个最大元素后，去掉了 2*i 个最小元素的情况下的和。
            //中 i 表示已选择的最小元素的数量
            ans = max(ans, cha);
            // 更新 ans，保存当前的最大和。
        }
        cout << ans << endl;
    }

    return 0;
}

【4】商品储存管理

【题目描述】

现在在一个仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量为 0。

现在管理团队设计了 m 个操作，每个操作涉及一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L, R]）。执行这些操作时，区间内商品数量增加 1，然而，在某些情况下管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在管理团队需要一个评估机制，用来确定如果某一个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，每个操作未执行时，库存量为 0 的商品的种类数。

【输入输出描述】

输入格式：第一行包含两个整数 n 和 m，分别表示商品的种类数和操作个数。

接下来的 m 行，每行包含两个整数 L 和 R，表示一个操作设计的商品区间。

输出格式：输出共 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。

对于所有评测用例：1<=n, m<=3*10^5; 1<=L<=R<=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
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m; cin >> n >> m; // 读入，数据不大用int
  int goods[n + 1] = {0};

  vector<pair<int, int>> operate(m);
  for (int i = 0; i < m; i++) {
    int L, R; cin >> L >> R;
    operate[i] = make_pair(L, R);
  }

  for (int i = 0; i < m; ++i) {
    goods[operate[i].first]++;
    if ((operate[i].second + 1) <= n) goods[operate[i].second + 1]--; 
  }

  int sum = 0, num = 0;
  for (int i = 0; i < m; ++i) {
    goods[operate[i].first]--;
    if ((operate[i].second + 1) <= n) goods[operate[i].second + 1]++;
    for (int i = 1; i <= n; ++i) {
      sum += goods[i];
      if (sum ==0) num++;
    }
    cout << num << endl;
    sum = 0; num = 0;
    goods[operate[i].first]++;
    if ((operate[i].second + 1) <= n) goods[operate[i].second + 1]--;
  }
  return 0;
}

我们仔细思考会发现，这里的商品库存最小就是 0。如果减少一个操作后，该商品数量为 0，那么在减少操作之前该商品数量要么是 0，要么是 1，如果大于或等于 2，那么这个商品就决不可能通过减少一次操作使得库存量为 0。有了这样的想法，我们就可以通过差分数组还原出原数组，此时求出数量为 0 的商品个数。

同时，我们使用一个前缀和数组 one[] 维护在前 i 个商品中经过所有操作后商品数为 1 的个数。那么假设某个操作区间为 [L, R] ，减少该操作后，商品数为 0 的个数增加 one[R] - one[L - 1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n , m , zero , a[N] , l[N] , r[N] , one[N];

int main(){
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i ++){ //  差分数组记录操作
        cin >> l[i] >> r[i];
        a[l[i]] ++ , a[r[i] + 1] --;
    }
    for(int i = 1 ; i <= n ; i ++) a[i] += a[i - 1]; // 恢复原数组
    for(int i = 1 ; i <= n ; i ++){ // 构造前缀和数组one[]，并统计商品数为 0 的个数
        one[i] = one[i - 1] + (a[i] == 1);
        zero += (a[i] == 0);
    }
    // 计算每次减少一个操作后商品数为 0 的个数
    for(int i = 1 ; i <= m ; i ++) cout << one[r[i]] - one[l[i] - 1] + zero << '\n';
    return 0;
}

【5】四个瓷瓶的神秘游戏

【题目描述】

在一座寺庙中，有四个精美的瓷瓶，每个瓷瓶中都装有神秘的珍珠。珍珠的数量可以衡量寺庙的强大。寺庙的主持现在可以做出以下操作：

  • 选择一个瓷瓶，将其中的珍珠数量增加 2 个，同时将其它三个瓷瓶中的珍珠各减少 1 个。这个操作只有在其余三个瓷瓶中珍珠数量大于零时才能进行。

主持的目标是使得四个瓷瓶中最多珍珠的数量尽可能大。请你计算通过如上操作，四个瓷瓶中最多珍珠的数量最大可以是多少。

【输入输出描述】

输入格式：输入的第一行包含四个非负整数，分别代表四个瓷瓶中珍珠的初始数量，输入的四个整数的范围都在区间 [0, 2*10^9]中。

1
3 3 3 3

输出格式：输出一行一个整数，表示主持通过操作后，四个瓷瓶中最多珍珠的数量最大可以是多少。

1
9

【题解】

本题，我们首先给出基本想法：对于初始数量最多的瓷瓶每次操作增加2，其余瓷瓶每次操作减去1。直至最后，初始数量最少的瓷瓶中珍珠数量为0时结束操作。但显然这样不是最多的，此时我们可以将数量为0的瓷瓶进行一次操作使其数量增加2，其余瓷瓶数量减去1。再进行两次操作使其数量重新变为0，初始数量最多的瓷瓶增加4。在这一过程中，初始数量最多的瓷瓶内珍珠增加3，另外两个瓷瓶中珍珠减去3。

重复以上过程即可完成本题。但是最终数量第二少的瓷瓶中可能还剩余1颗珍珠或2颗珍珠。如果是一颗珍珠，此时再进行上述操作，初始数量最多的瓷瓶中珍珠数量会减少，因此不再进行操作。如果是两颗珍珠，此时再进行上述操作，初始数量最多的瓷瓶中珍珠数量可以增加1，因此可以进行操作。

但还有一种情况，如果四个瓷瓶中珍珠数量为 a a a 0形，那么经过尝试会发现最大珍珠数量为2*a，而不是通过我们上述操作得到的最大数量。

有了以上想法，我们就可以写出相应的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll num[4] = {0};
int main() {
  cin >> num[0] >> num[1] >> num[2] >> num[3];
  sort(num, num + 4);
  if (num[0] == 0 && num[1] == num[2] && num[2] == num[3]) {
      cout << num[3] * 2;
  }
  else {
    num[3] += 2 * num[0];
    num[1] -= num[0];
    if (num[1] % 3 != 2) cout << num[3] + num[1] / 3 * 3;
    else cout << num[3] + num[1] / 3 * 3 + 1;
  }
  return 0;
}

第三章 · 搜索

【1】特殊的多边形

【题目描述】

假设一个 n 边形 n 条边为 a1,a2,a3,...,an，定义该 n 边形的值 v=a1*a2*a3*...*an。定义两个 n 边形不同是指至少有一边的长度在一个 n 边形中有使用而另一个 n 边形没有用到，如 (3,4,5,6) 和 (3,5,4,6) 是两个相同的 n 边形，(3,4,5,6) 和 (4,5,6,7) 是两个不同的 n 边形。

现在有 t 和 n ，表示 t 个询问并且询问的是 n 边形，每个询问给定一个区间 [l,r]，问有多少个 n 边形的值（要求所有边长度各不相同）在该区间范围内。

【输入输出描述】

输入格式：第一行包含两个正整数 t,n，表示有 t 个询问，询问的是 n 边形。接下来 t 行，每行有两个空格隔开的正整数 l, r ，表示询问区间 [l, r]。

1
2
3
4
5
4 3
1 10
30 50
60 200
200 400

输出格式：输出共 t 行，第 i 行对应第 i 个查询的 n 边形个数。

1
2
3
4
0
1
18
32

对于所有评测用例：1<=t<=1e5, 3<=n<=10, 1<=l<=r<=1e5。

【题解】

本题我们采用搜索算法并使用剪枝优化。首先，由于有多次查询，我们不妨将所有乘积可能的情况都计算出来，从而方便最后的询问。由此，我们的搜索过程便是对于乘积进行搜索，而利用 DFS，我们得到的 n 元组是递增的，每一次搜索可以计算当前这个位置的上限，并记录当前所有边的乘积，因为乘的越多数字越大，当乘积大于 1e5 时直接返回。同时记录以下 n-1 条边的长度和 sum，最后一条边必须小于 sum。最后用前缀和快速求和查询。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n; // 查找的是n边形
int cnt[N], prefix[N];
void DFS(int dep, int st, int mul, int sum) {
    if (mul > 1e5) return; // 剪枝1：边乘积不大于1e5
    if (dep == n + 1) {
        cnt[mul] += 1;
        return;
    }

    int up = pow(1e5 / mul, 1.0 / (n + 1 - dep)) + 1; // 剪枝2：在对应乘积要求下下一条边的最大值

    for (int i = st + 1; i < (dep == n ? min(sum, up) : up); i++) {
        DFS(dep + 1, i, mul * i, sum + i);
    }
}

int main() {
    int t; cin >> t >> n;
    DFS(1, 0, 1, 0);
    for (int i = 1; i <= 1e5; i++) prefix[i] = prefix[i - 1] + cnt[i];

    while (t--) {
        int l, r; cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
    return 0;
}

【2】串变换

【题目描述】

有两个长度为 n 的数字字符串 S 和 T。一共有 k 个操作，操作只可能是以下两种类型：

  • 1 x v 表示将 S[x] 变为 (S[x] + v) % 10；
  • 2 x y 表示交换 S[x] 和 S[y]。

你可以挑选出任意个操作，以任意顺序执行，但是每个操作最多只能执行一次，如果可以将 S 串变为 T 串，则输出 Yes，反之输出 No。

【输入输出描述】

输入格式：第一行输入一个正整数 n，表示字符串 S 和 T 的长度。第二行输入一个长度为 n 只由数字构成的字符串 S。第三行输入一个长度为 n 只由数字构成的字符串 T。第四行输入一个正整数 k，表示操作的数量。接下来 k 行，每行三个整数，其中第 i 行表示第 i 种操作的三个参数 op[i], x[i], y[i]。

1
2
3
4
5
6
7
5
01012
10103
3
2 0 1
2 3 2
1 4 1

输出格式：一行一个字符串，如果通过操作可以使 S 串和 T 串相等，则输出 Yes，反之则输出 No。

1
Yes

对于所有评测用例：1<=n<=10, 1<=k<=7, 1<=op[i]<=2, 0<=x[i],y[i]<n。

【题解】

这道题目，我们不难想到全排列是一种解决方法。因为，第一种方法就是直接使用全排列函数，遍历所有可能的操作方法，如果找到一种成立方案则返回 Yes，反之返回 No。

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
#include <bits/stdc++.h>
using namespace std;
string s, t;
int n, k, ans;
vector<vector<int>> v(10, vector<int>(5));
int main() {
    cin >> n;
    cin >> s >> t;
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    sort(v.begin() + 1, v.end());
    do {
        string s1 = s;
        for (int i = 1; i <= k; i++) {
            if (v[i][0] == 1) {
                int temp = s1[v[i][1]] - '0';
                temp = (temp + v[i][2]) % 10;
                s1[v[i][1]] = char(temp + '0');
            } else
                swap(s1[v[i][1]], s1[v[i][2]]);
            
            if (s1 == t) {
                cout << "Yes";
                return 0;
            }
        }
    } while (next_permutation(v.begin() + 1, v.end()));
    cout << "No";
    return 0;
}

另一种方法其实就是将全排列的思想用到 DFS 中，即利用递归过程实现全排列。每一次完成一种操作后递归选择下一个操作，直至实现最终效果。

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
#include <bits/stdc++.h>
using namespace std;
struct Data {  //记录三个数据类型
  int ops, x, y;
};
string postion(int &id, int &x, int &y, string s) {  //执行修改，返回修改完成后的串
  if (id == 1) s[x] = (s[x] - '0' + y) % 10 + '0';
  else swap(s[x], s[y]);
  return s;
}
bool vis[10];  //状态数组
bool dfs(vector<Data>& arr, string s1, string &s2) {
  if (s1 == s2) return true;  //每一次询问，如果相等则立即返回
  for (int i = 0; i < arr.size(); i++) {   //参考全排列，枚举每一个，拿第一个没有使用过的状态
      if (vis[i]) continue; //跳过使用过的状态
      vis[i] = true;   //标记为使用
      string temp = s1;  //记录开始时s1的串
      s1 = postion(arr[i].ops, arr[i].x, arr[i].y, s1);  //执行对s1的修改
      if (dfs(arr, s1, s2)) return true;  //递归过程，如果找到则快速返回
      vis[i] = false;   //回溯过程，标记为未使用
      s1 = temp;  //将s1变成原来的串
  }
  return false; 
}
int main() {
  int n; cin >> n;
  string s1, s2;
  cin >> s1 >> s2;
  if (s1 == s2) cout << "Yes" << endl;
  int k; cin >> k;
  vector<Data> arr(k);
  for (int i = 0; i < k; i++) {
      cin >> arr[i].ops >> arr[i].x >> arr[i].y;
  }
  if (dfs(arr, s1, s2)) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

【3】团建

【题目描述】

小蓝和小光在玩一个游戏，两个分别拿到一棵大小为 n 和 m 的树，树上的每一个结点上面都有一个正整数权值。两人需要从各自树上的根结点出发走向某个叶结点，这会形成一个正整数序列，两人的最长公共前缀即为他们的得分。给出两棵树，请计算两个人最多的得分是多少？

【输入输出格式】

输入格式： 输入的第一行包含两个正整数 n, m，用一个空格分隔。

第二行包含 n 个正整数，相邻整数之间用一个空格分隔，其中 c[i] 表示第一棵树结点 i 上的权值。

第三行包含 m 个正整数，相邻整数之间用一个空格分隔，其中 d[i] 表示第二棵树结点 i 上的权值。

接下来 n-1 行，每行包含两个正整数 u ，v，表示第一棵树中包含一条 u 和 v 之间的边。

接下来 m-1 行，每行包含两个正整数 u ，v，表示第二棵树中包含一条 u 和 v 之间的边。

1
2
3
4
5
6
7
8
9
10
5 4
10 20 30 40 50
10 40 20 30
1 2
1 3
2 4
3 5
1 2
1 3
3 4

输出格式： 输出一行包含一个整数表示答案。

1
2

【题解】

这同样也是一道搜索问题，但特殊之处在于它需要同时对两棵树进行搜索，这样才能使时间利用最大化。也就是说，我们从根结点开始，依次搜索两棵树相应的结点。如果这两个结点权值相同，我们就可以认为到目前为止两棵树搜索结果的前缀相同，可以继续搜索；否则，两棵树的搜索结果前缀已经出现不同，应该停止当前搜索过程。最终记录前缀最长的情况。

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
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

// 全局变量
int n, m, res, a[N], b[N];  
// n 和 m 分别表示两个图的节点数，res 用于存储最大匹配深度，
// a 和 b 分别存储两个图的节点标记
vector<int> G1[N], G2[N];   // G1 和 G2 分别存储两个图的邻接表

// 深度优先搜索函数
// 因为是树，不用考虑除父结点之外的回溯情况
void dfs(int u1, int far1, int u2, int far2, int dep) {
    res = max(res, dep);  // 更新最大匹配深度

    // 使用哈希表存储第一个图中当前节点的邻接节点及其标记
    map<int, int> mp;
    for (auto v : G1[u1]) {  // 遍历第一个图中当前节点 u1 的邻接节点
        if (v == far1) continue;  // 跳过父节点（避免回溯）
        mp[a[v]] = v;  // 将邻接节点的标记存储到哈希表中
    }

    // 遍历第二个图中当前节点 u2 的邻接节点
    for (auto v : G2[u2]) {
        if (v == far2) continue;  // 跳过父节点（避免回溯）
        // 如果第二个图的邻接节点标记在第一个图的哈希表中存在
        if (mp[b[v]]) {
            dfs(mp[b[v]], u1, v, u2, dep + 1);  // 递归搜索，深度加1
        }
    }
}

int main() {
    cin >> n >> m;  // 输入两个图的节点数
    for (int i = 1; i <= n; i++) cin >> a[i];  // 输入第一个图的节点标记
    for (int i = 1; i <= m; i++) cin >> b[i];  // 输入第二个图的节点标记

    // 输入第一个图的边
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        G1[u].push_back(v);  // 添加边
        G1[v].push_back(u);  // 添加边（无向图）
    }

    // 输入第二个图的边
    for (int i = 2; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G2[u].push_back(v);  // 添加边
        G2[v].push_back(u);  // 添加边（无向图）
    }

    // 如果两个图的根节点标记不匹配，直接输出 0
    if (a[1] != b[1]) return cout << 0 << '\n', 0;

    // 从根节点开始深度优先搜索，初始深度为 1
    dfs(1, 0, 1, 0, 1);

    // 输出最大匹配深度
    cout << res << '\n';
    return 0;
}

第四章 · 动态规划

第五章 · 字符串

【1】诗歌双联

【题目描述】

小桥准备了两个字符串s和t。她发现，如果从字符串s中选出两个长度为k的不相交字串，并将它们拼接在一起（不能改变相对位置），可能会形成一个包含t的字符串。为了验证这个想法，她想设计一种算法来检验是否可以这样做。

【输入输出描述】

输入格式：第一行包含三个整数n,m,k (2<=m<=2*k<=n<=1e2)，表示字符串s和字符串t的长度，以及可选子串的长度。接下来两行是由小写字母组成的字符串s和t。

输出格式：如果可以选出两个字串，使得拼接后得到的字符串包含t，则输出Yes，否则输出No。

【题解】

本题，我们使用KMP算法。我们通过遍历所有可能组成的字符串，并依次使用KMP判断是否含有要求的子串来解决这个问题。

在此过程中，有两个难点，一是如何将所有的可能组成的子串不遗漏地遍历，另一个是完成KMP算法。具体实现方式我们依次分析：

为了不遗漏地遍历所有子串，我们可以使用C++中自带的substr()方法将所有可能的长度为k的子串存入容器中。

1
2
3
4
vector<string> f;
for (int i = 0; i < n - k + 1; ++i) {
	f.push_back(s.substr(i, k)); // 其中i表示子串开始的位置，k表示子串的长度
}

由于两个子串不能有重复的元素，我们使用嵌套for循环依次拼接两个可能的子串，并用valid记录是否出现正确的情况。

1
2
3
4
5
6
7
8
9
10
11
int len = f.size();
bool valid = false;
for (int i = 0; i < len; ++i) {
	for (int j = i + k; j < len; ++j) {
		string x = f[i] + f[j]; // 拼接字符串
    	if (kmp(x,t)) {
			valid = true;
             break;
        }
    }
}

接着继续分析如何实现KMP算法，这主要是一个记住并使用模板的过程，在此不再赘述其具体细节。（可以参考以下网站：https://www.cnblogs.com/Higurashi-kagome/p/18013626）

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
bool kmp(string s, string t) {
	int n = s.length(), m = t.length();
    vector<int> next(m);
    
    int idx = 0;
    for (int i = 1; i < m; ++i) { // 构建next数组
		while (idx && t[i] != t[idx]) {
			idx = next[idx - 1];
        }
        if (t[i] == t[idx]) {
			idx++;
        }
        next[i] = idx;
    }
    
    idx = 0;
    for (int i = 0; i < n; ++i) { // 匹配模式串和主串
		while (idx && s[i] != t[idx]) {
			idx = next[idx - 1];
        }
        if (s[i] == t[idx]) {
			idx++;
		}
        if (idx == m) return true;
    }
    return false;
}

综合上述过程就完成了这道题，总体而言思路比较清晰，可以认为是一个不错的模板题。

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
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

bool kmp(string s, string t) {
    int n = s.length(), m = t.length();
    vector<int> next(m);

    int idx = 0;
    for (int i = 1; i < m; ++i) {
        while (idx && t[i] != t[idx]) {
            idx = next[idx - 1];
        }
        if (t[i] == t[idx]) {
            idx++;
        }
        next[i] = idx;
    }

    idx = 0;
    for (int i = 0; i < n; i++) {
        while (idx && s[i] != t[idx]) {
            idx = next[idx - 1];
        }
        if (t[idx] == s[i]) {
            idx++;
        }
        if (idx == m) return true;
    }

    return false;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    string s, t;
    cin >> s >> t;
    vector<string> f;
    for (int i = 0; i < n + 1 - k; ++i) {
        f.push_back(s.substr(i, k));
    }
    int len = f.size();
    bool valid = false;
    for (int i = 0; i < len; ++i) {
        for (int j = i + k; j < len; ++j) {
            string x = f[i] + f[j];
            if (kmp(x,t)) {
                valid = true;
                break;
            }
        }
    }

    if (valid) cout << "Yes";
    else cout << "No";

    return 0;
}

第六章 · 数学

第七章 · 数据结构

第八章 · 图论

【1】寻找图中是否存在路径

【题目描述】

有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

【输入输出描述】

输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5

输出：false

解释：不存在由顶点 0 到顶点 5 的路径.

示例图片

【题解】

这是一个经典的判断图中两点连通性的问题。我们在这里采用广度优先搜索和深度优先搜素两种方法进行解答。

1、广度优先搜索

使用广度优先搜索判断顶点 source 到顶点 destination 的连通性，需要我们从顶点 source 开始按照层次依次遍历每一层的顶点，检测是否可以到达顶点 destination。遍历过程我们使用队列存储最近访问过的顶点，同时记录每个顶点的访问状态，每次从队列中取出顶点 vertex 时，将其未访问过的邻接顶点入队列。

初始时将顶点 source 设为已访问，并将其入队列。每次将队列中的节点 vertex 出队列，并将与 vertex 相邻且未访问的顶点 next 入队列，并将 next 设为已访问。当队列为空或访问到顶点 destination 时遍历结束，返回顶点 destination 的访问状态即可。

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
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> adj(n); // 构造邻接表
        for (auto &edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].emplace_back(y); // 在vector容器中使用emplace_back()比push_back()更高效
            adj[y].emplace_back(x);
        }
        vector<bool> visited(n, false);
        queue<int> qu;
        qu.emplace(source); // 在队列中只能使用emplace这种添加方法
        visited[source] = true;
        while (!qu.empty()) {
            int vertex = qu.front();
            qu.pop();
            if (vertex == destination) {
                break;
            }
            for (int next : adj[vertex]) {
                if (!visited[next]) {
                    qu.emplace(next);
                    visited[next] = true;
                }
            }
        }
        return visited[destination];
    }
};

2、深度优先搜索

我们使用深度优先搜索检测顶点 source,destination 的连通性，需要从顶点 source 开始依次遍历每一条可能的路径，判断可以到达顶点 destination，同时还需要记录每个顶点的访问状态防止重复访问。

首先从顶点 source 开始遍历并进行递归搜索。搜索时每次访问一个顶点 vertex 时，如果 vertex 等于 destination 则直接返回，否则将该顶点设为已访问，并递归访问与 vertex 相邻且未访问的顶点 next。如果通过 next 的路径可以访问到 destination，此时直接返回 true，当访问完所有的邻接节点仍然没有访问到 destination，此时返回 false。

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;

class Solution {
public:
    bool dfs(int source, int destination, vector<vector<int>> &adj, vector<bool> &visited) {
        if (source == destination) {
            return true;
        }
        visited[source] = true;
        for (int next : adj[source]) {
            if (!visited[next] && dfs(next, destination, adj, visited)) {
                return true;
            }
        }
        return false;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> adj(n);
        for (auto &edge : edges) {
            int x = edge[0], y = edge[1];
            adj[x].emplace_back(y);
            adj[y].emplace_back(x);
        }
        vector<bool> visited(n, false);
        return dfs(source, destination, adj, visited);
    }
};

【2】所有可能的路径

【题目描述】

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

【输入输出描述】

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]

输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

示例图片

【题解】

本题和上题相比，差别在于需要输出所有可能的路径，因此我们需要使用一个容器来记录所有的路径，按照要求，我们使用：

1
2
vector<vector<int>> ans; // 记录所有的路径集合
vector<int> path; // 记录每一条路径

之后，我们主要使用深度优先搜索完成本题，这种写法主要针对的就是输出路径的搜索方式。其中，path需要用到回溯的思想，从而在深度搜索的同时，可以回到之前未走过的路径上。

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
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    void DFS(vector<vector<int>>& graph, int x, int n) {
        if (x == n) {
            ans.emplace_back(path);
            return;
        }
        for (auto &i : graph[x]) {
            path.push_back(i);
            DFS(graph, i, n);
            path.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);
        DFS(graph, 0, graph.size()-1);
        return ans;
    }
};

【3】统计无向图中无法互相到达点对数

【题目描述】

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

【输入输出描述】

1
2
3
4
5
输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。
示例图片

【题解】

本题首先需要明白如何计算无法互相到达的不同点对数目。假设存在一个连通片的顶点数量为 x，总共有 n 个顶点，则这个连通片总共贡献了 x*(n-x) 个无法互相到达的不同点对数目。依照上面的方法统计所有的连通片，此时，每个点对都统计了两次，因此最终结果还需要除以 2。

接下来我们思考如何遍历所有的连通片。我们采用深度优先遍历，每一次遍历都只可能遍历其中一个连通片，我们的目标就是统计这个连通片中顶点的个数。

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
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<bool> visited;
    long long DFS(vector<vector<int>>& graph, int x) { // 从x开始深度遍历
        visited[x] = true;
        long long cnt = 1;
        for (auto& y : graph[x]) {
            if (!visited[y]) {
                cnt += DFS(graph, y);
            }
        }
        return cnt;
    }

    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto &edge : edges) { // 创建邻接表
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        for (int i = 0; i < n; i++) { // 创建标记表
            visited.push_back(false);
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) { // 统计每个连通片的贡献次数
            if (!visited[i]) {
                long long cnt = DFS(graph, i);
                ans += cnt * (n - cnt);
            }
        }

        return ans / 2;
    }
};

第九章 · 计算几何