第十四届蓝桥杯 C/C++ 省赛 B 组题解

一共两道填空题，八道程序设计题。

A:日期统计（5 分）

题意：

小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示：

5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为 8；
这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。

请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。

解法：

先按照题目要求找到第一个 2023 的位置：

5 6 8 6 9 1 6 1 -2- 4 9 1 9 8 2 3 6 4 7 7 5 9 5 -0- 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 -2- 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 -3- 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

删去这个位置之前的所有数

3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3

在剩余的数上枚举月份和日期。

注意到剩余的数不会产生 30 日和 31 日，也不会产生 2 月 29 日。所以不需要特判。

#include <bits/stdc++.h>
using namespace std;
int a[50];
bool f[2][10][3][10];
int main(){
    int n=0;
    int x=0;
    while(x!=-1){ cin>>x; a[++n]=x;}
    --n;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>1)continue;
        for(int j=i+1;j<=n;j++){
            if(a[i]==0&&a[j]==0)continue;
            if(a[i]==1&&a[j]>2)continue;
            for(int k=j+1;k<=n;k++){
                if(a[k]>2)continue;
                for(int m=k+1;m<=n;m++){
                    if(a[k]==0&&a[m]==0)continue;
                    if(f[a[i]][a[j]][a[k]][a[m]])continue;
                    ++ans; f[a[i]][a[j]][a[k]][a[m]]=1;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

答案是 235

B:01 串的熵（5 分）

题意：

信息熵是信息论中的一个重要概念，用来量化信息的不确定性。在 01 串中，信息熵可以用来衡量 0 和 1 出现的概率分布。对于一个长度为 n 的 01 串，其信息熵 H(S) 的计算公式为：

H(S) = -\sum p(x_i) \log_2(p(x_i))

其中，p(0) 和 p(1) 分别表示 0 和 1 在串中出现的概率。

比如，对于 S = 100 来说，

H(S) = -\frac{1}{3}\log_2(\frac{1}{3}) - \frac{2}{3}\log_2(\frac{2}{3}) - \frac{2}{3}\log_2(\frac{2}{3}) = 1.3083

假设我们有一个长度为 23333333 的 01 串，其信息熵为 11625907.5798，并且 0 的出现次数比 1 少。我们需要计算这个 01 串中 0 出现的次数。

解法：

令 n = 23333333 假设 0 出现的次数是 a 那么 1 出现的次数 b = n - a H(S) = -a * (a/n) * log2(a/n) - b * (b/n) * log2(b/n)

枚举 a 使得 H(S) = 11625907.5798 即可

#include <bits/stdc++.h>
using namespace std;
int main(){
    double n=23333333;
    double ans=11625907.5798;
    double mn=ans,mi=-1;
    for(int i=1;i<n;i++){
        double a=i;
        double b=n-a;
        double anss=-(a*(a/n)*log2(a/n)+b*(b/n)*log2(b/n));
        anss-=ans;
        if(anss<0) anss=-anss;
        if(anss<mn){ mn=anss; mi=i;}
    }
    printf("%.8lf %.0lf",mn,mi);
    return 0;
}

答案是 11027421

C:冶炼金属（10 分）

题目描述

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 N，表示冶炼记录的数目。

接下来输入 N 行，每行两个整数 A,B，含义如题目所述。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

20 25

说明/提示

【样例说明】

当 V=20 时，有：⌊75/20⌋=3, ⌊53/20⌋=2, ⌊59/20⌋=2，可以看到符合所有冶炼记录。

当 V=25 时，有：⌊75/25⌋=3, ⌊53/25⌋=2, ⌊59/25⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

【评测用例规模与约定】

对于 30% 的评测用例，1≤N≤10^2。

对于 60% 的评测用例，1≤N≤10^3。

对于 100% 的评测用例，1≤N≤10^4，1≤B≤A≤10^9。

解法：

根据题意直接枚举 V，尝试得部分分。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    vector<int>a(n+1),b(n+1);
    for(int i=1;i<=n;i++){ cin>>a[i]>>b[i];}
    int l=-1,r=-1;
    for(int v=1;;v++){
        bool f=0;
        for(int i=1;i<=n;i++){
            if(a[i]/v==b[i])continue; f=1;break;
        }
        if(f){if(l!=-1)break;continue;}
        if(l==-1) l=v; r=v;
    }
    cout<<l<<' '<<r<<'\n';
    return 0;
}

数据太水了，直接通过本题。

不过还是考虑如何优化，经过分析可以发现：对于给出的每组 A 和 B，Vmax=⌊A/B⌋，Vmin=⌊A/(B+1)⌋+1。如果求出每组 Vmax 的最小值，和每组 Vmin 的最大值，就是最终答案。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    int l=-1,r=1000000000;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        l=max(l,a/(b+1)+1); r=min(r,a/b);
    }
    cout<<l<<' '<<r<<'\n';
    return 0;
}

