devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十四届蓝桥杯cb组省赛个人题解_蓝桥杯冶炼金属

作者：知新_RL | 2024-04-27 02:48:02

赞

踩

蓝桥杯冶炼金属

试题 C: 冶炼金属

​ 时间限制: 1.0s 内存限制: 256.0MB 本题总分：10 分

【问题描述】

​ 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个 炉子有一个称作转换率的属性 V , V V,V V,V 是一个正整数，这意味着消耗 V V V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V V V 时，无法继续冶炼。
​ 现在给出了 N N N 条冶炼记录，每条记录中包含两个整数 A A A 和 B B B，这表示本次投入了 A A A 个普通金属 O，最终冶炼出了 B B B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
​ 根据这 N N N 条冶炼记录，请你推测出转换率 V V V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

【输入格式】

​ 第一行一个整数 N N N，表示冶炼记录的数目。
​ 接下来输入 N N N 行，每行两个整数 A 、 B A、B A、B，含义如题目所述。

【输出格式】

​ 输出两个整数，分别表示 V V V 可能的最小值和最大值，中间用空格分开。

【样例输入】

3
75 3
53 2
59 2

【样例输出】

20 25

【样例说明】

​ 当 V = 20 V = 20 V=20 时，有：⌊ 75 75 75 20 20 20⌋ = 3 = 3 =3，⌊ 53 53 53 20 20 20⌋ = 2 = 2 =2，⌊ 59 59 59 20 20 20⌋ = 2 = 2 =2，可以看到符合所有冶炼记录。
​ 当 V = 25 V = 25 V=25 时，有：⌊ 75 75 75 25 25 25⌋ = 3 = 3 =3，⌊ 53 53 53 25 25 25⌋ = 2 = 2 =2，⌊ 59 59 59 25 25 25⌋ = 2 = 2 =2，可以看到符合所有冶炼记录。
​ 且再也找不到比 20 20 20 更小或者比 25 25 25 更大的符合条件的 V V V 值了。

【评测用例规模与约定】

对于 30 30 30% 的评测用例， 1 ≤ N ≤ 1 0 2 1\le N \le 10^2 1≤N≤102。
对于 60 60 60% 的评测用例， 1 ≤ N ≤ 1 0 3 1\le N \le 10^3 1≤N≤103。
对于 100 100 100% 的评测用例， 1 ≤ N ≤ 1 0 4 , 1 ≤ B ≤ A ≤ 1 0 9 1\le N \le 10^4,1\le B\le A\le 10^9 1≤N≤104,1≤B≤A≤109。

笨蒟蒻个人题解

笨蒟蒻当初是推公式写的：
​ 首先，最大值很好看出就是 a b \frac{a}{b} ba​，主要是最小值怎么计算？就拿 75 75 75 和 3 3 3 来说，它要冶炼出来的金属不能超过 4 4 4 个，假设我们就让他 4 4 4 个呢，看它最小能满足什么情况，那么就是 75 4 \frac{75}{4} 475​ 得出来的是 18 18 18，但是 18 18 18 是不行的， 18 18 18 是那个第一个能冶炼出来的金属，必须要是在 18 18 18 的基础上 + 1 +1 +1 才可以，就是 19 19 19。有人说，最小值公式可以是 a b + 1 \frac{a}{b+1} b+1a​ 上取整，但这样是不可以的，假如说 12 12 12 和 3 3 3，那么我上取整的答案是 12 4 = 3 \frac{12}{4}=3 412​=3，显然这样是不可以的，所以必须要是下取整 + 1 +1 +1，公式如下 a b + 1 + 1 \frac{a}{b+1}+1 b+1a​+1，那么这就是最终答案了。
​ 除了公式，当然也可以二分来写，这样也是能过的。我们可以直接二分最大值和最小值的答案，判断是否每个都能满足。

AC_Code

方法一：推公式
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
int n, u, v = inf;
signed main()
{

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        u = max(u, a / (b + 1) + 1);
        v = min(v, a / b);
    }
    cout << u << " " << v << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
方法二：二分
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
const int N = 1e4 + 10;
int n, k = inf, a[N], b[N];
signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        if (a[i] / b[i] < k)k = a[i] / b[i];
    }
    int l = 1, r = k;
    while (l < r) 
    {
        int mid = l + r >> 1;
        int i = 0;
        for (i = 0; i < n; i++)
            if (a[i] / mid != b[i])break;
        if (i == n)r = mid;
        else l = mid + 1;
    }
    cout << l << " " << k << endl;
    return 0;
}

  • 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

试题 D: 飞机降落

​ 时间限制: 2.0s 内存限制: 256.0MB 本题总分：10 分

【问题描述】

​ N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti​ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 D i D_{i} Di​ 个单位时间，即它最早可以于 T i T_{i} Ti​ 时刻开始降落，最晚可以于 T i + D i T_{i} + D_{i} Ti​+Di​ 时刻开始降落。降落过程需要 L i L_{i} Li​ 个单位时间。
​ 一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

​ 请你判断 N N N 架飞机是否可以全部安全降落。

【输入格式】

​ 输入包含多组数据。
​ 第一行包含一个整数 T T T，代表测试数据的组数。
​ 对于每组数据，第一行包含一个整数 N N N。
​ 以下 N N N 行，每行包含三个整数： T i T_{i} Ti​， D i D_{i} Di​ 和 L i L_{i} Li​。

【输出格式】

​ 对于每组数据，输出 Y E S YES YES 或者 N O NO NO，代表是否可以全部安全降落。

【样例输入】

2 3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

【样例输出】

YES
NO

【样例说明】

