十四届蓝桥杯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>usingnamespace std;int a[50];bool f[2][10][3][10];intmain(){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;return0;}

答案是 235

B:01串的熵（5分）

题意：

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

H(S)=−∑1np(xi)log2(p(xi))H(S)=-\sum_{1}^{n}p(x_i)log_2(p(x_i))H(S)=−∑1n​p(xi​)log2​(p(xi​))

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

比如，对于 S = 100 来说，

H(S)=−13log2(13)−23log2(23)−23log2(23)=1.3083H(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.3083H(S)=−31​log2​(31​)−32​log2​(32​)−32​log2​(32​)=1.3083

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

解法：

令 n = 23333333
假设 0 出现的次数是 a
那么 1 出现的次数 b = n - a
H(S)=−a∗anlog2(an)−b∗bnlog2(bn)H(S)=-a*\frac{a}{n}log_2(\frac{a}{n})-b*\frac{b}{n}log_2(\frac{b}{n})H(S)=−a∗na​log2​(na​)−b∗nb​log2​(nb​)

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

#include<bits/stdc++.h>usingnamespace std;intmain(){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);return0;}

答案是 11027421

C:冶炼金属 （10分）

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 75 3 53 2 59 2 

输出 #1

20 25 

说明/提示

【样例说明】

当 V=20V=20V=20 时，有：⌊7520⌋=3,⌊5320⌋=2,⌊5920⌋=2\left\lfloor\frac{75}{20}\right\rfloor=3,\left\lfloor\frac{53}{20}\right\rfloor=2,\left\lfloor\frac{59}{20}\right\rfloor=2⌊2075​⌋=3,⌊2053​⌋=2,⌊2059​⌋=2，可以看到符合所有冶炼记录。

当 V=25V=25V=25 时，有：⌊7525⌋=3,⌊5325⌋=2,⌊5925⌋=2\left\lfloor\frac{75}{25}\right\rfloor=3,\left\lfloor\frac{53}{25}\right\rfloor=2,\left\lfloor\frac{59}{25}\right\rfloor=2⌊2575​⌋=3,⌊2553​⌋=2,⌊2559​⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 202020 更小或者比 252525 更大的符合条件的 VVV 值了。

【评测用例规模与约定】

对于 30%30 \%30% 的评测用例，1≤N≤1021 \leq N \leq 10^{2}1≤N≤102。

对于 60%60 \%60% 的评测用例，1≤N≤1031 \leq N \leq 10^{3}1≤N≤103。

对于 100%100 \%100% 的评测用例，1≤N≤1041 \leq N \leq 10^{4}1≤N≤104，1≤B≤A≤1091 \leq B \leq A \leq 10^{9}1≤B≤A≤109。

解法：

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

#include<bits/stdc++.h>usingnamespace std;intmain(){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';return0;}

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

不过还是考虑如何优化，经过分析可以发现：对于给出的每组 A 和 B，Vmax=⌊AB⌋V_{max}=\lfloor{\frac{A}{B}}\rfloorVmax​=⌊BA​⌋，Vmin=⌊AB+1⌋+1V_{min}=\lfloor{\frac{A}{B+1}}\rfloor+1Vmin​=⌊B+1A​⌋+1。
如果求出每组VmaxV_{max}Vmax​的最小值，和每组VminV_{min}Vmin​的最大值，就是最终答案。

#include<bits/stdc++.h>usingnamespace std;intmain(){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';return0;}

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

D:飞机降落 （10分）

题目描述

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

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

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

输入格式

输入包含多组数据。

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

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

以下 NNN 行，每行包含三个整数 Ti,Di,LiT_{i},D_{i},L_{i}Ti​,Di​,Li​。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

YES NO 

说明/提示

【样例说明】

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

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

【评测用例规模与约定】

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

对于 100%100 \%100% 的数据，1≤T≤101 \leq T \leq 101≤T≤10，1≤N≤101 \leq N \leq 101≤N≤10，0≤Ti,Di,Li≤1050 \leq T_{i},D_{i},L_{i} \leq 10^{5}0≤Ti​,Di​,Li​≤105。

解法：

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

#include<bits/stdc++.h>usingnamespace std;int n;int t[11],d[11],l[11];bool f;bool v[11];voiddfs(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;}}intmain(){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");elseputs("NO");}return0;}

E:接龙数列（15分）

题目描述

对于一个长度为 KKK 的整数数列：A1,A2,…,AKA_{1},A_{2},\ldots,A_{K}A1​,A2​,…,AK​，我们称之为接龙数列当且仅当 AiA_{i}Ai​ 的首位数字恰好等于 Ai−1A_{i-1}Ai−1​ 的末位数字（2≤i≤K2 \leq i \leq K2≤i≤K）。

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

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

输入格式

第一行包含一个整数 NNN。

第二行包含 NNN 个整数 A1,A2,…,ANA_{1},A_{2},\ldots,A_{N}A1​,A2​,…,AN​。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

5 11 121 22 12 2023 

输出 #1

1 

说明/提示

【样例说明】

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

【评测用例规模与约定】

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

对于 50%50 \%50% 的数据，1≤N≤1041 \leq N \leq 10^41≤N≤104。

对于 100%100 \%100% 的数据，1≤N≤1051 \leq N \leq 10^{5}1≤N≤105，1≤Ai≤1091 \leq A_{i} \leq 10^{9}1≤Ai​≤109。所有 AiA_{i}Ai​ 保证不包含前导 0。

解法：

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

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

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

#include<bits/stdc++.h>usingnamespace std;int n;int l[100011],r[100011];voidf(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}int ans=0;voiddfs(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);}}}intmain(){ cin>>n;for(int i=1;i<=n;i++){int x; cin>>x;f(i,x);}dfs(0,0); cout<<n-ans;return0;}

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

可以通过20%的数据。

重新思考这道题，用s(x)表示n=x时最长接龙序列长度。

从n=1时开始考虑，此时最长接龙序列长度显然为1。即s(1)=1

接下来考虑n增加1时，最长接龙序列的变化。

如果增加的数不能和前面的数接龙，那么答案显然不变，即s(n+1)=s(n)。

如果可以和前面的某个数假设为AiA_iAi​接龙，那答案应该取s(n)和s(i)+1中的最大值。

即s(n+1)=max(s(n),s(i)+1)

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

#include<bits/stdc++.h>usingnamespace std;int n;int l[100011],r[100011];voidf(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}int s[100011];int ans;intmain(){ 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;return0;}

时间复杂度：O(n2n^2n2)

可以通过50%的数据。

用l[i]表示AiA_{i}Ai​最左边的数，用r[i]表示AiA_{i}Ai​最右边的数。

那么AiA_{i}Ai​能更新接龙序列一定以l[i]结尾。

更新完序列变成以r[i]结尾。

所以如果用s[k]表示以数字k结尾的最长序列长度。

枚举到AiA_{i}Ai​时，s[r[i]]=max(s[r[i]],s[l[i]]+1)s[r[i]]=max(s[r[i]],s[l[i]]+1)s[r[i]]=max(s[r[i]],s[l[i]]+1)

#include<bits/stdc++.h>usingnamespace std;int n;int l[100011],r[100011];voidf(int i,int x){ r[i]=x%10;while(x>9){ x/=10;} l[i]=x;}int s[100011];int ans;intmain(){ 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;return0;}

时间复杂度：O(nnn)

能通过所有数据。

F:岛屿个数（15分）

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1 3 

说明/提示

【样例说明】

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

01111 11001 10201 10001 11111 

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

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

111111 100001 020301 100001 111111 

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

【评测用例规模与约定】

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

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

解法：

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

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

#include<bits/stdc++.h>usingnamespace 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};boolck1(int x,int y){if(x<0||y<0||x>n+1||y>m+1||s[x][y]==-1)return0;return1;}bool v[5005];voiddfs1(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};boolck2(int x,int y){if(x<1||y<1||x>n||y>m||s[x][y]!=1)return0;return1;}voiddfs2(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);}}}intmain(){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));}return0;}

G:字串简写（20分）

题目描述

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

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

给定一个字符串 SSS 和两个字符 c1c_{1}c1​ 和 c2c_{2}c2​，请你计算 SSS 有多少个以 c1c_{1}c1​ 开头 c2c_{2}c2​ 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数 KKK。

第二行包含一个字符串 SSS 和两个字符 c1c_{1}c1​ 和 c2c_{2}c2​。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

4 abababdb a b 

输出 #1

6 

说明/提示

【样例说明】

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

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

【评测用例规模与约定】

对于 20%20 \%20% 的数据，2≤K≤∣S∣≤1042 \leq K \leq|S| \leq 10^42≤K≤∣S∣≤104。

对于 100%100 \%100% 的数据，2≤K≤∣S∣≤5×1052 \leq K \leq|S| \leq 5 \times 10^{5}2≤K≤∣S∣≤5×105。SSS 只包含小写字母。c1c_{1}c1​ 和 c2c_{2}c2​ 都是小写字母。

∣S∣|S|∣S∣ 代表字符串 SSS 的长度。

解法：

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

#include<bits/stdc++.h>usingnamespace std;intmain(){int k; cin>>k; string s; cin>>s;char c1,c2; cin>>c1>>c2;int n=s.size();longlong 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';return0;}

时间复杂度：O(n2n^2n2)

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

#include<bits/stdc++.h>usingnamespace std;intmain(){int k; cin>>k; string s; cin>>s;char c1,c2; cin>>c1>>c2;int n=s.size(); vector<int>a(n);longlong 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';return0;}

时间复杂度：O(nnn)

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

H:整数删除（20分）

题目描述

给定一个长度为 NNN 的整数数列：A1,A2,…,ANA_{1},A_{2},\ldots,A_{N}A1​,A2​,…,AN​。你要重复以下操作 KKK 次：

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

输出 KKK 次操作后的序列。

输入格式

第一行包含两个整数 NNN 和 KKK。

第二行包含 NNN 个整数，A1,A2,A3,…,ANA_{1},A_{2},A_{3},\ldots,A_{N}A1​,A2​,A3​,…,AN​。

输出格式

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

输入输出样例 #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%20 \%20% 的数据，1≤K<N≤1041 \leq K<N \leq 10^41≤K<N≤104。

对于 100%100 \%100% 的数据，1≤K<N≤5×1051 \leq K<N \leq 5 \times 10^{5}1≤K<N≤5×105，0≤Ai≤1080 \leq A_{i} \leq 10^{8}0≤Ai​≤108。

解法：

首先尝试按照题意模拟

#include<bits/stdc++.h>usingnamespace std;intmain(){int n,k; cin>>n>>k; vector<longlong>s(n+1);for(int i=1;i<=n;i++){ cin>>s[i];}while(k--){longlong 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]<<' ';}return0;}

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

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

分别进行优化：

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

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

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

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

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

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

至此三部分都优化完成。

#include<bits/stdc++.h>usingnamespace std;structlb{int l,r;longlong x;}s[500005];#defineplipair<longlong,int>#definexxfirst#defineyysecond priority_queue<pli,vector<pli>,greater<pli>> q;intmain(){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++){longlong 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<<' ';}return0;}

时间复杂度：O(nlog⁡nn \log nnlogn)

I:景区导游（25分）

题目描述

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

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

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

输入格式

第一行包含 222 个整数 NNN 和 KKK。

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

最后一行包含 KKK 个整数 A1,A2,…,AKA_{1},A_{2},\ldots,A_{K}A1​,A2​,…,AK​ 代表原定游览线路。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

10 7 13 14 

说明/提示

【样例说明】

原路线是 2→6→5→12 \rightarrow 6 \rightarrow 5 \rightarrow 12→6→5→1。

当跳过 222 时，路线是 6→5→16 \rightarrow 5 \rightarrow 16→5→1，其中 6→56 \rightarrow 56→5 花费时间 3+2+2=73+2+2=73+2+2=7，5→15 \rightarrow 15→1 花费时间 2+1=32+1=32+1=3，总时间花费 101010。

当跳过 666 时，路线是 2→5→12 \rightarrow 5 \rightarrow 12→5→1，其中 2→52 \rightarrow 52→5 花费时间 1+1+2=41+1+2=41+1+2=4，5→15 \rightarrow 15→1 花费时间 2+1=32+1=32+1=3，总时间花费 777。

当跳过 555 时，路线是 2→6→12 \rightarrow 6 \rightarrow 12→6→1，其中 2→62 \rightarrow 62→6 花费时间 1+1+2+3=71+1+2+3=71+1+2+3=7，6→16 \rightarrow 16→1 花费时间 3+2+1=63+2+1=63+2+1=6 ，总时间花费 131313。

当跳过 111 时，路线时 2→6→52 \rightarrow 6 \rightarrow 52→6→5，其中 2→62 \rightarrow 62→6 花费时间 1+1+2+3=71+1+2+3=71+1+2+3=7，6→56 \rightarrow 56→5 花费时间 3+2+2=73+2+2=73+2+2=7 ，总时间花费 141414。

【评测用例规模与约定】

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

对于 40%40 \%40% 的数据，2≤K≤N≤1042 \leq K \leq N \leq 10^{4}2≤K≤N≤104。

对于 100%100 \%100% 的数据，2≤K≤N≤1052 \leq K \leq N \leq 10^{5}2≤K≤N≤105，1≤u,v,Ai≤N1 \leq u,v,A_{i} \leq N1≤u,v,Ai​≤N，1≤t≤1051 \leq t \leq 10^{5}1≤t≤105。保证 AiA_{i}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>usingnamespace std; vector<pair<longlong,int>>s[100005];#definexxfirst#definewwsecondint h[100005];longlong d[100005];int f[100005];voiddfs(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);}}intlca(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;}longlongdist(int x,int y){if(x==0||y==0)return0;int m=lca(x,y);longlong sum=d[x]+d[y]-2*d[m];return sum;}intmain(){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];}longlong 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<<' ';}return0;}

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

可以通过 20% 数据。

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

假如原始总距离为ansansans，那么跳过AiA_iAi​后的距离，就是ansansans减去 Ai−1A_{i-1}Ai−1​到AiA_iAi​ 的距离 和 AiA_iAi​到Ai+1A_{i+1}Ai+1​ 的距离，加上 Ai−1A_{i-1}Ai−1​到Ai+1A_{i+1}Ai+1​ 的距离。

#include<bits/stdc++.h>usingnamespace std; vector<pair<longlong,int>>s[100005];#definexxfirst#definewwsecondint h[100005];longlong d[100005];int f[100005];voiddfs(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);}}intlca(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;}longlongdist(int x,int y){if(x==0||y==0)return0;int m=lca(x,y);longlong sum=d[x]+d[y]-2*d[m];return sum;}intmain(){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];}longlong ans=0;for(int i=1;i<k;i++){ ans+=dist(p[i],p[i+1]);}for(int i=1;i<=k;i++){longlong 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<<' ';}return0;}

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

可以通过40%的数据。

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

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

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

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

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

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

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

#include<bits/stdc++.h>usingnamespace std; vector<pair<longlong,int>>s[100005];#definexxfirst#definewwsecondint h[100005];longlong d[100005];int f[100005][25];voiddfs(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);}}intlca(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];}longlongdist(int x,int y){if(x==0||y==0)return0;int m=lca(x,y);longlong sum=d[x]+d[y]-2*d[m];return sum;}intmain(){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];}longlong ans=0;for(int i=1;i<k;i++){ ans+=dist(p[i],p[i+1]);}for(int i=1;i<=k;i++){longlong 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<<' ';}return0;}

时间复杂度：O(logn∗klog n * klogn∗k)

可以通过100%数据。

J:砍树（25分）

题目描述

给定一棵由 nnn 个结点组成的树以及 mmm 个不重复的无序数对 (a1,b1),(a2,b2),…,(am,bm)\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)(a1​,b1​),(a2​,b2​),…,(am​,bm​)，其中 aia_{i}ai​ 互不相同，bib_{i}bi​ 互不相同，ai≠bj(1≤i,j≤m)a_{i} \neq b_{j}(1 \leq i,j \leq m)ai​=bj​(1≤i,j≤m)。

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

