第十四届蓝桥杯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
现在他想要从这个数组中寻找一些满足以下条件的子序列:
- 子序列的长度为8;
- 这个子序列可以按照下标顺序组成一个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=x1x2x3…xn,香农信息熵的定义为 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 \rfloor⌊2075=3⌋, ⌊ 5320= 2 ⌋\lfloor \frac{53}{20}=2 \rfloor⌊2053=2⌋, ⌊ 5920= 2 ⌋\lfloor \frac{59}{20}=2 \rfloor⌊2059=2⌋可以看到符合所有冶炼记录。
当 V = 25V = 25V=25 时,有: ⌊ 7525= 3 ⌋\lfloor \frac{75}{25}=3 \rfloor⌊2575=3⌋, ⌊ 5325= 2 ⌋\lfloor \frac{53}{25}=2 \rfloor⌊2553=2⌋, ⌊ 5925= 2 ⌋\lfloor \frac{59}{25}=2 \rfloor⌊2559=2⌋可以看到符合所有冶炼记录。
且再也找不到比 202020 更小或者比 252525 更大的符合条件的 VVV 值了。
评测用例规模与约定
对于 30 %30\%30% 的评测用例, 1 ≤ N ≤ 1 02 1 ≤ N ≤ 10^21≤N≤102。
对于 60 %60\%60% 的评测用例, 1 ≤ N ≤ 1 03 1 ≤ N ≤ 10^31≤N≤103。
对于 100 %100\%100% 的评测用例, 1 ≤ N ≤ 1 04 1 ≤ N ≤ 10^41≤N≤104, 1 ≤ B ≤ A ≤ 1 09 1 ≤ B ≤ A ≤ 10^91≤B≤A≤109。
思路
感觉是个数学题,算一下即可。
#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 ≤ 2N≤2。
对于 100 %100\%100% 的评测用例, 1 ≤ T ≤ 101 ≤ T ≤ 101≤T≤10, 1 ≤ N ≤ 101 ≤ N ≤ 101≤N≤10, 0 ≤ Ti, Di, Li≤ 1 05 0 ≤ T_i, D_i, L_i ≤ 10^50≤Ti,Di,Li≤105。
思路
本来以为要贪心然后排序去做,手推了几个发现贪心不对,重新看了眼数据范围,发现是个纯暴力的题?
#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}Ai−1 的末位数字 ( 2 ≤ i ≤ K )(2 ≤ i ≤ K)(2≤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, . . . , 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 ≤ 201≤N≤20。
对于 50 %50\%50% 的评测用例, 1 ≤ N ≤ 1 04 1 ≤ N ≤ 10^41≤N≤104。
对于 100 %100\%100% 的评测用例, 1 ≤ N ≤ 1 05 1 ≤ N ≤ 10^51≤N≤105, 1 ≤ Ai≤ 1 09 1 ≤ A_i ≤ 10^91≤Ai≤109。所有 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),…,(xk−1,yk−1),其中 ( 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)(0≤i≤k−1),此时这 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 ≤ 101≤M,N≤10。
对于 100 %100\%100% 的评测用例, 1 ≤ T ≤ 10 , 1 ≤ M , N ≤ 501 ≤T≤ 10, 1 ≤ M,N ≤ 501≤T≤10,1≤M,N≤50。
思路
这个题蛮有意思的,如果不考虑子岛屿的话,基本上是白送分题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简写成i18n,Kubernetes 简写成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 | ≤ 100002≤K≤∣S∣≤10000。
对于 100 %100\%100% 的评测用例, 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 05 2 ≤ K ≤ |S | ≤ 5 × 10^52≤K≤∣S∣≤5×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 − KN−K 个整数,中间用一个空格隔开,代表 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^41≤K≤N≤104。
对于 100 %100\%100% 的评测用例, 1 ≤ K ≤ N ≤ 5 × 1 05 1 ≤K ≤N ≤ 5 ×10^51≤K≤N≤5×105, 0 ≤ Ai≤ 1 08 0 ≤ A_i ≤ 10^80≤Ai≤108。
思路
堆+链表。因为需要频繁删除元素,故考虑使用链表,又因为需要找最小,因此可以使用堆解决。这题最大会爆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 − 1N−1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。
小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 KKK 个景点: A1, A2, . . . , AK A_1, A_2, … , A_KA1,A2,…,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1K − 1K−1 个景点。具体来说,如果小明选择跳过 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,…,Ai−1,Ai+1,…,AK(1≤i≤K)。
请你对任意一个 Ai A_iAi,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?
输入格式
第一行包含 222 个整数 NNN 和 KKK。
以下 N − 1N − 1N−1 行,每行包含 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 → 12→6→5→1。
当跳过 222 时,路线是 6 → 5 → 16 → 5 → 16→5→1,其中 6 → 56 → 56→5 花费时间 3 + 2 + 2 = 73 + 2 + 2 = 73+2+2=7, 5 → 15 → 15→1 花费时间 2 + 1 = 32 + 1 = 32+1=3,总时间花费 101010。
当跳过 666 时,路线是 2 → 5 → 12 → 5 → 12→5→1,其中 2 → 52 → 52→5 花费时间 1 + 1 + 2 = 41 + 1 + 2 = 41+1+2=4, 5 → 15 → 15→1 花费时间 2 + 1 = 32 + 1 = 32+1=3,总时间花费 777。
当跳过 555 时,路线是 2 → 6 → 12 → 6 → 12→6→1,其中 2 → 62 → 62→6 花费时间 1 + 1 + 2 + 3 = 71 + 1 + 2 + 3 = 71+1+2+3=7, 6 → 16 → 16→1 花费时间 3 + 2 + 1 = 63 + 2 + 1 = 63+2+1=6,总时间花费 131313。
当跳过 111 时,路线时 2 → 6 → 52 → 6 → 52→6→5,其中 2 → 62 → 62→6 花费时间 1 + 1 + 2 + 3 = 71 + 1 + 2 + 3 = 71+1+2+3=7, 6 → 56 → 56→5 花费时间 3 + 2 + 2 = 73 + 2 + 2 = 73+2+2=7,总时间花费 141414。
评测用例规模与约定
对于 20 %20\%20% 的数据, 2 ≤ K ≤ N ≤ 1 02 2 ≤ K ≤ N ≤ 10^22≤K≤N≤102。
对于 40 %40\%40% 的数据, 2 ≤ K ≤ N ≤ 1 04 2 ≤ K ≤ N ≤ 10^42≤K≤N≤104。
对于 100 %100\%100% 的数据, 2 ≤ K ≤ N ≤ 1 05, 1 ≤ u , v , Ai≤ N2 ≤ K ≤ N ≤ 10^5,1 ≤ u, v, A_i ≤ N2≤K≤N≤105,1≤u,v,Ai≤N, 1 ≤ t ≤ 1 05 1 ≤ t ≤ 10^51≤t≤105。保证 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(1≤i,j≤m)。
小明想知道是否能够选择一条树上的边砍断,使得对于每个 ( ai, bi)(a_i, b_i)(ai,bi) 满足 ai和 bi a_i和b_iai和bi 不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 111 开始),否则输出 − 1-1−1。
输入格式
输入共 n + mn + mn+m 行,第一行为两个正整数 nnn, mmm。
后面 n − 1n − 1n−1 行,每行两个正整数 xi, yi x_i,y_ixi,yi 表示第 iii 条边的两个端点。
后面 mmm 行,每行两个正整数 ai, bi a_i,b_iai,bi。
输出格式
一行一个整数,表示答案,如有多个答案,输出编号最大的一个。
样例输入
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^31≤N≤103。
对于 100 %100\%100% 的评测用例, 1 ≤ N ≤ 1 05 1 ≤ N ≤ 10^51≤N≤105, 1 ≤ m ≤ n2 1 ≤ m ≤ \frac{n}{2}1≤m≤2n。
思路
感觉这题输出格式写的有问题,只砍断一条边,并且多个答案只输出最大的,那应该输出只有一个数,为啥一行一个整数…没懂。
解法的话应该是树上边差分的板子题。对于每个 ( ai, bi)(a_i, b_i)(ai,bi) 满足 ai和 bi a_i和b_iai和bi 不连通,则断开的边一定在 ai→ L C A ( ai, bi)a_i → LCA(a_i,b_i)ai→LCA(ai,bi)和 bi→ L C A ( ai, bi)b_i → LCA(a_i,b_i)bi→LCA(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;}