​ 对于第一组数据，可以安排第 3 3 3 架飞机于 0 0 0 时刻开始降落， 20 20 20 时刻完成降落。安排第 2 2 2 架飞机于 20 20 20 时刻开始降落， 30 30 30 时刻完成降落。安排第 1 1 1 架飞机于 30 30 30 时刻开始降落， 40 40 40 时刻完成降落。
​ 对于第二组数据，无论如何安排，都会有飞机不能及时降落。
​ 对于 30 30 30% 的数据， N ≤ 2 N \le 2 N≤2。
​ 对于 100 100 100% 的数据， 1 ≤ T ≤ 10 , 1 ≤ N ≤ 10 , 0 ≤ T i , D i , L i ≤ 1 0 5 1\le T \le 10,1\le N \le 10,0\le T_{i},D_{i},L_{i} \le10^{5} 1≤T≤10,1≤N≤10,0≤Ti​,Di​,Li​≤105。

笨蒟蒻的个人题解

好几种贪心方式，不妨来看看：

第一种贪心方式：“先到先服务”，先对t排序，然后哪个下落早，哪个先走，但这样是错误的，设两个飞机分别为 t 1 , l 1 , d 1 , t 2 , l 2 , d 2 t1 ,l1, d1, t2, l2, d2 t1,l1,d1,t2,l2,d2，只要满足d1 >= t2 + l2即证得失败，因为未限制 d d d，例：0 5 5 1 3 2

第二种贪心方式：“最晚开始降落早的先降落”，对 t + d t+d t+d 排序，然后哪个能先早的走就走，但这样也是错误的，笨蒟蒻考试的时候就这么想的，设两个飞机分别为 t 1 , l 1 , d 1 , t 2 , l 2 , d 2 t1, l1, d1, t2, l2, d2 t1,l1,d1,t2,l2,d2，只要满足L2 <= t1 + d1 - t2即证得失败，因为未限制 L 2 L2 L2，例：0 5 10 1 6 2

第三种贪心方式：最晚降地的早降落，对 t + d + l t+d+l t+d+l 排序，然后贪心，但这样也是错误的，设两个飞机分别为 t 1 , l 1 , d 1 , t 2 , l 2 , d 2 t1 ,l1, d1, t2, l2, d2 t1,l1,d1,t2,l2,d2，只要满足t1 + l1 >= t2 + d2则证明失败，例：2 5 3 0 4 7

那么怎么做？我们可以用全排列的方法做，就是枚举所有可能降落的情况，判断是否能全部满足，时间复杂度 O ( T n n ! ) O(Tnn!) O(Tnn!) 约为 3 e 8 3e8 3e8 理论上会超时，但是剪枝之后，实际上飞快，因为找到一组有解的即可。

还有状态压缩dp。

这就得用状态压缩dp去写了，怎么做？设 f [ i ] f[i] f[i] 是表示第 i i i 种情况能够降落的最小时间，把下标当成二进制来思考，那么这个降落就和飞机的顺序没有关系了，就不用考虑顺序了。然后在能满足飞机能落地的情况下，再去不断更新最小值，那么这个有多少种情况呢？有 1024 1024 1024 种情况，不断去更新，最终判断f[(1 << n) - 1]是否成立即可。

AC_Code