另外本题还有通过两次二分 V，分别求出 V 的最小值和最大值的写法。可以自己尝试，此处不再赘述。

D:飞机降落（10 分）

题目描述

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晩可以于 Ti+Di 时刻开始降落。降落过程需要 Li 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

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

输入格式

输入包含多组数据。

第一行包含一个整数 T，代表测试数据的组数。

对于每组数据，第一行包含一个整数 N。

以下 N 行，每行包含三个整数 Ti,Di,Li。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

YES NO

说明/提示

【样例说明】

对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

【评测用例规模与约定】

对于 30% 的数据，N≤2。

对于 100% 的数据，1≤T≤10，1≤N≤10，0≤Ti,Di,Li≤10^5。

解法：

数据范围很小，直接搜索即可

#include <bits/stdc++.h>
using namespace std;
int n;
int t[11],d[11],l[11];
bool f;
bool v[11];
void dfs(int ti,int k){
    if(k==n){ f=1;return;}
    for(int i=1;i<=n;i++){
        if(v[i])continue;
        if(t[i]+d[i]<ti)return;
        v[i]=1;
        dfs(max(ti,t[i])+l[i],k+1);
        v[i]=0;
        if(f)break;
    }
}
int main(){
    int m; cin>>m;
    while(m--){
        f=0; cin>>n;
        for(int i=1;i<=n;i++){ cin>>t[i]>>d[i]>>l[i];}
        dfs(-1,0);
        if(f)puts("YES");else puts("NO");
    }
    return 0;
}

E:接龙数列（15 分）

题目描述

对于一个长度为 K 的整数数列：A1,A2,…,AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字（2≤i≤K）。

例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A1,A2,…,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…,AN。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

5
11 121 22 12 2023

输出 #1

说明/提示

【样例说明】

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

【评测用例规模与约定】

对于 20% 的数据，1≤N≤20。

对于 50% 的数据，1≤N≤10^4。

对于 100% 的数据，1≤N≤10^5，1≤Ai≤10^9。所有 Ai 保证不包含前导 0。

解法：

首先可以发现对于每个 Ai 只有最左和最右两个数字有用，所以输入时可以直接把中间的去掉。

又因为删去最少的数字，和保留最多的数字是一样的，所以可以转化为求最长的接龙数列。

基于这个最容易想到的是，直接搜索：

#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011],r[100011];
void f(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}
int ans=0;
void dfs(int x,int k){ ans=max(ans,k);for(int i=x+1;i<=n;i++){if(x==0||l[i]==r[x]){dfs(i,k+1);}}}
int main(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x);}dfs(0,0); cout<<n-ans;return 0;}

时间复杂度：O(2^n) 可以通过 20% 的数据。

重新思考这道题，用 s(x) 表示 n=x 时最长接龙序列长度。从 n=1 时开始考虑，此时最长接龙序列长度显然为 1。即 s(1)=1

接下来考虑 n 增加 1 时，最长接龙序列的变化。如果增加的数不能和前面的数接龙，那么答案显然不变，即 s(n+1)=s(n)。如果可以和前面的某个数假设为 Ai 接龙，那答案应该取 s(n) 和 s(i)+1 中的最大值。即 s(n+1)=max(s(n),s(i)+1)

根据上面的分析，可以写出代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011],r[100011];
void f(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}
int s[100011];
int ans;
int main(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x); s[i]=1;}
for(int i=1;i<=n;i++){
    for(int j=1;j<i;j++){
        if(l[i]==r[j]){ s[i]=max(s[i],s[j]+1);}
    }
} ans=0;
for(int i=1;i<=n;i++){ ans=max(ans,s[i]);}
cout<<n-ans;return 0;}

时间复杂度：O(n^2) 可以通过 50% 的数据。

