第十四届蓝桥杯C++B组复盘

  • A: 日期统计(5分)
    • 问题描述
    • 思路
  • B: 01 串的熵(5分)
    • 问题描述
    • 思路
  • C: 冶炼金属(10分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • D: 飞机降落(10分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • E: 接龙数列(15分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • F: 岛屿个数(15分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • G: 子串简写(20分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • H: 整数删除(20分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • I: 景区导游(25分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路
  • J: 砍树(25分)
    • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 样例说明
    • 评测用例规模与约定
    • 思路

这届蓝桥杯跟上届蓝桥杯一样,只有2个填空题,8个编程的大题。本届蓝桥杯我愿称之为四小时怒开九道题 。难度跟上届相比,没有那么多思维题,反倒板子题多了,不知道其他组是不是也是这样。
博客地址:https://blog.csdn.net/m0_46326495/article/details/130043563

A: 日期统计(5分)

问题描述

小蓝现在有一个长度为 100100100 的数组,数组中的每个元素的值都在 000 999 的范围之内。数组中的元素从左至右如下所示:

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

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

  1. 子序列的长度为8;
  2. 这个子序列可以按照下标顺序组成一个yyyymmdd 格式的日期,并且要求这个日期是2023 年中的某一天的日期,例如20230902,20231223。yyyy 表示年份,mm 表示月份,dd 表示天数,当月份或者天数的长度只有一位时需要一个前导零补充。
    请你帮小蓝计算下按上述条件一共能找到多少个不同的2023 年的日期。
    对于相同的日期你只需要统计一次即可。

思路

纯暴力的话就dfs,或者用8重循环。不妨再考虑下题目,由于对于相同的日期只需统计一次,因此可以查询每个2023年的日期能否由上面给的数字拼出来。这样既能有很好的效率,又能省去去重的过程。最终结果是235
具体代码如下

#include #include #include using namespace std;const int numbers[100] = {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};const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main() {int ans = 0;for (int i = 1; i <= 12; i++) {for (int j = 1; j <= days[i]; j++) {string str = "2023";if (i < 10)str += "0";str += to_string(i);if (j < 10)str += "0";str += to_string(j);int k = 0;for (int l = 0; l < 100 && k < 8; l++) {if (numbers[l] == str[k] - '0') k++;}if (k >= 8) ans++;}}cout << ans << endl;return 0;}

B: 01 串的熵(5分)

问题描述

对于一个长度为 nnn 010101 S = x1x2x3. . . xn S = x_1x_2x_3…x_nS=x1x2x3xn,香农信息熵的定义为 H ( S ) = − ∑1np ( xi)log ⁡2( p ( xi) )H(S)=-\sum^n_1p(x_i)\log_2(p(x_i))H(S)=1np(xi)log2(p(xi)),其中 p ( 0 ) , p ( 1 )p(0), p(1)p(0),p(1) 表示在这个 010101 串中 000 111 出现的占比。比如,对于 S = 100S = 100S=100 来说,信息熵 H ( S ) = − 13 log ⁡2( 13) − 23 log ⁡2( 23) − 23 log ⁡2( 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)=31log2(31)32log2(32)32log2(32)=1.3083。对于一个长度为 233333332333333323333333 010101 串,如果其信息熵为 11625907.579811625907.579811625907.5798,且 000 出现次数比 111 少,那么这个 010101 串中 000 出现了多少次?

思路

枚举一下0的个数,计算的时候要开double保证精度。结果是11027421(因为本题数据并不是很大,直接暴力枚举也可以,并不一定需要使用二分)

暴力枚举:

#include #include #include using namespace std;const int total = 23333333;const double H = 11625907.5798;int main() {for (int i = 0; i < total / 2; i++) {double ans = 0;ans -= 1.0 * i * i / total * log2(1.0 * i / total);ans -= 1.0 * (total - i) * (total - i) / total * log2(1.0 * (total - i) / total);if (abs(ans - H) < 1e-4) {cout << i << endl;return 0;}}return 0;}

二分:

#include #include #include using namespace std;const int total = 23333333;const double H = 11625907.5798;int main() {int l = 0, r = total / 2;while (l < r) {int mid = (l + r) >> 1;double ans = 0;ans -= 1.0 * mid * mid / total * log2(1.0 * mid / total);ans -= 1.0 * (total - mid) * (total - mid) / total * log2(1.0 * (total - mid) / total);if (abs(ans - H) < 1e-4) {cout << mid << endl;return 0;}if (ans > H) {r = mid;} else {l = mid + 1;}}return 0;}

C: 冶炼金属(10分)

问题描述

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

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

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

输入格式

第一行一个整数 NNN,表示冶炼记录的数目。
接下来输入 NNN 行,每行两个整数 AAA BBB,含义如题目所述。

输出格式

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

样例输入

3
75 3
53 2
59 2

样例输出

20 25

样例说明

V = 20V = 20V=20 时,有: ⌊ 7520= 3 ⌋\lfloor \frac{75}{20}=3 \rfloor2075=3 ⌊ 5320= 2 ⌋\lfloor \frac{53}{20}=2 \rfloor2053=2 ⌊ 5920= 2 ⌋\lfloor \frac{59}{20}=2 \rfloor2059=2可以看到符合所有冶炼记录。
V = 25V = 25V=25 时,有: ⌊ 7525= 3 ⌋\lfloor \frac{75}{25}=3 \rfloor2575=3 ⌊ 5325= 2 ⌋\lfloor \frac{53}{25}=2 \rfloor2553=2 ⌊ 5925= 2 ⌋\lfloor \frac{59}{25}=2 \rfloor2559=2可以看到符合所有冶炼记录。
且再也找不到比 202020 更小或者比 252525 更大的符合条件的 VVV 值了。

评测用例规模与约定

对于 30 %30\%30% 的评测用例, 1 ≤ N ≤ 1 02 1 ≤ N ≤ 10^21N102
对于 60 %60\%60% 的评测用例, 1 ≤ N ≤ 1 03 1 ≤ N ≤ 10^31N103
对于 100 %100\%100% 的评测用例, 1 ≤ N ≤ 1 04 1 ≤ N ≤ 10^41N104 1 ≤ B ≤ A ≤ 1 09 1 ≤ B ≤ A ≤ 10^91BA109

思路

感觉是个数学题,算一下即可。

#include#includeusing namespace std;int main() {int n;cin >> n;int ansMin = 0, ansMax = 1e9;while (n--) {int a, b;cin >> a >> b;ansMin = max(a / (b + 1) + 1, ansMin);ansMax = min(a / b, ansMax);}cout << ansMin << " " << ansMax << endl;return 0;}

D: 飞机降落(10分)

问题描述

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

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

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

输入格式

输入包含多组数据。
第一行包含一个整数 TTT,代表测试数据的组数。
对于每组数据,第一行包含一个整数 NNN
以下 NNN 行,每行包含三个整数: Ti T_iTi Di D_iDi Li L_iLi

输出格式

对于每组数据,输出 Y E SYESYES 或者 N ONONO,代表是否可以全部安全降落。

样例输入

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

样例输出

YES
NO

样例说明

对于第一组数据,可以安排第 333 架飞机于 000 时刻开始降落, 202020 时刻完成降落。安排第 222 架飞机于 202020 时刻开始降落, 303030 时刻完成降落。安排第 111 架飞机于 303030 时刻开始降落, 404040 时刻完成降落。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。

评测用例规模与约定

对于 30 %30\%30% 的评测用例, N ≤ 2N ≤ 2N2
对于 100 %100\%100% 的评测用例, 1 ≤ T ≤ 101 ≤ T ≤ 101T10 1 ≤ N ≤ 101 ≤ N ≤ 101N10 0 ≤ Ti, Di, Li≤ 1 05 0 ≤ T_i, D_i, L_i ≤ 10^50Ti,Di,Li105

思路

本来以为要贪心然后排序去做,手推了几个发现贪心不对,重新看了眼数据范围,发现是个纯暴力的题?

#include #include using namespace std;const int N = 10;bool st[N];int n;bool flag = false;int t[N], d[N], l[N];void dfs(int u, int last) {if (flag) return;if (u == n) {flag = true;return;}for (int i = 0; i < n; i++) {if (!st[i]) {if (t[i] + d[i] >= last) {st[i] = true;if (t[i] > last) dfs(u + 1, t[i] + l[i]);else dfs(u + 1, last + l[i]);st[i] = false;} else return;}}}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> l[i];for (int i = 0; i < N; i++) st[i] = false;flag = false;dfs(0, 0);if (flag) cout << "YES" << endl;else cout << "NO" << endl;}return 0;}

E: 接龙数列(15分)

问题描述

对于一个长度为 KKK 的整数数列: A1, A2, . . . , AK A_1, A_2,…, A_KA1,A2,,AK,我们称之为接龙数列当且仅当 Ai A_iAi 的首位数字恰好等于 A i − 1 A_{i−1}Ai1 的末位数字 ( 2 ≤ i ≤ K )(2 ≤ i ≤ K)(2iK)

例如 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, . . . , AN A_1, A_2,…, A_NA1,A2,,AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?

输入格式

第一行包含一个整数 NNN
第二行包含 NNN 个整数 A1, A2, . . . , AN A_1, A_2, … ,A_NA1,A2,,AN

输出格式

一个整数代表答案

样例输入

5
11 121 22 12 2023

样例输出

1

样例说明

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

评测用例规模与约定

对于 30 %30\%30% 的评测用例, 1 ≤ N ≤ 201 ≤ N ≤ 201N20
对于 50 %50\%50% 的评测用例, 1 ≤ N ≤ 1 04 1 ≤ N ≤ 10^41N104
对于 100 %100\%100% 的评测用例, 1 ≤ N ≤ 1 05 1 ≤ N ≤ 10^51N105 1 ≤ Ai≤ 1 09 1 ≤ A_i ≤ 10^91Ai109。所有 Ai A_iAi 保证不包含前导 000

思路

动态规划,定义 d p [ i ] [ j ]dp[i][j]dp[i][j]为用到第 iii个,结尾为 jjj最少要删掉的元素数量

#include#includeusing namespace std;typedef long long ll;typedef unsigned long long ull;const int N = 1e5 + 10;int dp[N][10];int a[N];int inline tou(int x) {while (x >= 10) {x /= 10;}return x;}int inline wei(int x) {return x % 10;}int main() {ios::sync_with_stdio(false);int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 0; i < N; i++) {for (int j = 0; j < 10; j++) {dp[i][j] = 0x3f3f3f3f;}}for (int i = 1; i <= n; i++) {int t = tou(a[i]);int w = wei(a[i]);for (int j = 1; j <= 9; j++) dp[i][j] = dp[i - 1][j] + 1;dp[i][w] = min(dp[i][w], dp[i - 1][t]);dp[i][w] = min(dp[i][w], i - 1);}int ans = dp[n][1];for (int i = 2; i <= 9; i++) ans = min(ans, dp[n][i]);cout << ans << endl;return 0;}

F: 岛屿个数(15分)

问题描述

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

在岛屿 AAA 所占据的格子中,如果可以从中选出 kkk 个不同的格子,使得他们的坐标能够组成一个这样的排列: ( x0, y0) , ( x1, y1) , . . . , ( x k − 1, y k − 1)(x_0, y_0), (x_1,y_1),…, (x_{k−1}, y_{k−1})(x0,y0),(x1,y1),,(xk1,yk1),其中 ( x ( i + 1 ) % k, y ( i + 1 ) % k)(x_{(i+1)\%k}, y_{(i+1)\%k})(x(i+1)%k,y(i+1)%k) 是由 ( xi, yi)(x_i, y_i)(xi,yi) 通过上/下/左/右移动一次得来的 ( 0 ≤ i ≤ k − 1 )(0 ≤ i ≤ k − 1)(0ik1),此时这 kkk个格子就构成了一个“环”。如果另一个岛屿 BBB 所占据的格子全部位于这个“环” 内部,此时我们将岛屿 BBB 视作是岛屿 AAA 的子岛屿。若 BBB AAA 的子岛屿, CCC 又是 BBB 的子岛屿,那 CCC 也是 AAA 的子岛屿。

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

输入格式

第一行一个整数 TTT,表示有 TTT 组测试数据。
接下来输入 TTT 组数据。对于每组数据,第一行包含两个用空格分隔的整数 MMM NNN 表示地图大小;接下来输入 MMM 行,每行包含 NNN 个字符,字符只可能是 ‘ 0 ’‘0’‘0’ ‘ 1 ’‘1’‘1’

输出格式

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

样例输入

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

样例输出

1
3

样例说明

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

01111
11001
10201
10001
11111

岛屿 222 在岛屿 111 的“环” 内部,所以岛屿 222 是岛屿 111 的子岛屿,答案为 111
对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:

111111
100001
020301
100001
111111

注意岛屿 333 并不是岛屿 111 或者岛屿 222 的子岛屿,因为岛屿 111 和岛屿 222 中均没有“环”。

评测用例规模与约定

对于 30 %30\%30% 的评测用例, 1 ≤ M , N ≤ 101 ≤ M,N ≤ 101M,N10
对于 100 %100\%100% 的评测用例, 1 ≤ T ≤ 10 , 1 ≤ M , N ≤ 501 ≤T≤ 10, 1 ≤ M,N ≤ 501T10,1M,N50

思路

这个题蛮有意思的,如果不考虑子岛屿的话,基本上是白送分题hhh。如果考虑子岛屿就需要判断是不是成环,以及另一个岛屿是不是在这个成环的岛屿中。不妨换个思路看,如果一个岛屿不在另一个岛屿中,则这个岛屿在有水的地方(为’0’的地方)一定是跟外界连通的(注意此处的连通包括对角线这种连通)。可以用这个思路去写代码会更简单一些。

#include#include#includeusing namespace std;typedef long long ll;const int dx[8] = {1, -1, 0, 0, -1, -1, 1, 1};const int dy[8] = {0, 0, 1, -1, -1, 1, -1, 1};int n, m;char graph[60][60];bool vis[60][60];bool fill(int A, int B) {for (int i = 0; i <= n + 1; i++) {for (int j = 0; j <= m + 1; j++) {vis[i][j] = false;}}queue<pair<int, int> > q;q.emplace(A, B);vis[A][B] = true;while (!q.empty()) {auto cur = q.front();q.pop();int x = cur.first, y = cur.second;for (int i = 0; i < 8; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) return true;if (graph[nx][ny] == '0' && !vis[nx][ny]) {vis[nx][ny] = true;q.emplace(nx, ny);}}}return false;}void bfs(int A, int B) {queue<pair<int, int> > q;q.emplace(A, B);while (!q.empty()) {auto cur = q.front();q.pop();int x = cur.first, y = cur.second;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 && graph[nx][ny] == '1') {graph[nx][ny] = '0';q.emplace(nx, ny);}}}}int main() {ios::sync_with_stdio(false);int T;cin >> T;while (T--) {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> graph[i][j];}}int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (graph[i][j] == '1') {if (!fill(i, j))graph[i][j] = '0';}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (graph[i][j] == '1') {ans++;bfs(i, j);}}}cout << ans << endl;}return 0;}

G: 子串简写(20分)

问题描述

程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如internationalization简写成i18nKubernetes 简写成K8s, Lanqiao 简写成L5o 等。

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

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

输入格式

第一行包含一个整数 KKK
第二行包含一个字符串 SSS 和两个字符 c1 c_1c1 c2 c_2c2

输出格式

一个整数代表答案。

样例输入

4
abababdb a b

样例输出

6

样例说明

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

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

评测用例规模与约定

对于 30 %30\%30% 的评测用例, 2 ≤ K ≤ ∣ S ∣ ≤ 100002 ≤ K ≤ |S | ≤ 100002KS10000
对于 100 %100\%100% 的评测用例, 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 05 2 ≤ K ≤ |S | ≤ 5 × 10^52KS5×105 SSS 只包含小写字母。 c1 c_1c1 c2 c_2c2 都是小写字母。
∣ S ∣|S |S 代表字符串 SSS 的长度。

思路

感觉也算个数学思维题,感觉跟前缀和有点像。

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 5e5 + 10;string s;int sum[maxn];int main() {int k;cin >> k;cin >> s;int n = s.size();char a, b;cin >> a >> b;for (int i = 1; i <= n; i++) {if (s[i - 1] == b) sum[i] = 1;sum[i] += sum[i - 1];}ll ans = 0;for (int i = 1; i + k - 1 <= n; i++) {if (s[i - 1] == a) ans += sum[n] - sum[i + k - 2];}cout << ans << endl;return 0;}

H: 整数删除(20分)

问题描述

给定一个长度为 NNN 的整数数列: A1, A2, . . . , AN A_1, A_2, …, A_NA1,A2,,AN。你要重复以下操作 KKK 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
输出 KKK次操作后的序列。

输入格式

第一行包含两个整数 NNN KKK
第二行包含 NNN 个整数, A1, A2, A3, . . . , AN A_1, A_2, A_3, …, A_NA1,A2,A3,,AN

输出格式

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

样例输入

5 3
1 4 2 8 7

样例输出

17 7

样例说明

数列变化如下,中括号里的数是当次操作中被选择的数:

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

评测用例规模与约定

对于 20 %20\%20% 的评测用例, 1 ≤ K ≤ N ≤ 1 04 1 ≤K ≤N ≤ 10^41KN104
对于 100 %100\%100% 的评测用例, 1 ≤ K ≤ N ≤ 5 × 1 05 1 ≤K ≤N ≤ 5 ×10^51KN5×105 0 ≤ Ai≤ 1 08 0 ≤ A_i ≤ 10^80Ai108

思路

堆+链表。因为需要频繁删除元素,故考虑使用链表,又因为需要找最小,因此可以使用堆解决。这题最大会爆int,因此必须开long long。

#include #include #include using namespace std;typedef long long ll;const int maxn = 5e5 + 10;ll v[maxn], l[maxn], r[maxn];void del(ll x) {r[l[x]] = r[x], l[r[x]] = l[x];v[l[x]] += v[x], v[r[x]] += v[x];}int main() {int n, k;cin >> n >> k;priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;r[0] = 1, l[n + 1] = n;for (int i = 1; i <= n; i++) {cin >> v[i];l[i] = i - 1;r[i] = i + 1;pq.emplace(v[i], i);}while (k--) {auto p = pq.top();pq.pop();if (p.first != v[p.second]) {pq.emplace(v[p.second], p.second);k++;} else del(p.second);}ll head = r[0];while (head != n + 1) {cout << v[head] << " ";head = r[head];}return 0;}

I: 景区导游(25分)

问题描述

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

小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 KKK 个景点: A1, A2, . . . , AK A_1, A_2, … , A_KA1,A2,,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1K − 1K1 个景点。具体来说,如果小明选择跳过 Ai A_iAi,那么他会按顺序带游客游览 A1, A2, . . . , A i − 1, A i + 1, . . . , AK( 1 ≤ i ≤ K )A_1, A_2,…, A_{i−1}, A_{i+1},…, A_K(1 ≤ i ≤ K)A1,A2,,Ai1,Ai+1,,AK(1iK)

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

输入格式

第一行包含 222 个整数 NNN KKK
以下 N − 1N − 1N1 行,每行包含 333 个整数 u , vu, vu,v ttt,代表景点 uuu vvv 之间有摆渡车线路,花费 ttt 个单位时间。
最后一行包含 KKK 个整数 A1, A2, . . . , AK A_1, A_2,…, A_KA1,A2,,AK 代表原定游览线路。

输出格式

输出 KKK 个整数,其中第 iii 个代表跳过 Ai A_iAi 之后,花费在摆渡车上的时间。

样例输入

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 → 12 → 6 → 5 → 12651
当跳过 222 时,路线是 6 → 5 → 16 → 5 → 1651,其中 6 → 56 → 565 花费时间 3 + 2 + 2 = 73 + 2 + 2 = 73+2+2=7 5 → 15 → 151 花费时间 2 + 1 = 32 + 1 = 32+1=3,总时间花费 101010
当跳过 666 时,路线是 2 → 5 → 12 → 5 → 1251,其中 2 → 52 → 525 花费时间 1 + 1 + 2 = 41 + 1 + 2 = 41+1+2=4 5 → 15 → 151 花费时间 2 + 1 = 32 + 1 = 32+1=3,总时间花费 777
当跳过 555 时,路线是 2 → 6 → 12 → 6 → 1261,其中 2 → 62 → 626 花费时间 1 + 1 + 2 + 3 = 71 + 1 + 2 + 3 = 71+1+2+3=7 6 → 16 → 161 花费时间 3 + 2 + 1 = 63 + 2 + 1 = 63+2+1=6,总时间花费 131313
当跳过 111 时,路线时 2 → 6 → 52 → 6 → 5265,其中 2 → 62 → 626 花费时间 1 + 1 + 2 + 3 = 71 + 1 + 2 + 3 = 71+1+2+3=7 6 → 56 → 565 花费时间 3 + 2 + 2 = 73 + 2 + 2 = 73+2+2=7,总时间花费 141414

评测用例规模与约定

对于 20 %20\%20% 的数据, 2 ≤ K ≤ N ≤ 1 02 2 ≤ K ≤ N ≤ 10^22KN102
对于 40 %40\%40% 的数据, 2 ≤ K ≤ N ≤ 1 04 2 ≤ K ≤ N ≤ 10^42KN104
对于 100 %100\%100% 的数据, 2 ≤ K ≤ N ≤ 1 05, 1 ≤ u , v , Ai≤ N2 ≤ K ≤ N ≤ 10^5,1 ≤ u, v, A_i ≤ N2KN1051u,v,AiN 1 ≤ t ≤ 1 05 1 ≤ t ≤ 10^51t105。保证 Ai A_iAi 两两不同。

思路

一眼LCA,如果用floyd过不去所有数据

#include #include #include using namespace std;typedef long long ll;const int maxn = 1e5 + 10;vector<pair<int, int>> e[maxn];ll fa[maxn], dep[maxn], son[maxn], siz[maxn], top[maxn];ll c[maxn], suf[maxn];ll sum[maxn];void dfs1(ll u, ll f, ll val) {fa[u] = f;dep[u] = dep[f] + 1;siz[u] = 1;sum[u] = val;for (auto x: e[u]) {ll v = x.first;if (v == f) continue;dfs1(v, u, val + x.second);siz[u] += siz[v];if (siz[v] > siz[son[u]]) son[u] = v;}}void dfs2(ll u, ll t) {top[u] = t;if (!son[u]) return;dfs2(son[u], t);for (auto x: e[u]) {ll v = x.first;if (v != son[u] && v != fa[u]) dfs2(v, v);}}ll lca(ll x, ll y) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);x = fa[top[x]];}return dep[x] > dep[y] ? y : x;}ll get(ll x, ll y) {if (x == 0 || y == 0) return 0;return sum[x] + sum[y] - 2 * sum[lca(x, y)];}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, k;cin >> n >> k;for (int i = 1; i < n; i++) {int u, v, z;cin >> u >> v >> z;e[u].emplace_back(v, z);e[v].emplace_back(u, z);}dfs1(1, 1, 0);dfs2(1, 1);for (int i = 1; i <= k; i++) cin >> c[i];for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] + get(c[i], c[i + 1]);ll pre = 0;for (int i = 1; i <= k; i++) {cout << pre + get(c[i - 1], c[i + 1]) + suf[i + 1] << " ";pre += get(c[i - 1], c[i]);}return 0;}

J: 砍树(25分)

问题描述

给定一棵由 nnn 个结点组成的树以及 mmm 个不重复的无序数对 ( a1, b1) , ( a2, b2) , . . . , ( am, bm)(a_1, b_1), (a_2, b_2),… , (a_m, b_m)(a1,b1),(a2,b2),,(am,bm),其中 ai a_iai 互不相同, bi b_ibi 互不相同, ai, bj( 1 ≤ i , j ≤ m )a_i , b_j(1 ≤ i, j ≤ m)ai,bj(1i,jm)

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

输入格式

输入共 n + mn + mn+m 行,第一行为两个正整数 nnn mmm
后面 n − 1n − 1n1 行,每行两个正整数 xi, yi x_i,y_ixiyi 表示第 iii 条边的两个端点。
后面 mmm 行,每行两个正整数 ai, bi a_i,b_iaibi

输出格式

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

样例输入

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

样例输出

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 和6 不连通, 444 555 不连通。
444 编号更大,因此答案为 444

评测用例规模与约定

对于 30 %30\%30% 的评测用例, 1 ≤ N ≤ 1 03 1 ≤ N ≤ 10^31N103
对于 100 %100\%100% 的评测用例, 1 ≤ N ≤ 1 05 1 ≤ N ≤ 10^51N105 1 ≤ m ≤ n2 1 ≤ m ≤ \frac{n}{2}1m2n

思路

感觉这题输出格式写的有问题,只砍断一条边,并且多个答案只输出最大的,那应该输出只有一个数,为啥一行一个整数…没懂。

解法的话应该是树上边差分的板子题。对于每个 ( ai, bi)(a_i, b_i)(ai,bi) 满足 ai和 bi a_i和b_iaibi 不连通,则断开的边一定在 ai→ L C A ( ai, bi)a_i → LCA(a_i,b_i)aiLCA(ai,bi) bi→ L C A ( ai, bi)b_i → LCA(a_i,b_i)biLCA(ai,bi)上。相当于对上面区间贡献度+1,因此贡献度和为 mmm的边为最后的解,如果不存在则无解。

#include #include #include using namespace std;typedef long long ll;const int maxn = 1e5 + 50;vector<int> e[maxn];ll fa[maxn], dep[maxn], son[maxn], siz[maxn], top[maxn];ll diff[maxn];void dfs1(ll u, ll f) {fa[u] = f;dep[u] = dep[f] + 1;siz[u] = 1;for (auto x: e[u]) {ll v = x;if (v == f) continue;dfs1(v, u);siz[u] += siz[v];if (siz[v] > siz[son[u]]) son[u] = v;}}void dfs2(ll u, ll t) {top[u] = t;if (!son[u]) return;dfs2(son[u], t);for (auto x: e[u]) {ll v = x;if (v != son[u] && v != fa[u]) dfs2(v, v);}}ll lca(ll x, ll y) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);x = fa[top[x]];}return dep[x] > dep[y] ? y : x;}void dfs(int x, int fx) {for (auto y: e[x]) {if (y == fx) continue;dfs(y, x);diff[x] += diff[y];}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, m;cin >> n >> m;for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;e[u].emplace_back(v);e[v].emplace_back(u);}dfs1(1, 1);dfs2(1, 1);for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;diff[u]++, diff[v]++, diff[lca(u, v)] -= 2;}dfs(1, 0);ll ans = -1;for (int i = 0; i <= n; i++) if (diff[i] >= m) ans = i - 1;cout << ans << endl;return 0;}