方法一：全排列
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 15;
struct Edge
{
    int t, d, l;
}e[N];
bool st[N];
int n;
bool dfs(int u, int last)
{
    if (u == n) return true;
    for (int i = 0; i < n; i++)
    {
        int t = e[i].t, d = e[i].d, l = e[i].l;
        if (!st[i] && t + d >= last)
        {
            st[i] = true;
            if (dfs(u + 1, max(t, last) + l)) return true;
            st[i] = false;
        }
    }
    return false;
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) scanf("%d%d%d", &e[i].t, &e[i].d, &e[i].l);
        memset(st, false, sizeof(st));
        if (dfs(0, 0)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

  • 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
方法二：状态压缩DP
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N = 15, M = (1 << 10) + 10;
struct Edge
{
    int t, d, l;
}e[N];
int T, n;
int f[M];
int main()
{
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> e[i].t >> e[i].d >> e[i].l;
        memset(f, inf, sizeof(f));
        f[0] = 0;
        for(int i = 1; i < 1 << n; i++)
            for(int j = 0; j < n; j++)
                if(i >> j & 1)
                {
                    int t = e[j].t, d = e[j].d, l = e[j].l;
                    if(t + d >= f[i - (1 << j)])
                        f[i] = min(f[i], max(f[i - (1 << j)], t) + l);
                }
        if(f[(1 << n) - 1] != inf) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

  • 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

试题 E: 接龙数列

​ 时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】

​ 对于一个长度为 K K K 的整数数列： A 1 , A 2 , … , A K A_{1},A_{2},\dots,A_{K} A1​,A2​,…,AK​，我们称之为接龙数列当且仅当 A i A_{i} Ai​ 的首位数字恰好等于 A i − 1 A_{i−1} Ai−1​ 的末位数字 ( 2 ≤ i ≤ K ) (2\le i\le K) (2≤i≤K)。
​ 例如 12 , 23 , 35 , 56 , 61 , 11 12,23,35,56,61,11 12,23,35,56,61,11 是接龙数列； 12 , 23 , 34 , 56 12,23,34,56 12,23,34,56 不是接龙数列，因为 56 56 56 的首位数字不等于 34 34 34 的末位数字。所有长度为 1 1 1 的整数数列都是接龙数列。
​ 现在给定一个长度为 N N N 的数列 A 1 , A 2 , … , A N A_{1},A_{2},\dots,A_{N} A1​,A2​,…,AN​，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

【输入格式】

​ 第一行包含一个整数 N N N。
​ 第二行包含 N N N 个整数 A 1 , A 2 , … , A N A_{1},A_{2},\dots,A_{N} A1​,A2​,…,AN​。

【输出格式】

​ 一个整数代表答案。

【样例输入】

5
11 121 22 12 2023

【样例输出】

1

【样例说明】

​ 删除 22 22 22，剩余 11 , 121 , 12 , 2023 11,121,12,2023 11,121,12,2023 是接龙数列。

【评测用例规模与约定】

​ 对于 20 20 20% 的数据， 1 ≤ N ≤ 20 1\le N \le 20 1≤N≤20。
​ 对于 50 50 50% 的数据， 1 ≤ N ≤ 10000 1\le N \le 10000 1≤N≤10000。
​ 对于 100 100 100% 的数据， 1 ≤ N ≤ 1 0 5 1\le N \le 10^{5} 1≤N≤105， 1 ≤ A i ≤ 1 0 9 1\le A_{i} \le 10^{9} 1≤Ai​≤109。所有 A i A_{i} Ai​ 保证不包含前导 0 0 0。

笨蒟蒻的个人题解

不难看出这题用 LIS，可这满打满算也只能拿 50 50 50% 的分数，毕竟是 O ( n 2 ) O(n^2) O(n2)，如何 AC 呢？
其实我们只要关心最后一个数结尾的序列的最长值就行了，那就可以直接优化掉一个循环！然后其实找首位和尾位也可以优化的，时间复杂度 O ( n ) O(n) O(n)。

AC_Code

LIS
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define int long long
int n,res;
int f[15];
signed main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
    {
        char x[15];
        scanf("%s", x);
        int l = x[0] - '0',r = x[strlen(x) - 1] - '0';
        f[r] = max(f[r], max(1ll, f[l] + 1));
    }
    for(int i = 0; i < 10; i++) res = max(res, f[i]);
    cout << n - res << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

试题 F: 岛屿个数

​ 时间限制: 2.0s 内存限制: 256.0MB 本题总分：15 分

【问题描述】

​ 小蓝得到了一副大小为 M × N M\times N M×N 的格子地图，可以将其视作一个只包含字符 ‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水， 每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
​ 在岛屿 A 所占据的格子中，如果可以从中选出 k k k 个不同的格子，使得 他们的坐标能够组成一个这样的排列： ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 ) (x_{0},y_{0}),(x_{1},y_{1}),...,(x_{k−1},y_{k−1}) (x0​,y0​),(x1​,y1​),...,(xk−1​,yk−1​)，其中 ( x ( i + 1 ) (x_{(i+1)} (x(i+1)​% k , y ( i + 1 ) _{k},y_{(i+1)} k​,y(i+1)​% k ) _{k} ) k​) 是由 ( x i , y i ) (x_{i},y_{i}) (xi​,yi​) 通过上/下/左/右移动一次得来的 ( 0 ≤ i ≤ k − 1 ) (0 \le i \le k−1) (0≤i≤k−1)， 此时这 k k k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于 这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。
​ 请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

【输入格式】

​ 第一行一个整数 T T T，表示有 T T T 组测试数据。
​ 接下来输入 T T T 组数据。对于每组数据，第一行包含两个用空格分隔的整数 M 、 N M、N M、N 表示地图大小；接下来输入 M M M 行，每行包含 N N N 个字符，字符只可能是 ‘0’ 或 ‘1’。

【输出格式】

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

【样例输入】

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

【样例输出】

1
3

【样例说明】

​ 对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：
​ 01111
​ 11001
​ 10201
​ 10001
​ 11111
​ 岛屿 2 2 2 在岛屿 1 1 1 的 “环” 内部，所以岛屿 2 2 2 是岛屿 1 1 1 的子岛屿，答案为 1 1 1。
​ 对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：
​ 111111
​ 100001
​ 020301
​ 100001
​ 111111
​ 注意岛屿 3 3 3 并不是岛屿 1 1 1 或者岛屿 2 2 2 的子岛屿，因为岛屿 1 1 1 和岛屿 2 2 2 中均没有 “环”。

【评测用例规模与约定】

​ 对于 30 30 30% 的评测用例， 1 ≤ M , N ≤ 10 1\le M,N \le 10 1≤M,N≤10。
​ 对于 100 100 100% 的评测用例， 1 ≤ T ≤ 10 ， 1 ≤ M , N ≤ 50 1\le T \le 10，1\le M,N \le 50 1≤T≤10，1≤M,N≤50。

笨蒟蒻的个人题解

一道 dfs/bfs 的题？如何思考？最关键的是那个环！那么该怎么判断那个岛是否在环里呢？笨蒟蒻是这样想的，一开始先找 1 1 1 对吧，大多数人也这样想，然后那个 1 1 1 如果在边界，那必定就是一个岛（要算进去答案的），就这样一直找完 1 1 1 的所有点，那然后如果不是呢？或者说每个点都不在边界呢？那咱就找 0 0 0 呗。这样想啊，假设它不是一个环，那么从那个点开始往外走，就一定有出路！因为它没有被包围，只要一直找，看出路是否能找到边界即可！那么问题就简化为一个四联通+八联通的dfs/bfs了（笨蒟蒻当时是写 dfs 的，当然用 bfs 也是可以的），四联通就是找 1 1 1，把每个点都变成’#'，当然用其它符号也是可以的，然后8联通找 0 0 0，找 0 0 0 的出路，能否到边界记得一定要剪枝，不然过不了吧（猜的）。然后时间复杂度呢？ O ( T n 2 ) O(Tn^{2}) O(Tn2)（剪枝）。
再来说说网上的题解是怎么讲的，也非常有意思。首先在最外围补一圈 0 0 0，比如说：
01111
11001
10101
10001
11111
然后把它变成：
0000000
0011110
0110010
0101010
0100010
0111110
0000000
然后就可以从最上面 ( 0 , 0 ) \left(0,0\right) (0,0) 开始dfs/bfs了找所有八联通的 0 0 0，然后标记，剩下的没有被标记过的联通块的个数就是答案了，那么如何找呢？就用四联通 bfs/dfs 即可找出，时间复杂度 O ( T n 2 ) O(Tn^{2}) O(Tn2)，但同样两遍 dfs，这个不容易爆，因为我写的是 1 1 1 和 0 0 0 同时找，它这个是先找 0 0 0 再找连通块。

AC_Code

方法一：两遍dfs
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 55;
char g[N][N];
bool st[N][N];
bool flag;
int t, ans;
int n, m;
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
void dfs2(int x, int y)
{
    if (flag)return;
    st[x][y] = true;
    for (int i = -1; i <= 1; i++)
        for (int j = -1; j <= 1; j++)
        {
            if (i == 0 && j == 0) continue;
            int nx = i + x, ny = j + y;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            {
                flag = true;
                break;
            }
            if (st[nx][ny]) 
                continue;
            if (g[nx][ny] == '0') dfs2(nx, ny);
        }
}
void dfs1(int x, int y)
{
    g[x][y] = '#';
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        {
            flag = true;
            continue;
        }
        if (g[nx][ny] == '1') dfs1(nx, ny);
        if (g[nx][ny] == '0') dfs2(nx, ny);
    }
}
int main()
{
    cin >> t;
    while (t--)
    {
        ans = 0;
        cin >> n >> m;
        memset(g, 0, sizeof(g));
        memset(st, 0, sizeof(st));
        for (int i = 0; i < n; i++) scanf("%s", g[i]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                if (g[i][j] == '1')
                {
                    dfs1(i, j);
                    if (flag)ans++;
                    memset(st, false, sizeof(st));
                    flag = false;
                }
            }
        cout << ans << endl;
    }
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
方法二：两遍dfs
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=55;
char g[N][N];
bool st[N][N];
bool flag;
int t, ans;
int n, m;
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
void dfs_0(int x, int y)
{
    st[x][y] = true;
    for(int i = -1; i <= 1; i++)
        for(int j = -1; j <= 1; j++)
        {
            if(i == 0 && j == 0) continue;
            int nx = x + i, ny = y + j;
            if(nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1 || st[nx][ny]) continue;
            if(!g[nx][ny]) dfs_0(nx, ny);
        }
}
void dfs_1(int x, int y)
{
    st[x][y] = true;
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > m || st[nx][ny]) continue;
        dfs_1(nx, ny);
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(g, 0, sizeof(g));
        memset(st, false, sizeof(st));
        cin >> n >> m;
        ans = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                char c;
                cin >> c;
                g[i][j] = c - '0';
            }
        dfs_0(0, 0);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                if(!st[i][j])
                {
                    dfs_1(i, j);
                    ans++;
                }
            }
        cout << ans << endl;
    }
    return 0;
}

  • 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