用 l[i] 表示 Ai 最左边的数，用 r[i] 表示 Ai 最右边的数。那么 Ai 能更新接龙序列一定以 l[i] 结尾。更新完序列变成以 r[i] 结尾。所以如果用 s[k] 表示以数字 k 结尾的最长序列长度。枚举到 Ai 时，s[r[i]]=max(s[r[i]],s[l[i]]+1)

#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011],r[100011];
void f(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}
int s[100011];
int ans;
int main(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x);}
for(int i=1;i<=n;i++){ s[r[i]]=max(s[r[i]],s[l[i]]+1);}
for(int i=0;i<=9;i++){ ans=max(ans,s[i]);}
cout<<n-ans;return 0;}

时间复杂度：O(n) 能通过所有数据。

F:岛屿个数（15 分）

题目描述

小蓝得到了一副大小为 M×N 的格子地图，可以将其视作一个只包含字符 0（代表海水）和 1（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。

在岛屿 AAA 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),…,(xk−1,yk−1)，其中 (x(i+1) mod k,y(i+1) mod k) 是由 (xi,yi) 通过上/下/左/右移动一次得来的（0≤i≤k−1），此时这 k 个格子就构成了一个「环」。如果另一个岛屿 BBB 所占据的格子全部位于这个「环」内部，此时我们将岛屿 BBB 视作是岛屿 AAA 的子岛屿。若 BBB 是 AAA 的子岛屿，CCC 又是 BBB 的子岛屿，那 CCC 也是 AAA 的子岛屿。

请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

输入格式

第一行一个整数 T，表示有 T 组测试数据。

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

1
3

说明/提示

【样例说明】

对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：

岛屿 2 在岛屿 1 的「环」内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。

对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有「环」。

【评测用例规模与约定】

对于 30% 的评测用例，1≤M,N≤10。

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

解法：

本题可以分为两部分解决：1：判断岛屿个数，2：判断一个岛屿是否为子岛屿。

观察题目描述，如果一个岛屿不是子岛屿，那么一定和地图最边界的 0 相接。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int s[55][55];
int dx1[8]={-1,-1,-1,0,+1,+1,+1,0};
int dy1[8]={-1,0,+1,+1,+1,0,-1,-1};
bool ck1(int x,int y){if(x<0||y<0||x>n+1||y>m+1||s[x][y]==-1)return 0;return 1;}
bool v[5005];
void dfs1(int x,int y){ s[x][y]=-1;int nx,ny;for(int i=0;i<8;i++){ nx=x+dx1[i]; ny=y+dy1[i];if(ck1(nx,ny)){int a=s[nx][ny];if(a!=0){ v[a]=1;}else{dfs1(nx,ny);}}}}
int k;
int dx2[4]={-1,0,+1,0};
int dy2[4]={0,+1,0,-1};
bool ck2(int x,int y){if(x<1||y<1||x>n||y>m||s[x][y]!=1)return 0;return 1;}
void dfs2(int x,int y){ s[x][y]=k;int nx,ny;for(int i=0;i<4;i++){ nx=x+dx2[i]; ny=y+dy2[i];if(ck2(nx,ny)){dfs2(nx,ny);}}}
int main(){
    int t; cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                char ch; cin>>ch; s[i][j]=ch-'0';
            }
        }
        k=2;
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i][j]==1){dfs2(i,j);++k;}
            }
        }
        dfs1(0,0);
        for(int i=2;i<k;i++){ ans+=v[i];}
        cout<<ans<<'\n';
        memset(s,0,sizeof(s));memset(v,0,sizeof(v));
    }
    return 0;
}

G:字串简写（20 分）

题目描述

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s，Lanqiao 简写成 L5o 等。

在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法 (长度小于 K 的字符串不配使用这种简写)。

给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数 K。

第二行包含一个字符串 S 和两个字符 c1 和 c2。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

4 abababdb a b

输出 #1

说明/提示

【样例说明】

符合条件的子串如下所示，中括号内是该子串：

[abab]abdb [ababab]db [abababdb] ab[abab]db ab[ababdb] abab[abdb]

【评测用例规模与约定】

对于 20% 的数据，2≤K≤|S|≤10^4。

对于 100% 的数据，2≤K≤|S|≤5×10^5。S 只包含小写字母。c1 和 c2 都是小写字母。 |S| 代表字符串 S 的长度。

解法：