输入格式

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

后面 n−1n-1n−1 行，每行两个正整数 xi,yix_{i},y_{i}xi​,yi​ 表示第 iii 条边的两个端点。

后面 mmm 行，每行两个正整数 ai,bia_{i},b_{i}ai​,bi​。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

4 

说明/提示

【样例说明】

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

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

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

【评测用例规模与约定】

对于 30%30 \%30% 的数据，保证 1<n≤1031<n \leq 10^31<n≤103。

对于 100%100 \%100% 的数据，保证 1<n≤1051<n \leq 10^{5}1<n≤105，1≤m≤n21 \leq m \leq \frac{n}{2}1≤m≤2n​。

解法：

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

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

#include<bits/stdc++.h>usingnamespace std; vector<pair<int,int>>s[100005];#definexxfirst#defineiisecondint id[100005];int f[100005];int h[100005];int cnt[100005];voiddfs(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);}}voidsol(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];}}intmain(){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;return0;}} cout<<-1;return0;}

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

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

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

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

#include<bits/stdc++.h>usingnamespace std; vector<pair<int,int>>s[100005];#definexxfirst#defineiisecondint id[100005];int f[100005][25];int h[100005];int cnt[100005];voiddfs(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);}}intlca(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];}voidsol(int x,int y){int m=lca(x,y); cnt[id[x]]++; cnt[id[y]]++; cnt[id[m]]-=2;}voiddfs2(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]];}}intmain(){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;return0;}} cout<<-1;return0;}

时间复杂度：O(m∗log⁡nm*\log nm∗logn)

可以通过100%数据。

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

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

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

#include<bits/stdc++.h>usingnamespace std; vector<pair<int,int>>s[100005];#definexxfirst#defineiisecondint cnt[100005];int ans=-1;int n,k;voiddfs(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);}}}}intmain(){ 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;return0;}

时间复杂度：O(n)

总结：

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

涉及知识点：

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