试题 G: 子串简写

​ 时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分

【问题描述】

​ 程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
​ 在本题中，我们规定长度大于等于 K K K 的字符串都可以采用这种简写方法 （长度小于 K K K 的字符串不配使用这种简写）。
​ 给定一个字符串 S S S 和两个字符 c 1 c_{1} c1​ 和 c 2 c_{2} c2​，请你计算 S S S 有多少个以 c 1 c_{1} c1​ 开头 c 2 c_{2} c2​ 结尾的子串可以采用这种简写？

【输入格式】

​ 第一行包含一个整数 K K K。 第二行包含一个字符串 S S S 和两个字符 c 1 c_{1} c1​ 和 c 2 c_{2} c2​。

【输出格式】

​ 一个整数代表答案。

【样例输入】

4
abababdb a b

【样例输出】

6

【样例说明】

​ 符合条件的子串如下所示，中括号内是该子串：
​ [abab]abdb
​ [ababab]db
​ [abababdb]
​ ab[abab]db
​ ab[ababdb]
​ abab[abdb]

【评测用例规模与约定】

​ 对于 20 20 20% 的数据， 2 ≤ K ≤ ∣ S ∣ ≤ 10000 2\le K \le |S|\le 10000 2≤K≤∣S∣≤10000。
​ 对于 100 100 100% 的数据， 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 0 5 2 \le K \le |S|\le 5\times 10^{5} 2≤K≤∣S∣≤5×105。 S S S 只包含小写字母。 c 1 c_{1} c1​ 和 c 2 c_{2} c2​ 都 是小写字母。
​ ∣ S ∣ |S| ∣S∣ 代表字符串 S S S 的长度。

笨蒟蒻的个人题解

这题其实有很多方法的，可以用二分、双指针、前缀和。一定要记得要开 ll！
那么笨蒟蒻当时是用双指针来写的，因为好写，但其实都一样的。具体思路就是枚举每一位 i i i，找到对应的 j j j 即可，由于递增，所以 j j j 不用改变的。
那二分呢，就是用二分找第一个满足对应的 j j j 即可。
前缀和呢，维护给定首字母出现的次数，然后用 j j j 维护，找到尾字母时，然后累加答案。

AC_Code

方法一：双指针
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int k, ans;
int u[N], v[N];
int cnt1, cnt2;
string s;
char a[2], b[2];
signed main()
{
    cin >> k >> s >> a >> b;
    for (int i = 0; i < s.size(); i++)
    {
        if(s[i] == a[0]) u[cnt1++] = i + 1;
        if(s[i] == b[0]) v[cnt2++] = i + 1;
    }
    int j = 0;
    for (int i = 0; i < cnt1; i++)
    {
        while(v[j] - u[i] < k - 1 && j < cnt2) j++;
        if(j >= cnt2) break;
        ans += cnt2 - j;
    }
    cout << ans << endl;
    return 0;
}

  • 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<iostream>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int k, ans;
int u[N], v[N];
int cnt1, cnt2;
string s;
char a[2], b[2];
signed main()
{
    cin >> k >> s >> a >> b;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == a[0]) u[cnt1++] = i + 1;
        if (s[i] == b[0]) v[cnt2++] = i + 1;
    }
    for (int i = 0; i < cnt1; i++)
    {
        int l = 0, r = cnt2;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (v[mid] - u[i] >= k - 1) r = mid;
            else l = mid + 1;
        }
        ans += cnt2 - l;
    }
    cout << ans << endl;
    return 0;
}

  • 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