直接对于每个 c1，枚举整个数组找到符合条件的 c2 并计数。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k; cin>>k; string s; cin>>s;
    char c1,c2; cin>>c1>>c2;
    int n=s.size();
    long long ans=0;
    for(int i=0;i<n;i++){
        if(s[i]==c1){
            for(int j=i+k-1;j<n;j++){
                if(s[j]==c2){++ans;}
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

时间复杂度：O(n^2)

使用前缀和优化，用一个数组记录 c1 的前缀数量。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int k; cin>>k; string s; cin>>s;
    char c1,c2; cin>>c1>>c2;
    int n=s.size();
    vector<int>a(n);
    long long ans=0;
    for(int i=0;i<n;i++){
        if(s[i]==c1){ a[i]++;}
        if(i) a[i]+=a[i-1];
        if(s[i]==c2){
            int l=i-k+1;
            if(l>=0){ ans+=a[l];}
        }
    }
    cout<<ans<<'\n';
    return 0;
}

时间复杂度：O(n)

需要注意，本题答案可能非常大超过 int 范围，所以要使用 long long 型存答案。

H:整数删除（20 分）

题目描述

给定一个长度为 N 的整数数列：A1,A2,…,AN。你要重复以下操作 K 次：

每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。

输出 K 次操作后的序列。

输入格式

第一行包含两个整数 N 和 K。

第二行包含 N 个整数，A1,A2,A3,…,AN。

输出格式

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

输入输出样例 #1

输入 #1

5 3
1 4 2 8 7

输出 #1

17 7

说明/提示

【样例说明】

数列变化如下，中括号里的数是当此操作中被选择的数：

[1] 4 2 8 7
5 [2] 8 7
7 [10] 7
17 7

【评测用例规模与约定】

对于 20% 的数据，1≤K<N≤10^4。

对于 100% 的数据，1≤K<N≤5×10^5，0≤Ai≤10^8。

解法：

首先尝试按照题意模拟

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k; cin>>n>>k;
    vector<long long>s(n+1);
    for(int i=1;i<=n;i++){ cin>>s[i];}
    while(k--){
        long long mn=-1;int p=-1;
        for(int i=1;i<=n;i++){
            if(s[i]==-1)continue;
            if(p==-1|| s[i]<mn){ p=i; mn=s[i];}
        }
        s[p]=-1;
        for(int i=p-1;i>=1;i--){if(s[i]!=-1){ s[i]+=mn;break;}}
        for(int i=p+1;i<=n;i++){if(s[i]!=-1){ s[i]+=mn;break;}}
    }
    for(int i=1;i<=n;i++){
        if(s[i]==-1)continue; cout<<s[i]<<' ';
    }
    return 0;
}

时间复杂度：O(N*M)

尝试优化，每次操作由三部分组成，一是找到最小值，二是删除最小值，三是最小值两侧数据增加。

分别进行优化：

因为数组是不停改变的，所以使用堆来优化找最小值。

删除最小值使用链表解决。

改变最小值两侧数据，在链表中很好处理，在堆中处理起来很麻烦。

注意到，如果这个数是最小值才有处理的必要。

所以在堆中改变数据这个操作可以在找最小值这一步完成。

如果和链表中的数据不同再进行处理，否则不需要处理。

至此三部分都优化完成。

#include <bits/stdc++.h>
using namespace std;
struct lb{int l,r;long long x;}s[500005];
#define pl pair<long long,int>
#define xx first
#define yy second
priority_queue<pl,vector<pl>,greater<pl>> q;
int main(){
    int n,k; cin>>n>>k;
    s[0].l=-1; s[0].r=1; s[0].x=-1;
    for(int i=1;i<=n;i++){
        cin>>s[i].x; s[i].l=i-1; s[i].r=i+1; q.push({s[i].x,i});
    }
    s[n].r=-1;
    for(int i=1;i<=k;i++){
        long long x=q.top().xx;int p=q.top().yy;
        while(s[p].x!=x){ x=s[p].x; q.pop(); q.push({x,p}); x=q.top().xx; p=q.top().yy;}
        q.pop();
        s[s[p].l].x+=x; s[s[p].r].x+=x;
        s[s[p].l].r=s[p].r; s[s[p].r].l=s[p].l;
        s[p].l=-1; s[p].r=-1;
    }
    int p=0;
    while(s[p].r!=-1){ p=s[p].r; cout<<s[p].x<<' ';
    }
    return 0;
}

时间复杂度：O(n log n)

I:景区导游（25 分）

题目描述

某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N−1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A1,A2,…,AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K−1 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A1,A2,…,Ai−1,Ai+1,…,AK(1≤i≤K)。

请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

输入格式

第一行包含 2 个整数 N 和 K。

以下 N−1 行，每行包含 3 个整数 u，v,t，代表景点 u 和 v 之间有摆渡车线路，花费 t 个单位时间。

最后一行包含 K 个整数 A1,A2,…,AK 代表原定游览线路。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

10 7 13 14

说明/提示

【样例说明】

原路线是 2→6→5→1。

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

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

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

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

【评测用例规模与约定】

对于 20% 的数据，2≤K≤N≤100。

对于 40% 的数据，2≤K≤N≤10^4。

对于 100% 的数据，2≤K≤N≤10^5，1≤u,v,Ai≤N，1≤t≤10^5。保证 Ai 两两不同。

解法：

本题难度较高，至少需要了解树的基本结构。

分析题目：

首先题目中没有规定树的根结点，而且根结点不影响答案，所以可以任意选择一个点作为根结点，这里选择 1 号结点。

接下来分析，要求出答案需要完成什么操作，可以发现只需要实现一个函数，来求出两个结点之间的最短距离。

根据树的结构，x 到 y 的距离，可以分解成，x 到根结点的距离加上 y 到根节点的距离，减去二倍的 x 和 y 到根结点的公共距离。

x 和 y 到根结点的公共距离，和某个点到根结点的距离是相同的，这个点叫做 x 和 y 的最近公共祖先（LCA）。

为了方便理解，这里用自然语言阐述一下最近公共祖先怎么求。

假设要求 x 和 y 的最近公共祖先，因为 x 和 y 的顺序不影响结果，为了方便说明不妨令 x 的深度小于等于 y 的深度。也就是在树的结构中，x 不在 y 的下方。

首先，不断找 y 的父结点作为新的 y 直到 y 和 x 深度一样。这一步是因为，x 和 y 的最近公共祖先，深度一定不大于 x。

如果此时 x 和 y 相等，说明 x 和 y 的最近公共祖先就是 x，即 y 在 x 的子树里。

如果此时 x 和 y 不相等，那么就同时找 x，y 两个结点的父结点作为新的，x 和 y，直到两点相等，此时就找到了，x 和 y 的最近公共祖先。

理解了如何求 x 和 y 的最近公共祖先，按照题意依次求出答案即可。

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int>>s[100005];
#define xx first
#define ww second
int h[100005];
long long d[100005];
int f[100005];
void dfs(int u){
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx]=u; d[v.xx]=d[u]+v.ww;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    while(h[x]!=h[y]){ y=f[y];}
    if(x==y){return x;}
    while(x!=y){ x=f[x]; y=f[y];}
    return x;
}
long long dist(int x,int y){
    if(x==0||y==0)return 0;
    int m=lca(x,y);
    long long sum=d[x]+d[y]-2*d[m];
    return sum;
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w; s[u].push_back({v,w}); s[v].push_back({u,w});
    }
    h[1]=1;dfs(1);
    vector<int>p(k+1);
    for(int i=1;i<=k;i++){ cin>>p[i];}
    long long ans=0;
    for(int i=1;i<=k;i++){
        ans=0;int l=0;
        for(int j=1;j<=k;j++){
            if(i==j)continue; ans+=dist(l,p[j]); l=p[j];
        }
        cout<<ans<<' ';
    }
    return 0;
}

