第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学B组）
时间：2024-03-28 12:56:03 来源：网络cs 作者：言安琪 栏目：卖家故事 阅读：
蓝桥杯 2023年省赛真题
C/C++ 大学B组
试题 A: 日期统计试题 B: 01 串的熵试题 C: 冶炼金属试题 D: 飞机降落试题 E: 接龙数列试题 F: 岛屿个数试题 G: 子串简写试题 H: 整数删除试题 I: 景区导游试题 J: 砍树
要来力
试题 A: 日期统计
本题总分： 5 5 5 分
【问题描述】
小蓝现在有一个长度为 100 100 100 的数组，数组中的每个元素的值都在 0 0 0 到 9 9 9 的范围之内。数组中的元素从左至右如下所示：
5 5 5 6 6 6 8 8 8 6 6 6 9 9 9 1 1 1 6 6 6 1 1 1 2 2 2 4 4 4 9 9 9 1 1 1 9 9 9 8 8 8 2 2 2 3 3 3 6 6 6 4 4 4 7 7 7 7 7 7 5 5 5 9 9 9 5 5 5 0 0 0 3 3 3 8 8 8 7 7 7 5 5 5 8 8 8 1 1 1 5 5 5 8 8 8 6 6 6 1 1 1 8 8 8 3 3 3 0 0 0 3 3 3 7 7 7 9 9 9 2 2 2 7 7 7 0 0 0 5 5 5 8 8 8 8 8 8 5 5 5 7 7 7 0 0 0 9 9 9 9 9 9 1 1 1 9 9 9 4 4 4 4 4 4 6 6 6 8 8 8 6 6 6 3 3 3 3 3 3 8 8 8 5 5 5 1 1 1 6 6 6 3 3 3 4 4 4 6 6 6 7 7 7 0 0 0 7 7 7 8 8 8 2 2 2 7 7 7 6 6 6 8 8 8 9 9 9 5 5 5 6 6 6 5 5 5 6 6 6 1 1 1 4 4 4 0 0 0 1 1 1 0 0 0 0 0 0 9 9 9 4 4 4 8 8 8 0 0 0 9 9 9 1 1 1 2 2 2 8 8 8 5 5 5 0 0 0 2 2 2 5 5 5 3 3 3 3 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列：
1. 子序列的长度为 8 8 8；
2. 这个子序列可以按照下标顺序组成一个 y y y y m m d d \rm yyyymmdd yyyymmdd 格式的日期，并且要求这个日期是 2023 2023 2023 年中的某一天的日期，例如 20230902 20230902 20230902， 20231223 20231223 20231223。 y y y y \rm yyyy yyyy 表示年份， m m \rm mm mm 表示月份， d d \rm dd dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 2023 2023 年的日期。对于相同的日期你只需要统计一次即可。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
235
枚举长度为 8 8 8的子序列复杂度直接炸裂，不过考虑到日期前缀为 2023 2023 2023且唯一，因为找到 2023 2023 2023第一次出现的位置截断后枚举长度为 4 4 4的子序列与 2023 2023 2023年的合法日期取交集即可。
#include <bits/stdc++.h>char *A = "5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";char *prefix = "2023";int n = 100, m = 0, ds[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };std::set<int> subs[4], target;std::vector<int> ans;int main() { for (int k = 0; k < 4 && m < n; ++m) if (prefix[k] == A[m]) ++k; for (; m < n; ++m) { for (int i = 2; i >= 0; --i) for (int sb : subs[i]) subs[i + 1].insert(sb * 10 + A[m] - '0'); subs[0].insert(A[m] - '0'); } for (int m = 1; m <= 12; ++m) for (int d = 1; d <= ds[m]; ++d) target.insert(m * 100 + d); std::set_intersection(target.begin(), target.end(), subs[3].begin(), subs[3].end(), std::back_inserter(ans)); printf("%d", ans.size());}试题 B: 01 串的熵
本题总分： 5 5 5 分
【问题描述】
对于一个长度为 n n n 的 01 01 01 串 S = x 1 x 2 x 3 ⋯ x n S = x_1x_2x_3\cdots x_n S=x1x2x3⋯xn，香农信息熵的定义为 H ( S ) = − ∑ i n p ( x i ) log 2 ( p ( x i ) ) H(S)=-\sum_{i}^{n}p(x_i)\log_2(p(x_i)) H(S)=−∑inp(xi)log2(p(xi))，其中 p ( 0 ) , p ( 1 ) p(0), p(1) p(0),p(1) 表示在这个 01 01 01 串中 0 0 0 和 1 1 1 出现的占比。比如，对于 S = 100 S = 100 S=100 来说，信息熵 H ( S ) = − 1 3 log 2 ( 1 3 ) − 2 3 log 2 ( 2 3 ) − 2 3 log 2 ( 2 3 ) = 1.3083 H(S)=-\frac 13\log_2(\frac 13)-\frac 23\log_2(\frac 23)-\frac 23\log_2(\frac 23)=1.3083 H(S)=−31log2(31)−32log2(32)−32log2(32)=1.3083。对于一个长度为 23333333 23333333 23333333 的 01 01 01 串，如果其信息熵为 11625907.5798 11625907.5798 11625907.5798，且 0 0 0 出现次数比 1 1 1 少，那么这个 01 01 01 串中 0 0 0 出现了多少次？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
11027421
对于一个长度为 a + b a + b a+b且 0 0 0出现 a a a次的 01 01 01串 S S S， H ( S ) = − a a a + b log 2 ( a a + b ) − b b a + b log 2 ( b a + b ) H(S)=-a\frac a{a+b}\log_2(\frac a{a+b})-b\frac b{a+b}\log_2(\frac b{a+b}) H(S)=−aa+balog2(a+ba)−ba+bblog2(a+bb)，嗯算就完了。
#include <stdio.h>#include <math.h>int n = 23333333;double target = 11625907.5798;int main() { for (double i = 0, j = n; i <= n; i += 1, j -= 1) if (abs(i * (- i / n * log2(i / n)) + j * (- j / n * log2(j / n)) - target) < 1e-4) { printf("%.0lf", i); return 0; }}试题 C: 冶炼金属
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 10 10 10 分
【问题描述】
小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个称作转换率的属性 V V V， V V V 是一个正整数，这意味着消耗 V V V 个普通金属 O O O 恰好可以冶炼出一个特殊金属 X X X，当普通金属 O O O 的数目不足 V V V 时，无法继续冶炼。
现在给出了 N N N 条冶炼记录，每条记录中包含两个整数 A A A 和 B B B，这表示本次投入了 A A A 个普通金属 O O O，最终冶炼出了 B B B 个特殊金属 X X X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O O O 不会累加到下一次的冶炼当中。
根据这 N N N 条冶炼记录，请你推测出转换率 V V V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
【输入格式】
第一行一个整数 N N N，表示冶炼记录的数目。
接下来输入 N N N 行，每行两个整数 A 、 B A、B A、B，含义如题目所述。
【输出格式】
输出两个整数，分别表示 V V V 可能的最小值和最大值，中间用空格分开。
【样例输入】
375 353 259 2【样例输出】
20 25【样例说明】
当 V = 20 V = 20 V=20 时，有： ⌊ 75 20 ⌋ = 3 , ⌊ 53 20 ⌋ = 2 , ⌊ 59 20 ⌋ = 2 \lfloor\frac{75}{20}\rfloor=3,\lfloor\frac{53}{20}\rfloor=2,\lfloor\frac{59}{20}\rfloor=2 ⌊2075⌋=3,⌊2053⌋=2,⌊2059⌋=2，可以看到符合所有冶炼记录。
当 V = 25 V = 25 V=25 时，有： ⌊ 75 25 ⌋ = 3 , ⌊ 53 25 ⌋ = 2 , ⌊ 59 25 ⌋ = 2 \lfloor\frac{75}{25}\rfloor=3,\lfloor\frac{53}{25}\rfloor=2,\lfloor\frac{59}{25}\rfloor=2 ⌊2575⌋=3,⌊2553⌋=2,⌊2559⌋=2，可以看到符合所有冶炼记录。
且再也找不到比 20 20 20 更小或者比 25 25 25 更大的符合条件的 V V V 值了。
【评测用例规模与约定】
对于 30 % 30\% 30% 的评测用例， 1 ≤ N ≤ 1 0 2 1 ≤ N ≤ 10^2 1≤N≤102。
对于 60 % 60\% 60% 的评测用例， 1 ≤ N ≤ 1 0 3 1 ≤ N ≤ 10^3 1≤N≤103。
对于 100 % 100\% 100% 的评测用例， 1 ≤ N ≤ 1 0 4 ， 1 ≤ B ≤ A ≤ 1 0 9 1 ≤ N ≤ 10^4，1 ≤ B ≤ A ≤ 10^9 1≤N≤104，1≤B≤A≤109。
记 V i m a x V_i^{max} Vimax为满足 ⌊ A i V i ⌋ = B i \left\lfloor\cfrac{A_i}{V_i}\right\rfloor=B_i ⌊ViAi⌋=Bi的最大值， V i m i n V_i^{min} Vimin为满足 ⌊ A i V i ⌋ = B i \left\lfloor\cfrac{A_i}{V_i}\right\rfloor=B_i ⌊ViAi⌋=Bi的最小值，则最大的 V V V取 min { V i m a x } \min\{V_i^{max}\} min{Vimax}，因为取最大值可能会使 ⌊ A i V i ⌋ > B i \left\lfloor\cfrac{A_i}{V_i}\right\rfloor>B_i ⌊ViAi⌋>Bi成立，同理最小的 V V V取 max { V i m a x } \max\{V_i^{max}\} max{Vimax}。
对于 A A A、 B B B我们取 ⌊ A B ⌋ \left\lfloor\cfrac{A}{B}\right\rfloor ⌊BA⌋做 V m a x V^{max} Vmax，当 A = V B A=VB A=VB时 V V V的取值唯一，显然成立，否则 ⌈ A B ⌉ = V m a x + 1 \left\lceil\cfrac{A}{B}\right\rceil = V^{max} + 1 ⌈BA⌉=Vmax+1，当取 V m a x + 1 V^{max} + 1 Vmax+1做 V V V时带入 ⌊ A V ⌋ = ⌊ B ( V − 1 ) + A ′ V ⌋ < B \left\lfloor\cfrac{A}{V}\right\rfloor =\left\lfloor\cfrac{B(V - 1)+A'}{V}\right\rfloor<B ⌊VA⌋=⌊VB(V−1)+A′⌋<B，故 V m a x V^{max} Vmax最大。
考虑到 ⌊ A V ⌋ \left\lfloor\cfrac{A}{V}\right\rfloor ⌊VA⌋为单调减函数，我们取 A , B + 1 A,B+1 A,B+1的最大值加 1 1 1,显然最小。
#include <stdio.h>#include <algorithm>int n, a, b, max = 0x3f3f3f3f, min = 0;int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d %d", &a, &b); max = std::min(max, a / b); min = std::max(min, a / (b + 1) + 1); } printf("%d %d", min, max);}试题 D: 飞机降落
时间限制: 2.0 s 2.0\mathrm s 2.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 10 10 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 \rm YES YES 或者 N O \rm NO NO，代表是否可以全部安全降落。
【样例输入】
230 100 1010 10 100 2 2030 10 2010 10 2020 10 20【样例输出】
YESNO【样例说明】
对于第一组数据，可以安排第 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 ≤ 2 N≤2。
对于 100 % 100\% 100% 的数据， 1 ≤ T ≤ 10 ， 1 ≤ N ≤ 10 ， 0 ≤ T i , D i , L i ≤ 1 0 5 1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ T_i, D_i, L_i ≤ 10^5 1≤T≤10，1≤N≤10，0≤Ti,Di,Li≤105。
感觉暴搜会被卡常，所以选用记忆化搜索，用二进制表示第 i i i位为 1 1 1表示第 i i i量飞机降落，记 d p s t a t u s dp_{status} dpstatus为 s t a t u s status status表示的降落状态的最早完成时间， − 1 -1 −1表示不可达， inf \inf inf表示未访问，时间复杂度为 O ( ∑ i = 1 T ( N i C N N + ( N i − 1 ) C N N − 1 + ⋯ + C N 1 ) ) = O ( T N 2 N − 1 ) O(\sum_{i=1}^T(N_iC_N^N+(N_i-1)C_N^{N-1}+\cdots+C_{N}^1)) =O(TN2^{N-1}) O(∑i=1T(NiCNN+(Ni−1)CNN−1+⋯+CN1))=O(TN2N−1)。
#include <stdio.h>#include <algorithm>int T, n, t[1 << 10], d[1 << 10], l[1 << 10], dp[1 << 10], inf = 0x3f3f3f3f;int dfs(int status, int depth) { if (dp[status] != inf) return dp[status]; if (depth == n) return dp[status] = t[status] + l[status]; for (int i = status; i; ) { int p = i & -i; int q = dfs(status - p, depth + 1); if (q != -1 && q <= t[p] + d[p]) dp[status] = std::min(dp[status], std::max(t[p], q) + l[p]); i -= p; } if (dp[status] == inf) dp[status] = -1; return dp[status];}void run() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d %d %d", &t[1 << i], &d[1 << i], &l[1 << i]); int full = (1 << n) - 1; for (int i = 0; i <= full; ++i) dp[i] = inf; dfs(full, 1); printf(dp[full] >= 0 ? "YES\n" : "NO\n");}int main() { scanf("%d", &T); while (T--) run();}试题 E: 接龙数列
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 15 15 15 分
【问题描述】
对于一个长度为 K K K 的整数数列： A 1 , A 2 , ⋯ , A K A_1, A_2, \cdots, A_K A1,A2,⋯,AK，我们称之为接龙数列当且仅当 A i A_i Ai 的首位数字恰好等于 A i − 1 A_{i−1} Ai−1 的末位数字 ( 2 ≤ i ≤ K ) (2 ≤ i ≤ 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, \cdots, A_N A1,A2,⋯,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
【输入格式】
第一行包含一个整数 N N N。
第二行包含 N N N 个整数 A 1 , A 2 , ⋯ , A N A_1, A_2, \cdots, A_N A1,A2,⋯,AN。
【输出格式】
一个整数代表答案。
【样例输入】
511 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 ≤ N ≤ 20 1≤N≤20。
对于 50 % 50\% 50% 的数据， 1 ≤ N ≤ 10000 1 ≤ N ≤ 10000 1≤N≤10000。
对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 1 0 5 ， 1 ≤ A i ≤ 1 0 9 1 ≤ N ≤ 10^5，1 ≤ A_i ≤ 10^9 1≤N≤105，1≤Ai≤109。所有 A i A_i Ai 保证不包含前导 0 0 0。
令 d p i , d dp_{i,d} dpi,d为 [ 1 , i ] [1,i] [1,i]范围内构成的最长接龙序列以 d d d结尾的长度，则有状态转移方程 d p i , d = max ( d p i − 1 , d , d p i − 1 , b i ) dp_{i,d}=\max(dp_{i-1,d}, dp_{i-1,b_i}) dpi,d=max(dpi−1,d,dpi−1,bi)，其中 b i b_i bi为 A i A_i Ai的首位数字，然后滚动数组优化下，根据序理论，答案为 N − max { d p d } N-\max\{dp_d\} N−max{dpd}。
#include <stdio.h>#include <string.h>#include <algorithm>int n, ans, dp['9' + 1];char a[18];int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%s", &a); int last = a[strlen(a) - 1]; dp[last] = std::max(dp[last], dp[a[0]] + 1); } for (int i = '1'; i <= '9'; ++i) ans = std::max(ans, dp[i]); printf("%d", n - ans);}试题 F: 岛屿个数
时间限制: 2.0 s 2.0\mathrm s 2.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 15 15 15 分
【问题描述】
小蓝得到了一副大小为 M × N M × N M×N 的格子地图，可以将其视作一个只包含字符 ‘ 0 ’ ‘0’ ‘0’（代表海水）和 ‘ 1 ’ ‘1’ ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上 / / /下 / / /左 / / /右四个方向上相邻的 ‘ 1 ’ ‘1’ ‘1’ 相连接而形成。
在岛屿 A \rm A A 所占据的格子中，如果可以从中选出 k k k 个不同的格子，使得他们的坐标能够组成一个这样的排列： ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 ) (x0, y0),(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) 是由 ( x i , y i ) (x_i, y_i) (xi,yi) 通过上 / / /下 / / /左 / / /右移动一次得来的 ( 0 ≤ i ≤ k − 1 ) (0 ≤ i ≤ k − 1) (0≤i≤k−1)，此时这 k k k 个格子就构成了一个 “环”。如果另一个岛屿 B \rm B B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B \rm B B 视作是岛屿 A \rm A A 的子岛屿。若 B \rm B B 是 A \rm A A 的子岛屿， C \rm C C 又是 B \rm B B 的子岛屿，那 C \rm C C 也是 A \rm A A 的子岛屿。
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。
【输入格式】
第一行一个整数 T T T，表示有 T T T 组测试数据。
接下来输入 T T T 组数据。对于每组数据，第一行包含两个用空格分隔的整数 M 、 N M、N M、N 表示地图大小；接下来输入 M M M 行，每行包含 N N N 个字符，字符只可能是 ‘ 0 ’ ‘0’ ‘0’ 或 ‘ 1 ’ ‘1’ ‘1’。
【输出格式】
对于每组数据，输出一行，包含一个整数表示答案。
【样例输入】
25 501111110011010110001111115 6111111100001010101100001111111【样例输出】
13【样例说明】
对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：
01111 01111 01111
11001 11001 11001
10201 10201 10201
10001 10001 10001
11111 11111 11111
岛屿 2 2 2 在岛屿 1 1 1 的 “环” 内部，所以岛屿 2 2 2 是岛屿 1 1 1 的子岛屿，答案为 1 1 1。
对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：
111111 111111 111111
100001 100001 100001
020301 020301 020301
100001 100001 100001
111111 111111 111111
注意岛屿 3 3 3 并不是岛屿 1 1 1 或者岛屿 2 2 2 的子岛屿，因为岛屿 1 1 1 和岛屿 2 2 2 中均没有“环”。
【评测用例规模与约定】
对于 30 % 30\% 30% 的评测用例， 1 ≤ M , N ≤ 10 1 ≤ M, N ≤ 10 1≤M,N≤10。
对于 100 % 100\% 100% 的评测用例， 1 ≤ T ≤ 10 ， 1 ≤ M , N ≤ 50 1 ≤ T ≤ 10，1 ≤ M, N ≤ 50 1≤T≤10，1≤M,N≤50。
bfs，先将公海标记出来，然后碰到内海直接当成陆地，注意海洋有八个方向可以扩散。
#include <stdio.h>char map[66][66], inf = 0x7f;int T, n, m, offset[]{ -1, 0, 0, 1, 1, 0, 0, -1, -1, -1, -1, 1, 1, 1, 1, -1 };int h, t, X[2333], Y[2333];void bfs(int x, int y, int a, int r) { X[0] = x, Y[0] = y, map[x][y] = inf; for (h = 0, t = 1; h != t;) { x = X[h], y = Y[h], ++h; for (int i = 0; i < r;) { int k = x + offset[i++], g = y + offset[i++]; if (k < 0 || k >= n || y < 0 || y >= m) continue; if (map[k][g] <= a) { X[t] = k, Y[t] = g, ++t; map[k][g] = inf; } } }}void run() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%s", map[i]); for (int i = 0; i < n; ++i) { if (map[i][0] == '0') bfs(i, 0, '0', 16); if (map[i][m - 1] == '0') bfs(i, m - 1, '0', 16); } for (int i = 0; i < m; ++i) { if (map[0][i] == '0') bfs(0, i, '0', 16); if (map[n - 1][i] == '0') bfs(n - 1, i, '0', 16); } int ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (map[i][j] == '1'){ bfs(i, j, '1', 8); ++ans; } printf("%d\n", ans);}int main() { scanf("%d", &T); while (T--) run();}试题 G: 子串简写
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 20 20 20 分
【问题描述】
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 i n t e r n a t i o n \rm internation internation- a l i z a t i o n \rm alization alization 简写成 i 18 n \rm i18n i18n， K u b e r n e t e s \rm Kubernetes Kubernetes （注意连字符不是字符串的一部分）简写成 K 8 s \rm K8s K8s， L a n q i a o \rm Lanqiao Lanqiao 简写成 L 5 o \rm L5o 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。
【输出格式】
一个整数代表答案。
【样例输入】
4abababdb a b【样例输出】
6【样例说明】
符合条件的子串如下所示，中括号内是该子串：
[ a b a b ] a b d b \rm [abab]abdb [abab]abdb
[ a b a b a b ] d b \rm [ababab]db [ababab]db
[ a b a b a b d b ] \rm [abababdb] [abababdb]
a b [ a b a b ] d b \rm ab[abab]db ab[abab]db
a b [ a b a b d b ] \rm ab[ababdb] ab[ababdb]
a b a b [ a b d b ] \rm abab[abdb] abab[abdb]
【评测用例规模与约定】
对于 20 % 20\% 20% 的数据， 2 ≤ K ≤ ∣ S ∣ ≤ 10000 2 ≤ K ≤ |S | ≤ 10000 2≤K≤∣S∣≤10000。
对于 100 % 100\% 100% 的数据， 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 0 5 2 ≤ K ≤ |S | ≤ 5 × 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 的长度。
几乎裸一维dp，不是这题凭什么值20分啊。
#include <stdio.h>char s[500023], &c1 = s[500010], &c2 = s[500020];int i, k, dp[500010];long long ans = 0;int main() { scanf("%d\n%s %s %s", &k, s + 1, &c1, &c2); for (i = 1; s[i]; ++i) { if (s[i] == c1) dp[i] = 1; dp[i] += dp[i - 1]; } while (--i >= k) if (s[i] == c2) ans += dp[i - k + 1]; printf("%lld", ans);}试题 H: 整数删除
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 20 20 20 分
【问题描述】
给定一个长度为 N N N 的整数数列： A 1 , A 2 , ⋯ , A N A_1, A_2, \cdots, 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, \cdots, A_N A1,A2,A3,⋯,AN。
【输出格式】
输出 N − K N − K N−K 个整数，中间用一个空格隔开，代表 K K K 次操作后的序列。
【样例输入】
5 31 4 2 8 7【样例输出】
17 7【样例说明】
数列变化如下，中括号里的数是当次操作中被选择的数：
[ 1 ] 4 2 8 7 [1]\ 4\ 2\ 8\ 7 [1] 4 2 8 7
5 [ 2 ] 8 7 5\ [2]\ 8\ 7 5 [2] 8 7
[ 7 ] 10 7 [7]\ 10\ 7 [7] 10 7
17 7 17\ 7 17 7
【评测用例规模与约定】
对于 20 % 20\% 20% 的数据， 1 ≤ K < N ≤ 10000 1 ≤ K < N ≤ 10000 1≤K<N≤10000。
对于 100 % 100\% 100% 的数据， 1 ≤ K < N ≤ 5 × 1 0 5 ， 0 ≤ A i ≤ 1 0 8 1 ≤ K < N ≤ 5 × 10^5，0 ≤ A_i ≤ 10^8 1≤K<N≤5×105，0≤Ai≤108。
? 1 s 1s 1s， N N N还开到 5 e 5 5e5 5e5，出题人没什么大病吧
关键 A i A_i Ai对答案的贡献最差呈指数增加，实测答案范围可达 3.76 e 16 3.76e16 3.76e16，这意味着我们无法用一个 64 64 64位整形同时表示 A i A_i Ai和 i i i，以减少比较所使用的时间，而且用优先队列模拟还要考虑数据过期问题，手搓二叉堆看看吧，什么*题。
当然可能存在更优的解法，但题目的表述已经很“自然”了，考虑贪心又涉及到“松弛”复杂度更差，反正我想不出来。
不过现代处理器寄存器都挺大了，不用在值传递，值分开传递，引用传递之间择优，基本上256位以内无脑值传递，别写的编译器看不懂就行。
#include <stdio.h>#include <algorithm>const int N = 5e5 + 6;std::pair<long long, int> heap[N << 1];int n, k, l[N], r[N];long long a[N];inline void sink(int x) { for (int k = x; (k = k << 1) <= n; x = k) { if (k < n && heap[k + 1] < heap[k]) ++k; if (heap[x] < heap[k]) break; std::swap(heap[x], heap[k]); }}int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); heap[i] = {a[i], i}; l[i] = i - 1; r[i] = i + 1; } r[0] = 1; r[n] = 0; for (int i = n / 2; i; --i) sink(i); for (; k--; sink(1)) { std::pair<long long, int> top = heap[1]; if (a[top.second] != top.first) { heap[1].first = a[top.second], ++k; } else { heap[1] = heap[n--]; l[r[top.second]] = l[top.second]; r[l[top.second]] = r[top.second]; a[l[top.second]] += top.first; a[r[top.second]] += top.first; } } for (int i = r[0]; i; i = r[i]) printf("%lld ", a[i]);}对不起，常数小就是可以为所欲为的.jpg
试题 I: 景区导游
时间限制: 5.0 s 5.0\mathrm s 5.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 25 25 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, \cdots, 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, \cdots, A_{i−1}, A_{i+1}, \cdots, A_K, (1 ≤ i ≤ 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, \cdots, A_K A1,A2,⋯,AK 代表原定游览线路。
【输出格式】
输出 K K K 个整数，其中第 i i i 个代表跳过 A i A_i Ai 之后，花费在摆渡车上的时间。
【样例输入】
6 41 2 11 3 13 4 23 5 24 6 32 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 ≤ K ≤ N ≤ 10^2 2≤K≤N≤102。
对于 40 % 40\% 40% 的数据， 2 ≤ K ≤ N ≤ 1 0 4 2 ≤ K ≤ N ≤ 10^4 2≤K≤N≤104。
对于 100 % 100\% 100% 的数据， 2 ≤ K ≤ N ≤ 1 0 5 ， 1 ≤ u , v , A i ≤ N ， 1 ≤ t ≤ 1 0 5 2 ≤ K ≤ N ≤ 10^5，1 ≤ u, v, A_i ≤ N，1 ≤ t ≤ 10^5 2≤K≤N≤105，1≤u,v,Ai≤N，1≤t≤105。保证 A i A_i Ai 两两不同。
lca模板题，记 d i s t i , j dist_{i,j} disti,j为 i → j i→ j i→j花费的时间，则第 i i i个输出为 ∑ j = 1 k − 1 d i s t A j , A j + 1 − d i s t A j − 1 , A j − d i s t A j , A j + 1 + d i s t A j − 1 , A j + 1 \sum_{j=1}^{k-1}dist_{A_j,A_{j+1}}-dist_{A_{j-1},A_{j}}-dist_{A_j,A_{j+1}}+dist_{A_{j-1},A_{j+1}} ∑j=1k−1distAj,Aj+1−distAj−1,Aj−distAj,Aj+1+distAj−1,Aj+1，将路线上序号差不超过 2 2 2的路径用tarjan算出，然后代入计算就行。
#include <stdio.h>const int N = 1e5 + 6;int n, k, u, v, w, cur, a[N], f[N], q[N], head[N], next[6 * N], ver[6 * N], wei[6 * N];long long l, r[N], t[N], ans[N << 1];inline void link(int *g, int u, int v, int w) { next[++cur] = g[u], g[u] = cur, ver[cur] = v, wei[cur] = w; }int find(int x) { return x == f[x] ? x : (f[x] = find(f[x])); }void tarjan(int u) { f[u] = u; for (int i = head[u]; i; i = next[i]) if (!f[ver[i]]) { t[ver[i]] = t[u] + wei[i]; tarjan(ver[i]); f[ver[i]] = u; } for (int i = q[u]; i; i = next[i]) if (f[ver[i]]) ans[wei[i]] = t[u] + t[ver[i]] - 2 * t[find(ver[i])];}int main() { scanf("%d %d", &n, &k); for (int i = 1; i < n; ++i) { scanf("%d %d %d", &u, &v, &w); link(head, u, v, w); link(head, v, u, w); } for (int i = 1; i <= k; ++i) { scanf("%d", &a[i]); if (i > 1) { link(q, a[i], a[i - 1], i - 1); link(q, a[i - 1], a[i], i - 1); } if (i > 2) { link(q, a[i], a[i - 2], N + i - 2); link(q, a[i - 2], a[i], N + i - 2); } } int rand = (23333333 % n) + 1; tarjan(rand); for (int i = k - 1; i; --i) r[i] = r[i + 1] + ans[i]; for (int i = 1; i <= k; ++i) { printf("%lld ", l + r[i + 1] + ans[N + i - 1]); l += ans[i - 1]; }}试题 J: 砍树
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 25 25 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), \cdots, (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 ≤ i, j ≤ 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 21 22 34 32 56 53 64 5【样例输出】
4【样例说明】
断开第 2 2 2 条边后形成两个连通块： { 3 , 4 } ， { 1 , 2 , 5 , 6 } \{3, 4\}，\{1, 2, 5, 6\} {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 } \{1, 2, 3, 4\}，\{5, 6\} {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 ≤ 1000 1<n≤1000。
对于 100 % 100\% 100% 的数据，保证 1 < n ≤ 1 0 5 ， 1 ≤ m ≤ n 2 1 < n ≤ 10^5，1 ≤ m ≤ \frac n2 1<n≤105，1≤m≤2n。
刚开始没看出来是裸差分，想的是从入度为 0 0 0的节点遍历，经过哪条边就模拟拿掉，然后树被拆成两颗，也就是节点被划分为两个集合，所以这也是不断将某个节点加入集合的过程，对于加入集合的节点我们将它关联的二元组设一个权值并加一，然后统计总权值，总权值到 m m m并且没有二元权值大于 1 1 1则当前边是一个备选答案，然后迭代出最大。
这种做法的好处是题目无解可以提前跳出，复杂度下界比较优，但既然现在想通了就按树上差分去写，人就是突出一个懒。
#include <stdio.h>const int N = 1e5 + 6;int n, m, u, v, cur = 1, val[N], f[N], q[N], head[N], next[3 * N], ver[3 * N];inline void link(int *g, int u, int v) { next[++cur] = g[u], g[u] = cur, ver[cur] = v; }int find(int x) { return x == f[x] ? x : (f[x] = find(f[x])); }void tarjan(int u) { f[u] = u; for (int i = head[u]; i; i = next[i]) if (!f[ver[i]]) { tarjan(ver[i]); f[ver[i]] = u; } for (int i = q[u]; i; i = next[i]) if (f[ver[i]]) { val[u]++; val[ver[i]]++; val[find(ver[i])] -= 2; ver[i] = ver[i ^ 1] = 0; }}void dfs(int u, int r) { f[u] = r; for (int i = head[u]; i; i = next[i]) if (ver[i] != r) { f[ver[i]] = u; dfs(ver[i], u); val[u] += val[ver[i]]; }}int main() { scanf("%d %d", &n, &m); for (int i = 1; i < n; ++i) { scanf("%d %d", &u, &v); link(head, u, v); link(head, v, u); } for (int i = 1; i <= m; ++i) { scanf("%d %d", &u, &v); link(q, u, v); link(q, v, u); } int rand = (23333333 % n) + 1; tarjan(rand); dfs(rand, rand); cur = -2; for (int i = 1; i <= n; ++i) for (int x = head[i]; x; x = next[x]) if (f[i] == ver[x]){ if (val[i] == m && cur < x) cur = x; } else { if (val[ver[x]] == m && cur < x) cur = x; } printf("%d", cur >> 1);}本文链接：https://www.kjpai.cn/gushi/2024-03-28/149997.html，文章来源：网络cs，作者：言安琪，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！