方法三：前缀和
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int k, ans;
int u[N];
int cnt1, cnt2;
string s;
char a[2], b[2];
signed main()
{
    cin >> k >> s >> a >> b;
    for (int i = 0, j = 0; i < s.size(); i++)
    {
        if (s[i] == a[0]) j++;
        u[i] = j;
        if (i > k - 2 && s[i] == b[0]) ans += u[i - k + 1];
    }
    cout << ans << endl;
    return 0;
}

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

试题 H: 整数删除

​ 时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分

【问题描述】

​ 给定一个长度为 N N N 的整数数列： A 1 , A 2 , … , A N A_{1},A_{2},\dots,A_{N} A1​,A2​,…,AN​。你要重复以下操作 K K K 次： 每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
​ 输出 K K K 次操作后的序列。

【输入格式】

​ 第一行包含两个整数 N N N 和 K K K。
​ 第二行包含 N N N 个整数， A 1 , A 2 , A 3 , … , A N A_{1},A_{2},A_{3},\dots,A_{N} A1​,A2​,A3​,…,AN​。

【输出格式】

​ 输出 N − K N−K N−K 个整数，中间用一个空格隔开，代表 K K K 次操作后的序列。

【样例输入】

5 3
1 4 2 8 7

【样例输出】

17 7

【样例说明】

​ 数列变化如下，中括号里的数是当次操作中被选择的数：
[1] 4 2 8 7
5 [2] 8 7

【评测用例规模与约定】

​ 对于 20 20 20% 的数据， 1 ≤ K < N ≤ 10000 1\le K < N \le10000 1≤K<N≤10000。
​ 对于 100 100 100% 的数据， 1 ≤ K < N ≤ 5 × 105 ， 0 ≤ A i ≤ 1 0 8 1\le K < N \le 5\times 105，0\le A_{i} \le 10^{8} 1≤K<N≤5×105，0≤Ai​≤108。

笨蒟蒻的个人题解

当时想用双链表写的，因为手写链表写的比较少，不熟练，最后写是写了一个，还是单链表都有bug，不敢交，还是写了个暴力上去，拿 20 20 20% 太菜了qwq。

说说写法：可以用优先队列维护最小值+双链表都行。还有线段树的方法。

AC_Code

方法一：优先队列+双链表
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define int long long
#define fi first
#define se second
typedef pair<int, int>PII;
const int N = 5e5 + 10;

int n, k;
int a[N], l[N], r[N];
priority_queue<PII, vector<PII>, greater<PII>>q;

void dele(int id)
{
    l[r[id]] = l[id];
    r[l[id]] = r[id];
    a[l[id]] += a[id];
    a[r[id]] += a[id];
}
signed main()
{
    scanf("%lld%lld", &n, &k);
    
    r[0] = 1, l[n + 1] = n;
    
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        l[i] = i - 1, r[i] = i + 1;
        q.push({a[i], i});
    }
    
    while(k--)
    {
        auto t = q.top();
        q.pop();
        
        int u = t.fi, v = t.se;
        if(u != a[v]) 
        {
            q.push({a[v], v});
            k++;
        }
        else dele(v);
    }
    
    for(int i = r[0]; i != n + 1; i = r[i]) cout << a[i] << ' ';
    return 0;
}

  • 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
方法二：线段树
// 空着先，有空再补

  • 1

试题 I: 景区导游

​ 时间限制: 5.0s 内存限制: 256.0MB 本题总分：25 分

【问题描述】

​ 某景区一共有 N N N 个景点，编号 1 1 1 到 N N N。景点之间共有 N − 1 N −1 N−1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行， 需要花费一定的时间。
​ 小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K K K 个景点： A 1 , A 2 , … , A K A_{1},A_{2},\dots,A_{K} A1​,A2​,…,AK​。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 K−1 K−1 个景点。具体来说，如果小明选择跳过 A i A_{i} Ai​，那么他会按顺序带游客游览 A 1 , A 2 , … , A i − 1 , A i + 1 , … , A K , ( 1 ≤ i ≤ K ) A_{1},A_{2},\dots,A_{i−1},A_{i+1},\dots ,A_{K}, (1\le i\le K) A1​,A2​,…,Ai−1​,Ai+1​,…,AK​,(1≤i≤K)。
​ 请你对任意一个 A i A_{i} Ai​，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

【输入格式】

​ 第一行包含 2 2 2 个整数 N N N 和 K K K。
​ 以下 N − 1 N−1 N−1 行，每行包含 3 3 3 个整数 u , v u,v u,v 和 t t t，代表景点 u u u 和 v v v 之间有摆渡车线路，花费 t t t 个单位时间。
​ 最后一行包含 K K K 个整数 A 1 , A 2 , … , A K A_{1},A_{2},\dots,A_{K} A1​,A2​,…,AK​ 代表原定游览线路。

【输出格式】

​ 输出 K K K 个整数，其中第 i i i 个代表跳过 A i A_{i} Ai​ 之后，花费在摆渡车上的时间。

【样例输入】

6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1

【样例输出】

10 7 13 14

【样例说明】