时间复杂度：O(n*k^2)

可以通过 20% 数据。

思考如何优化，注意到跳过 Ai 后的距离，可以根据不跳过的原始总距离更改得到。

假如原始总距离为 ans，那么跳过 Ai 后的距离，就是 ans 减去 Ai−1 到 Ai 的距离和 Ai 到 Ai+1 的距离，加上 Ai−1 到 Ai+1 的距离。

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int>>s[100005];
#define xx first
#define ww second
int h[100005];
long long d[100005];
int f[100005];
void dfs(int u){
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx]=u; d[v.xx]=d[u]+v.ww;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    while(h[x]!=h[y]){ y=f[y];}
    if(x==y){return x;}
    while(x!=y){ x=f[x]; y=f[y];}
    return x;
}
long long dist(int x,int y){
    if(x==0||y==0)return 0;
    int m=lca(x,y);
    long long sum=d[x]+d[y]-2*d[m];
    return sum;
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w; s[u].push_back({v,w}); s[v].push_back({u,w});
    }
    h[1]=1;dfs(1);
    vector<int>p(k+1);
    for(int i=1;i<=k;i++){ cin>>p[i];}
    long long ans=0;
    for(int i=1;i<k;i++){ ans+=dist(p[i],p[i+1]);}
    for(int i=1;i<=k;i++){
        long long sum=ans; sum-=dist(p[i-1],p[i]); sum-=dist(p[i],p[i+1]); sum+=dist(p[i-1],p[i+1]);
        cout<<sum<<' ';
    }
    return 0;
}

