您现在的位置是:首页 >技术杂谈 >第十四届蓝桥杯大赛软件赛省赛(C/C++ 大学B组)网站首页技术杂谈
第十四届蓝桥杯大赛软件赛省赛(C/C++ 大学B组)
蓝桥杯 2023年省赛真题
C/C++ 大学B组
要来力
试题 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
m yyyymmdd
yyyymmdd 格式的日期,并且要求这个日期是
2023
2023
2023 年中的某一天的日期,例如
20230902
20230902
20230902,
20231223
20231223
20231223。
y
y
y
y
m yyyy
yyyy 表示年份,
m
m
m mm
mm 表示月份,
d
d
m 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_3cdots 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 13log_2(frac 13)-frac 23log_2(frac 23)-frac 23log_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)=-afrac a{a+b}log_2(frac a{a+b})-bfrac 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.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{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 可能的最小值和最大值,中间用空格分开。
【样例输入】
3
75 3
53 2
59 2
【样例输出】
20 25
【样例说明】
当
V
=
20
V = 20
V=20 时,有:
⌊
75
20
⌋
=
3
,
⌊
53
20
⌋
=
2
,
⌊
59
20
⌋
=
2
lfloorfrac{75}{20}
floor=3,lfloorfrac{53}{20}
floor=2,lfloorfrac{59}{20}
floor=2
⌊2075⌋=3,⌊2053⌋=2,⌊2059⌋=2,可以看到符合所有冶炼记录。
当
V
=
25
V = 25
V=25 时,有:
⌊
75
25
⌋
=
3
,
⌊
53
25
⌋
=
2
,
⌊
59
25
⌋
=
2
lfloorfrac{75}{25}
floor=3,lfloorfrac{53}{25}
floor=2,lfloorfrac{59}{25}
floor=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
leftlfloorcfrac{A_i}{V_i}
ight
floor=B_i
⌊ViAi⌋=Bi的最大值,
V
i
m
i
n
V_i^{min}
Vimin为满足
⌊
A
i
V
i
⌋
=
B
i
leftlfloorcfrac{A_i}{V_i}
ight
floor=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
leftlfloorcfrac{A_i}{V_i}
ight
floor>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
⌋
leftlfloorcfrac{A}{B}
ight
floor
⌊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
leftlceilcfrac{A}{B}
ight
ceil = 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
leftlfloorcfrac{A}{V}
ight
floor =leftlfloorcfrac{B(V - 1)+A'}{V}
ight
floor<B
⌊VA⌋=⌊VB(V−1)+A′⌋<B,故
V
m
a
x
V^{max}
Vmax最大。
考虑到
⌊
A
V
⌋
leftlfloorcfrac{A}{V}
ight
floor
⌊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.0mathrm s 2.0s 内存限制: 256.0 M B 256.0mathrm{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 m YES YES 或者 N O m NO NO,代表是否可以全部安全降落。
【样例输入】
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
【样例输出】
YES
NO
【样例说明】
对于第一组数据,可以安排第
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
" : "NO
");
}
int main() {
scanf("%d", &T);
while (T--) run();
}
试题 E: 接龙数列
时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{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。
【输出格式】
一个整数代表答案。
【样例输入】
5
11 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.0mathrm s 2.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分: 15 15 15 分
【问题描述】
小蓝得到了一副大小为
M
×
N
M × N
M×N 的格子地图,可以将其视作一个只包含字符
‘
0
’
‘0’
‘0’(代表海水)和
‘
1
’
‘1’
‘1’(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上
/
/
/下
/
/
/左
/
/
/右四个方向上相邻的
‘
1
’
‘1’
‘1’ 相连接而形成。
在岛屿
A
m 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
m B
B 所占据的格子全部位于这个 “环” 内部,此时我们将岛屿
B
m B
B 视作是岛屿
A
m A
A 的子岛屿。若
B
m B
B 是
A
m A
A 的子岛屿,
C
m C
C 又是
B
m B
B 的子岛屿,那
C
m C
C 也是
A
m 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’。
【输出格式】
对于每组数据,输出一行,包含一个整数表示答案。
【样例输入】
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
【样例输出】
1
3
【样例说明】
对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:
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
", ans);
}
int main() {
scanf("%d", &T);
while (T--) run();
}
试题 G: 子串简写
时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分: 20 20 20 分
【问题描述】
程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如
i
n
t
e
r
n
a
t
i
o
n
m internation
internation-
a
l
i
z
a
t
i
o
n
m alization
alization 简写成
i
18
n
m i18n
i18n,
K
u
b
e
r
n
e
t
e
s
m Kubernetes
Kubernetes (注意连字符不是字符串的一部分)简写成
K
8
s
m K8s
K8s,
L
a
n
q
i
a
o
m Lanqiao
Lanqiao 简写成
L
5
o
m 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。
【输出格式】
一个整数代表答案。
【样例输入】
4
abababdb a b
【样例输出】
6
【样例说明】
符合条件的子串如下所示,中括号内是该子串:
[
a
b
a
b
]
a
b
d
b
m [abab]abdb
[abab]abdb
[
a
b
a
b
a
b
]
d
b
m [ababab]db
[ababab]db
[
a
b
a
b
a
b
d
b
]
m [abababdb]
[abababdb]
a
b
[
a
b
a
b
]
d
b
m ab[abab]db
ab[abab]db
a
b
[
a
b
a
b
d
b
]
m ab[ababdb]
ab[ababdb]
a
b
a
b
[
a
b
d
b
]
m 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
%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.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{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 3
1 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。
试题 I: 景区导游
时间限制: 5.0 s 5.0mathrm s 5.0s 内存限制: 256.0 M B 256.0mathrm{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 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
→
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 两两不同。
试题 J: 魔法阵
时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{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 2
1 2
2 3
4 3
2 5
6 5
3 6
4 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。