​ 原路线是 2 → 6 → 5 → 1 2→6→5→1 2→6→5→1。
​ 当跳过 2 2 2 时，路线是 6 → 5 → 1 6 → 5 → 1 6→5→1，其中 6 → 5 6 → 5 6→5 花费时间 3 + 2 + 2 = 7 3 + 2 + 2 = 7 3+2+2=7， 5 → 1 5→1 5→1 花费时间 2 + 1 = 3 2 + 1 = 3 2+1=3，总时间花费 10 10 10。
​ 当跳过 6 6 6 时，路线是 2 → 5 → 1 2 → 5 → 1 2→5→1，其中 2 → 5 2 → 5 2→5 花费时间 1 + 1 + 2 = 4 1 + 1 + 2 = 4 1+1+2=4， 5 → 1 5→1 5→1 花费时间 2 + 1 = 3 2 + 1 = 3 2+1=3，总时间花费 7 7 7。
​ 当跳过 5 5 5 时，路线是 2 → 6 → 1 2 → 6 → 1 2→6→1，其中 2 → 6 2 → 6 2→6 花费时间 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 = 7 1+1+2+3=7， 6 → 1 6→1 6→1 花费时间 3 + 2 + 1 = 6 3 + 2 + 1 = 6 3+2+1=6，总时间花费 13 13 13。
​ 当跳过 1 1 1 时，路线时 2 → 6 → 5 2 → 6 → 5 2→6→5，其中 2 → 6 2 → 6 2→6 花费时间 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 = 7 1+1+2+3=7， 6 → 5 6→5 6→5 花费时间 3 + 2 + 2 = 7 3 + 2 + 2 = 7 3+2+2=7，总时间花费 14 14 14。

【评测用例规模与约定】

​ 对于 20 20 20% 的数据， 2 ≤ K ≤ N ≤ 1 0 2 2\le K \le N \le 10^{2} 2≤K≤N≤102。
​ 对于 40 40 40% 的数据， 2 ≤ K ≤ N ≤ 1 0 4 2\le K \le N \le10^{4} 2≤K≤N≤104。
​ 对于 100 100 100% 的数据， 2 ≤ K ≤ N ≤ 1 0 5 2 \le K \le N \le 10^{5} 2≤K≤N≤105， 1 ≤ u , v , A i ≤ N 1 \le u,v,A_{i} \le N 1≤u,v,Ai​≤N， 1 ≤ t ≤ 1 0 5 1 \le t \le 10^{5} 1≤t≤105。保证 A i A_{i} Ai​ 两两不同。

笨蒟蒻的个人题解

笨蒟蒻居然还有时间看这种题目，讲的是什么呢？让我们从一个地方依此走到好几处地方，求花费的路径最小时间。一眼图论，考前只背过简单的的板子，难受。太菜了，当时没学lca，不会……可是笨蒟蒻自己当时都忘记用floyd骗分了QwQ。
先来一波floyd骗分大法，理论上能至少通过 20 20 20%。
floyd骗分大法，代码如下：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 5e3 + 10;
#define int long long
#define inf 0x3f3f3f3f
int n, k, ans;
int kk[N], f[N][N];
void floyd()
{
    for(int u = 1; u <= n; u++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                f[i][j] = min(f[i][j], f[i][u] + f[u][j]);
}
signed main()
{
    cin >> n >> k;
    memset(f, inf, sizeof(f));
    for(int i = 1; i <= n; i++) f[i][i] = 0;
    for(int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        f[a][b] = f[b][a] = min(f[a][b], c);
    }
    floyd();
    for(int i = 1; i <= k; i++) scanf("%lld", &kk[i]);
    for(int i = 2; i <= k; i++) ans += f[kk[i - 1]][kk[i]];
    for(int i = 1; i <= k; i++)
    {
        if(i == 1) printf("%lld ", ans - f[kk[1]][kk[2]]);
        else if(i == k) printf("%lld\n", ans - f[kk[k - 1]][kk[k]]);
        else printf("%lld ", ans - f[kk[i - 1]][kk[i]] - f[kk[i]][kk[i + 1]] + f[kk[i - 1]][kk[i + 1]]);
    }
    return 0;
}

  • 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

OK，回归本题，这题要用到 lca，然后前缀和维护一下即可。求 lca 好几种方法，一种是倍增，一种是 tarjan，还有树剖。
简单说一下倍增思路：倍增是一种在线的做法，先预处理一下所有结点的深度 d e p t h depth depth，以及到根节点的距离 d i s t dist dist，还有每个点跳 2 k 2^k 2k 的祖宗结点记为 f a fa fa，最后求 lca 的时候记得从后往前跳，用的思想是二进制拼凑，最后的两点间距离就是dist[a] + dist[b] - 2 * dist[lca(a, b)]。时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。
简单说一下 tarjan 思路：tarjan 是一种离线做法，先预处理一下到根节点的距离 d i s t dist dist，然后先把所有询问存储下来，设置一个状态 s t st st，已经搜过的点设为 1 1 1，正在搜索的点设为 2 2 2，没被搜索的点设为 0 0 0，然后正在搜索的点对于已经搜过的点就是一条分支吧，利用这个来把所有最近公共祖先找出来，然后算距离存到 r e s res res 里。时间复杂度 O ( n + m ) O(n + m) O(n+m)。

简单说一下树剖思路：树剖也是一种在线做法，先预处理出所有树相关的信息（深度，父节点，重儿子，距离，重链头，儿子数量等），然后找 lca 就找每个链头，看是否相同。时间复杂度 O ( 2 n + l o g n ) O(2n + logn) O(2n+logn)。

AC_Code

方法一：LCA – 倍增
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
const int N = 1e5 + 10, M = N * 2;

int n, m, sum;
int e[M], ne[M], w[M], h[N], idx;
int depth[N], q[N], dist[N], v[N];
int fa[N][18];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void bfs(int root)
{
    memset(depth, inf, sizeof(depth));
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[++tt] = j;
                fa[j][0] = t;
                dist[j] = dist[t] + w[i];
                for(int k = 1; k < 18; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b) 
{
    if(depth[a] < depth[b]) swap(a, b);
    for(int k = 17; k >= 0; k--)
        if(depth[fa[a][k]] >= depth[b]) a = fa[a][k];
    if(a == b) return a;
    
    for(int k = 17; k >= 0; k--)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}
int getdis(int a, int b)
{
    return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}
signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    bfs(1);
    
    for(int i = 1; i <= m; i++) scanf("%lld", &v[i]);
    for(int i = 2; i <= m; i++) sum += getdis(v[i], v[i - 1]);
    for(int i = 1; i <= m; i++)
    {
        if(i == 1) printf("%lld ", sum - getdis(v[i], v[i + 1]));
        else if(i == m) printf("%lld\n", sum - getdis(v[i - 1], v[i]));
        else printf("%lld ", sum - getdis(v[i - 1], v[i]) - getdis(v[i], v[i + 1]) + getdis(v[i - 1], v[i + 1]));
    }
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
方法二：LCA – tarjan
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long 
#define fi first
#define se second
#define pb push_back
const int N = 1e5 + 10, M = 2 * N;
typedef pair<int, int>PII;
int n, m, ord, ans;
int e[M], ne[M], w[M], h[N], idx;
int dist[N], p[N], st[N], v[N], res[M * 2];
vector<PII>query[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u, int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}
void tarjan(int u)
{
    st[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }
    for(auto item : query[u])
    {
        int y = item.fi, id = item.se;
        if(st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }
    st[u] = 2;
}
signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%lld%lld%lld", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    for(int i = 0; i < m; i++) scanf("%lld", &v[i]);
    for(int i = 0; i < m - 1; i++)
    {
        query[v[i]].pb({v[i + 1], ord});
        query[v[i + 1]].pb({v[i], ord});
        ord++;
    }
    for(int i = 0; i < m - 2; i++)
    {
        query[v[i]].pb({v[i + 2], ord});
        query[v[i + 2]].pb({v[i], ord});
        ord++;
    }
    for(int i = 1; i <= n; i++) p[i] = i;
    
    dfs(1, -1);
    tarjan(1);
    
    for(int i = 0; i < m - 1; i++) ans += res[i];
    for(int i = 0; i < m; i++)
    {
        if(!i) printf("%lld ", ans - res[i]);
        else if(i == m - 1) printf("%lld\n", ans - res[i - 1]);
        else printf("%lld ", ans - res[i - 1] - res[i] + res[i + m - 2]);
    }
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
方法三：LCA – 树剖
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define int long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
typedef pair<int, int>PII;
const int N = 1e5 + 10, M = N * 2;

int n, m, res;
int e[M], ne[M], h[N], w[M], idx;
int depth[N], son[N], fa[N], siz[N], top[N], dist[N], v[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs_1(int u, int f)
{
    fa[u] = f, siz[u] = 1, son[u] = 0;
    if(f != -1) depth[u] = depth[f] + 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == f) continue;
        dist[j] = dist[u] + w[i];
        dfs_1(j, u);
        siz[u] += siz[j];
        if(siz[son[u]] < siz[j]) son[u] = j;
    }
}

void dfs_2(int u, int f)
{
    top[u] = f;
    if(son[u]) dfs_2(son[u], f);
    else return;
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa[u]) continue;
        if(j == son[u]) continue;
        dfs_2(j, j);
    }
}