时间复杂度：O(n*k)

可以通过 40% 的数据。

接下来，优化 LCA（最近公共祖先）的求法，这里给出最容易理解的倍增法。

同样先用自然语言阐述一遍方便理解：

倍增法和直接求的区别是，不是只记录每个结点的父结点，而是用 fi,j 记录，从 i 结点向上找 2^j 次父结点后的结点。

这样相当于预处理了很多操作。

同时根据 f 数组的含义也很容易推出 f 数组的求法：

显然 fi,0 代表 i 的父结点，之后，fi,j=ff_{i,j-1},j-1，这很好理解，因为 2^j=2^{j-1}+2^{j-1}，所以从 i 向上找 2^j 次父结点的结果和从 i 向上找 2^{j-1} 次之后再找 2^{j-1} 次父结点的结果一致。

在预处理完 f 数组之后，把求 LCA 过程中，找父结点的操作改为使用 f 数组找，可以将原本 O(n) 的时间复杂度降低至 O(log n)

#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,int>>s[100005];
#define xx first
#define ww second
int h[100005];
long long d[100005];
int f[100005][25];
void dfs(int u){
    for(int i=1;i<=24;i++){ f[u][i]=f[f[u][i-1]][i-1];}
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx][0]=u; d[v.xx]=d[u]+v.ww;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    for(int i=24;i>=0;i--){if(h[f[y][i]]>=h[x]){ y=f[y][i];}}
    if(x==y){return x;}
    for(int i=24;i>=0;i--){if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i];}}
    return f[x][0];
}
long long dist(int x,int y){
    if(x==0||y==0)return 0;
    int m=lca(x,y);
    long long sum=d[x]+d[y]-2*d[m];
    return sum;
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w; s[u].push_back({v,w}); s[v].push_back({u,w});
    }
    h[1]=1;dfs(1);
    vector<int>p(k+1);
    for(int i=1;i<=k;i++){ cin>>p[i];}
    long long ans=0;
    for(int i=1;i<k;i++){ ans+=dist(p[i],p[i+1]);}
    for(int i=1;i<=k;i++){
        long long sum=ans; sum-=dist(p[i-1],p[i]); sum-=dist(p[i],p[i+1]); sum+=dist(p[i-1],p[i+1]);
        cout<<sum<<' ';
    }
    return 0;
}

时间复杂度：O(log n * k)

可以通过 100% 数据。

J:砍树（25 分）

题目描述

给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1,b1),(a2,b2),…,(am,bm)，其中 ai 互不相同，bi 互不相同，ai≠bj(1≤i,j≤m)。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai,bi) 满足 ai 和 bi 不连通，如果可以则输出应该断掉的边的编号 (编号按输入顺序从 1 开始)，否则输出 -1。

输入格式

输入共 n+m 行，第一行为两个正整数 n,m。

后面 n−1 行，每行两个正整数 xi,yi 表示第 i 条边的两个端点。

后面 m 行，每行两个正整数 ai,bi。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例说明】

断开第 2 条边后形成两个连通块：{3,4},{1,2,5,6}，满足 3 和 6 不连通，4 和 5 不连通。

断开第 4 条边后形成两个连通块：{1,2,3,4},{5,6}，同样满足 3 和 6 不连通，4 和 5 不连通。

4 编号更大，因此答案为 4。

【评测用例规模与约定】

对于 30% 的数据，保证 1<n≤10^3。

对于 100% 的数据，保证 1<n≤10^5，1≤m≤n/2。

解法：

思考在树上如果一条边去掉以后可以使得 a 和 b 不连通这条边应该有什么特点，显然这条边一定在 a 和 b 的最短路径上。

根据这点，如果存在某个边被 m 组数对代表的路径经过 m 次，那么这个边就是符合题意的答案。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>s[100005];
#define xx first
#define ii second
int id[100005];
int f[100005];
int h[100005];
int cnt[100005];
void dfs(int u){
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx]=u; id[v.xx]=v.ii;
        dfs(v.xx);
    }
}
void sol(int x,int y){
    if(h[x]>h[y])swap(x,y);
    while(h[x]!=h[y]){ cnt[id[y]]++; y=f[y];}
    if(x==y)return;
    while(x!=y){ cnt[id[x]]++; cnt[id[y]]++; x=f[x]; y=f[y];}
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v; s[u].push_back({v,i}); s[v].push_back({u,i});
    }
    h[1]=1;dfs(1);
    for(int i=1;i<=k;i++){
        int x,y; cin>>x>>y;sol(x,y);
    }
    for(int i=n-1;i>=1;i--){
        if(cnt[i]==k){ cout<<i;return 0;}
    }
    cout<<-1;return 0;
}

时间复杂度：O(n*m)

这个复杂度理论上应该是只能通过 30% 的数据，但本题数据较弱，这种写法可以通过 100% 的数据。

接下来思考如何优化，可以注意到，对 x 和 y 经过的路径计数，和求 x 和 y 的最近公共祖先的暴力写法是基本一致的。那么能不能根据这点优化呢？

显然是可以的，x 和 y 的最近公共祖先相当于一个终点，而 x 和 y 是两个起点，有起点和终点要对之间的所有数加 1，很容易想到差分。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>s[100005];
#define xx first
#define ii second
int id[100005];
int f[100005][25];
int h[100005];
int cnt[100005];
void dfs(int u){
    for(int i=1;i<=24;i++){ f[u][i]=f[f[u][i-1]][i-1];}
    for(auto v:s[u]){
        if(h[v.xx])continue; h[v.xx]=h[u]+1; f[v.xx][0]=u; id[v.xx]=v.ii;
        dfs(v.xx);
    }
}
int lca(int x,int y){
    if(h[x]>h[y])swap(x,y);
    for(int i=24;i>=0;i--){if(h[f[y][i]]>=h[x]){ y=f[y][i];}}
    if(x==y)return x;
    for(int i=24;i>=0;i--){if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i];}}
    return f[x][0];
}
void sol(int x,int y){
    int m=lca(x,y); cnt[id[x]]++; cnt[id[y]]++; cnt[id[m]]-=2;
}
void dfs2(int u,int fa){
    for(auto v:s[u]){
        if(v.xx==fa)continue;
        dfs2(v.xx,u); cnt[id[u]]+=cnt[id[v.xx]];
    }
}
int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v; s[u].push_back({v,i}); s[v].push_back({u,i});
    }
    h[1]=1;dfs(1);
    for(int i=1;i<=k;i++){
        int x,y; cin>>x>>y;sol(x,y);
    }
    dfs2(1,0);
    for(int i=n-1;i>=1;i--){
        if(cnt[i]==k){ cout<<i;return 0;}
    }
    cout<<-1;return 0;
}

时间复杂度：O(m*log n)

可以通过 100% 数据。

但这题依旧还有优化空间。

回头重新看题目，题目要求找到一个条边把所有的 ai，bi 分开，那么分开后产生的两个子树里一定一个只包含 ai，一个只包含 bi。

根据这点，把 ai 点权设为 1，bi 点权设为 -1，之后对每个结点求子树和，如果一个点的点权的绝对值为 m，那么这个点与父结点之间的边就是符合题意的边。

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>s[100005];
#define xx first
#define ii second
int cnt[100005];
int ans=-1;
int n,k;
void dfs(int u,int fa){
    for(auto v:s[u]){
        if(v.xx==fa)continue;
        dfs(v.xx,u); cnt[u]+=cnt[v.xx];
    }
    if(abs(cnt[u])==k){
        for(auto v:s[u]){
            if(v.xx==fa){ ans=max(ans,v.ii);}
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v; s[u].push_back({v,i}); s[v].push_back({u,i});
    }
    for(int i=1;i<=k;i++){
        int x,y; cin>>x>>y; cnt[x]=1; cnt[y]=-1;
    }
    dfs(1,0);
    cout<<ans;return 0;
}

时间复杂度：O(n)

总结：

这一届题目难度明显比上一届高很多，涉及的知识点也更复杂。不过如果基本的知识掌握的足够好，就算没学过复杂的知识，也是足够获奖的。

涉及知识点：

搜索，简单动态规划，前缀和，链表，堆，树（最近公共祖先，树上差分）