int lca(int x, int y)
{
    while(top[x] != top[y])
    {
        if(depth[top[x]] < depth[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return depth[x] < depth[y]? x: y;
}

int dis(int x, int y)
{
    return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}

void solve()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1; i < n; i++)
    {
        int u, v, ww;
        cin >> u >> v >> ww;
        add(u, v, ww), add(v, u, ww);
    }
    
    depth[1] = 1;
    dfs_1(1, -1);
    dfs_2(1, 1);
    
    for(int i = 1; i <= m; i++) cin >> v[i];
    for(int i = 2; i <= m; i++) res += dis(v[i], v[i - 1]);
    for(int i = 1; i <= m; i++)
    {
        if(i == 1) cout << res - dis(v[i], v[i + 1]) << ' ';
        else if(i == m) cout << res - dis(v[i], v[i - 1]) << ' ';
        else cout << res - dis(v[i], v[i - 1]) - dis(v[i], v[i + 1]) + dis(v[i - 1], v[i + 1]) << ' ';
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while(T--)
        solve();
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103

试题 J: 砍树

​ 时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分

【问题描述】

​ 给定一棵由 n n n 个结点组成的树以及 m m m 个不重复的无序数对 ( a 1 , b 1 ) , ( a 2 , b 2 ) , … , ( a m , b m ) (a_{1},b_{1}), (a_{2},b_{2}),\dots, (a_{m},b_{m}) (a1​,b1​),(a2​,b2​),…,(am​,bm​)，其中 a i a_{i} ai​ 互不相同， b i b_{i} bi​ 互不相同， a i , b j ( 1 ≤ i , j ≤ m ) a_{i} , b_{j}(1\le i, j\le m) ai​,bj​(1≤i,j≤m)。
​ 小明想知道是否能够选择一条树上的边砍断，使得对于每个 ( a i , b i ) (a_{i},b_{i}) (ai​,bi​) 满足 a i a_{i} ai​ 和 b i b_{i} bi​ 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 1 1 开始），否则输出 − 1 -1 −1。

【输入格式】

​ 输入共 n + m n+ m n+m 行，第一行为两个正整数 n , m n,m n,m。
​ 后面 n − 1 n−1 n−1 行，每行两个正整数 x i , y i x_{i},y_{i} xi​,yi​ 表示第 i i i 条边的两个端点。
​ 后面 m m m 行，每行两个正整数 a i , b i a_{i} , b_{i} ai​,bi​。

【输出格式】

​ 一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

【样例输入】

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5

【样例输出】

4

【样例说明】

​ 断开第 2 2 2 条边后形成两个连通块： { 3 , 4 } , { 1 , 2 , 5 , 6 } \left\{3,4 \right\},\left\{1,2,5,6\right\} {3,4},{1,2,5,6}，满足 3 3 3 和 6 6 6 不连通， 4 4 4 和 5 5 5 不连通。
​ 断开第 4 4 4 条边后形成两个连通块： { 1 , 2 , 3 , 4 } , { 5 , 6 } \left\{1,2,3,4\right\},\left\{5,6\right\} {1,2,3,4},{5,6}，同样满足 3 3 3 和 6 6 6 不连通， 4 4 4 和 5 5 5 不连通。
​ 4 4 4 编号更大，因此答案为 4 4 4。

【评测用例规模与约定】

​ 对于 30 30 30% 的数据，保证 1 < n ≤ 1000 1 < n \le 1000 1<n≤1000。
​ 对于 100 100 100% 的数据，保证 $1 < n \le 10^{5},1 ≤ m \le \frac{n}{2} $。

笨蒟蒻的个人题解

当时写这个的时候一点都不会，没啥水平，只会骗分。ok，然后说说如何思考本题。

思考一下，每两个结点之间都经过那一条边，那个边假如被经过了 m m m 次，那砍掉就能使得不连通，输出众多边的最小编号即可，反之无解。这就有思路了。

当然我们不可能一个一个边往上找，要用差分的方法，在最近公共祖先那个边 − 2 -2 −2，两个结点 + 1 +1 +1，这样即完成了差分操作，最后累计求和即可。

AC_Code

方法一：LCA – 倍增 + 树上差分
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define fi first
#define se second
typedef pair<int, int>PII;
const int N = 1e5 + 10, M = 2 * N;

int e[M], ne[M], h[N], idx;
int depth[N], fa[N][18];
int q[N], st[N];
int n, m, cnt, ans = -1;
map<PII, int>mp;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs(int root)
{
    memset(depth, inf, sizeof(depth));
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q[++tt] = j;
                for(int k = 1; k <= 17; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b)
{
    if(depth[a] < depth[b]) swap(a, b);
    for(int k = 17; k >= 0; k--)
        if(depth[fa[a][k]] >= depth[b]) a = fa[a][k];
    if(a == b) return a;
    
    for(int k = 17; k >= 0; k--)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}
int dfs(int u, int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        st[u] += st[j];
    }
}
signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%lld%lld", &a, &b);
        add(a, b), add(b, a);
        mp[{a, b}] = mp[{b, a}] = i;
    }
    
    bfs(1);
    
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%lld%lld", &a, &b);
        int u = lca(a, b);
        st[a]++, st[b]++, st[u]-=2;
    }
    
    dfs(1, -1);
    
    for(int i = 1; i <= n; i++)
    {
        if(st[i] == m)
        {
            int u = i, v = fa[u][0];
            ans = max(ans, mp[{u, v}]);
        }
    }
    
    cout << ans << endl;
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
方法二：LCA – tarjan + 树上差分
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define int long long
#define pb push_back
#define inf 0x3f3f3f3f
#define fi first
#define se second
typedef pair<int, int>PII;
const int N = 1e5 + 10, M = N * 2;

int n, m, ans = -1;
int e[M], ne[M], h[N], idx;
int p[N], st[N], f[N], father[N];
vector<int>query[N];
map<PII, int>mp;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void tarjan(int u)
{
    st[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }
    
    for(auto y: query[u])
    {
        if(st[y] == 2)
        {
            int anc = find(y);
            f[u]++, f[y]++, f[anc] -= 2;
        }
    }
    st[u] = 2;
}
void dfs(int u, int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        father[j] = u;
        dfs(j, u);
        f[u] += f[j];
    }
}
signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    memset(father, -1, sizeof(father));
    for(int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%lld%lld", &a, &b);
        add(a, b), add(b, a);
        mp[{a, b}] = mp[{b, a}] = i;
    }
    
    for(int i = 1; i < N; i++) p[i] = i;
    
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%lld%lld", &a, &b);
        query[a].pb(b);
        query[b].pb(a);
    }
    
    tarjan(1);
    dfs(1, -1);

    for(int i = 1; i <= n; i++)
    {
        if(f[i] == m)
        {
            int uu = i, vv = father[uu];
            ans = max(ans, mp[{uu, vv}]);
        }
    }
    cout << ans << endl;
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
方法三：LCA – 树剖 + 树上差分
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define int long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
typedef pair<int, int>PII;
const int N = 1e5 + 10, M = N * 2;

int n, m, ans = -1;
int e[M], ne[M], h[N], idx;
int depth[N], son[N], fa[N], siz[N], top[N], st[N];
map<PII, int> mp;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs_1(int u, int f)
{
    son[u] = 0, fa[u] = f, siz[u] = 1;
    if(f != -1) depth[u] = depth[f] + 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == f) continue;
        dfs_1(j, u);
        siz[u] += siz[j];
        if(siz[son[u]] < siz[j]) son[u] = j;
    }
}

void dfs_2(int u, int f)
{
    top[u] = f;
    if(son[u]) dfs_2(son[u], f);
    else return;
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa[u]) continue;
        if(j == son[u]) continue;
        dfs_2(j, j);
    }
}

void dfs_3(int u, int f)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == f) continue;
        dfs_3(j, u);
        st[u] += st[j];
    }
}

int lca(int x, int y)
{
    while(top[x] != top[y])
    {
        if(depth[top[x]] < depth[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return depth[x] < depth[y]? x: y;
}

void solve()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
        mp[{a, b}] = mp[{b, a}] = i;
    }
    
    depth[1] = 1;
    dfs_1(1, -1);
    dfs_2(1, 1);
    
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        st[a]++, st[b]++, st[lca(a, b)] -= 2;
    }
    
    dfs_3(1, -1);
    
    for(int i = 1; i < n; i++)
        if(st[i] == m) ans = max(ans, mp[{i, fa[i]}]);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while(T--)
        solve();
    return 0;
}

  • 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
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/494385
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号