蓝桥杯 2024年省赛真题
Java 大学B组
- 试题 A: 报数游戏
- 试题 B: 类斐波那契循环数
- 试题 C: 分布式队列
- 试题 D: 食堂
- 试题 E: 最优分组
在找工作，随便写写，安定下来再把去年国赛题解补上
试题 A: 报数游戏
本题总分： 5 5 5 分
【问题描述】
小蓝和朋友们在玩一个报数游戏。由于今年是
2024
2024
2024 年，他们决定要
从小到大轮流报出是
20
20
20 或
24
24
24 倍数的正整数。前
10
10
10 个被报出的数是
：
：
：
20
,
24
,
40
,
48
,
60
,
72
,
80
,
96
,
100
,
120
20, 24, 40, 48, 60, 72, 80, 96, 100, 120
20,24,40,48,60,72,80,96,100,120。请问第
202420242024
202420242024
202420242024 个被报出的数是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
2429042904288
由容斥原理可知，第 i \rm i i 个报出的数为 k \rm k k 时，它们的关系为 i = k / 20 + k / 24 − k / l c m ( 20 , 24 ) \rm i=k/20+k/24-k/lcm(20,24) i=k/20+k/24−k/lcm(20,24) 即 i = 12 k \rm i=12k i=12k
试题 B: 类斐波那契循环数
本题总分： 5 5 5 分
【问题描述】
对于一个有
n
n
n 位的十进制数
N
=
d
1
d
2
d
3
⋯
d
n
N = d_1d_2d_3\cdots d_n
N=d1d2d3⋯dn，可以生成一个类斐波那契数列
S
S
S，数列
S
S
S 的前
n
n
n 个数为
{
S
1
=
d
1
,
S
2
=
d
2
,
S
3
=
d
3
,
⋯
,
S
n
=
d
n
}
\{S_1 = d1_, S_2 = d_2, S_3 = d_3, \cdots, S_n = d_n\}
{S1=d1,S2=d2,S3=d3,⋯,Sn=dn}，数列
S
S
S 的第
k
(
k
>
n
)
k(k > n)
k(k>n) 个数为
∑
i
=
k
−
n
k
−
1
S
i
\sum^{k−1}_{i=k−n} S_i
∑i=k−nk−1Si。如果这个数
N
N
N 会出现在对应的类斐波那契数列
S
S
S 中，那么
N
N
N 就是一个类斐波那契循环数。
例如对于
197
197
197，对应的数列
S
S
S 为
{
1
,
9
,
7
,
17
,
33
,
57
,
107
,
197
,
⋯
}
\{1, 9, 7, 17, 33, 57, 107, 197, \cdots \}
{1,9,7,17,33,57,107,197,⋯}，
197
197
197 出现在
S
S
S 中，所以
197
197
197 是一个类斐波那契循环数。
请问在
0
0
0 至
1
0
7
10^7
107 中，最大的类斐波那契循环数是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
7913837
假定答案为 7 7 7 位数，从后往前 B F \rm BF BF 就行
public class Main {
public static void main(String ...args) { new Main().run(); }
void run() {
int ans = 9999999, i, k;
int[] buf = new int[100];
for (;; --ans) {
for (i = 7, k = ans, buf[8] = 0; i > 0; --i, k /= 10) {
buf[8] += k % 10;
buf[i] = k % 10;
}
for (i = 8; buf[i] < ans; ++i) buf[i + 1] = 2 * buf[i] - buf[i - 7];
if (buf[i] == ans) break;
}
System.out.print(ans);
}
}
试题 C: 分布式队列
时间限制: 3.0 s 3.0\mathrm s 3.0s 内存限制: 512.0 M B 512.0\mathrm{MB} 512.0MB 本题总分： 10 10 10 分
【问题描述】
小蓝最近学习了一种神奇的队列：分布式队列。简单来说，分布式队列包含
N
N
N 个节点（编号为
0
0
0 至
N
−
1
N − 1
N−1，其中
0
0
0 号为主节点），其中只有一个主节点，其余为副节点。主/副节点中都各自维护着一个队列，当往分布式队列中添加元素时都是由主节点完成的（每次都会添加元素到队列尾部）；副节点只负责同步主节点中的队列。可以认为主/副节点中的队列是一个长度无限的一维数组，下标为
0
,
1
,
2
,
3
⋯
0, 1, 2, 3 \cdots
0,1,2,3⋯，同时副节点中的元素的同步顺序和主节点中的元素添加顺序保持一致。
由于副本的同步速度各异，因此为了保障数据的一致性，元素添加到主节点后，需要同步到所有的副节点后，才具有可见性。
给出一个分布式队列的运行状态，所有的操作都按输入顺序执行。你需要回答在某个时刻，队列中有多少个元素具有可见性。
【输入格式】
第一行包含一个整数
N
N
N，表示节点个数。
接下来包含多行输入，每一行包含一个操作，操作类型共有以下三种
：
：
：
a
d
d
、
s
y
n
c
add、sync
add、sync 和
q
u
e
r
y
query
query，各自的输入格式如下
：
：
：
1.
1.
1.
a
d
d
e
l
e
m
e
n
t
：
add\ element：
add element：表示这是一个添加操作，将元素
e
l
e
m
e
n
t
element
element 添加到队列中；
2.
2.
2.
s
y
n
c
f
o
l
l
o
w
e
r
_
i
d
：
sync\ follower\_id：
sync follower_id：表示这是一个同步操作，
f
o
l
l
o
w
e
r
_
i
d
follower\_id
follower_id 号副节点会从主节点中同步下一个自己缺失的元素；
3.
3.
3.
q
u
e
r
y
：
query：
query：查询操作，询问当前分布式队列中有多少个元素具有可见性。
【输出格式】
对于每一个 q u e r y query query 操作，输出一行，包含一个整数表示答案。
【样例输入】
3
add 1
add 2
query
add 1
sync 1
sync 1
sync 2
query
sync 1
query
sync 2
sync 2
sync 1
query
【样例输出】
0
1
1
3
【样例说明】
执行到第一个
q
u
e
r
y
query
query 时，队列内容如下
:
:
:
0
：
[
1
,
2
]
0：[1,2]
0：[1,2]
1
：
[
]
1：[]
1：[]
2
：
[
]
2：[]
2：[]
两个副节点中都无元素，因此答案为
0
0
0。
执行到第二个
q
u
e
r
y
query
query 时，队列内容如下
:
:
:
0
：
[
1
,
2
,
1
]
0：[1,2,1]
0：[1,2,1]
1
：
[
1
,
2
]
1：[1,2]
1：[1,2]
2
：
[
1
]
2：[1]
2：[1]
只有下标为
0
0
0 的元素被所有节点同步，因此答案为
1
1
1。
执行到第三个
q
u
e
r
y
query
query 时，队列内容如下
:
:
:
0
：
[
1
,
2
,
1
]
0：[1,2,1]
0：[1,2,1]
1
：
[
1
,
2
,
1
]
1：[1,2,1]
1：[1,2,1]
2
：
[
1
]
2：[1]
2：[1]
只有下标为
0
0
0 的元素被所有节点同步，因此答案为
1
1
1。
执行到第四个
q
u
e
r
y
query
query 时，队列内容如下
:
:
:
0
：
[
1
,
2
,
1
]
0：[1,2,1]
0：[1,2,1]
1
：
[
1
,
2
,
1
]
1：[1,2,1]
1：[1,2,1]
2
：
[
1
,
2
,
1
]
2：[1,2,1]
2：[1,2,1]
三个元素都被所有节点同步，因此答案为
3
3
3。
【评测用例规模与约定】
对于
30
%
30\%
30% 的评测用例
：
：
：
1
≤
1 ≤
1≤ 输入的操作数
≤
100
≤ 100
≤100。
对于
100
%
100\%
100% 的评测用例
：
：
：
1
≤
1 ≤
1≤ 输入的操作数
≤
2000
≤ 2000
≤2000，
1
≤
N
≤
10
1 ≤ N ≤ 10
1≤N≤10，
1
≤
f
o
l
l
o
w
e
r
_
i
d
<
N
1 ≤ f ollower\_id < N
1≤follower_id<N，
0
≤
e
l
e
m
e
n
t
≤
1
0
5
0 ≤ element ≤ 10^5
0≤element≤105。
感兴趣的可以去了解下能算在分布式队列一类的 K a f k a \rm Kafka Kafka 中的高水位机制，这里数据量太小，就随便弄两下
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.PrintWriter;
public class Main {
public static void main(String ...args) throws IOException { new Main().run(); }
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int[] LEO = new int[10];
void run() throws IOException {
in.nextToken();
int N = (int) in.nval;
while (in.nextToken() != StreamTokenizer.TT_EOF) {
switch (in.sval) {
case "add":
in.nextToken();
++LEO[0];
break;
case "sync":
in.nextToken();
int id = (int) in.nval;
if (LEO[id] < LEO[0]) ++LEO[id];
break;
case "query":
int HW = 2000;
for (int i = 0; i < N; ++i)
if (HW > LEO[i]) HW = LEO[i];
out.println(HW);
}
}
out.flush();
}
}
还有看到一些小白问 while(()) 停不下来，可以通过 Ctrl+Z 的方式强制关闭
J
a
v
a
\rm Java
Java 的输入流，也可以通过 Scanner(String source) 的方式构造输入工具，两种方法都可以辅助通过样例在本机完成初步测试
试题 D: 食堂
时间限制: 3.0 s 3.0\mathrm s 3.0s 内存限制: 512.0 M B 512.0\mathrm{MB} 512.0MB 本题总分： 10 10 10 分
【问题描述】
S S S 学校里一共有 a 2 a_2 a2 个两人寝、 a 3 a_3 a3 个三人寝， a 4 a_4 a4 个四人寝，而食堂里有 b 4 b_4 b4 个四人桌和 b 6 b_6 b6 个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐，请问这个食堂最多同时满足多少同学用餐？
【输入格式】
采用多组数据输入。
输入共
q
+
1
q + 1
q+1 行。
第一行为一个正整数
q
q
q 表示数据组数。
后面
q
q
q 行，每行五个非负整数
a
2
，
a
3
，
a
4
，
b
4
，
b
6
a_2，a_3，a_4，b_4，b_6
a2，a3，a4，b4，b6 表示一组数据。
【输出格式】
输出共 q q q 行，每行一个整数表示对应输入数据的答案。
【样例输入】
2
3 0 1 0 1
0 2 2 1
【样例输出】
6
10
【样例说明】
对于第一组数据，只有一个六人桌，因此最多安排三个两人寝的同学就餐，答案为
(
2
+
2
+
2
)
=
6
(2 + 2 + 2) = 6
(2+2+2)=6。
对于第二组数据，用一个六人桌安排两个三人寝的同学，用一个四人桌安排一个四人寝的同学，答案为
(
3
+
3
)
+
(
4
)
=
10
(3 + 3) + (4) = 10
(3+3)+(4)=10。
【评测用例规模与约定】
对于
20
%
20\%
20% 的评测用例，保证
a
2
+
a
3
+
a
4
≤
8
a_2 + a_3 + a_4 ≤ 8
a2+a3+a4≤8。
对于
100
%
100\%
100% 的评测用例，保证
q
≤
100
，
b
4
+
b
6
≤
a
2
+
a
3
+
a
4
≤
100
q ≤ 100，b_4 + b_6 ≤ a_2 + a_3 + a_4 ≤ 100
q≤100，b4+b6≤a2+a3+a4≤100。
直觉上是贪心，细看数据范围可以做
d
p
\rm dp
dp，但两种在 OJ 上都是
W
r
o
n
g
A
n
s
w
e
r
\rm Wrong\ Answer
Wrong Answer，结合站内统计来看有一定的测试点用例错误的可能在里面，当然也可能是本人在不同思路的实现上均犯了低级错误导致。
d
p
\rm dp
dp 转移时变量按题面命名的，没什么好说的，贪心大体则是按转移的这几种情况优先让每个桌子空位最少比如四人桌有
4
、
3
、
2
、
2
,
2
4、3、2、2,2
4、3、2、2,2 四种坐法，优先让
4
、
2
,
2
4、2,2
4、2,2 坐，而在此之中
4
4
4 先坐的价值肯定是比
2
,
2
2,2
2,2 高的。当我胡诌吧，感觉挺难证的。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import static java.lang.Math.max;
public class Main {
public static void main(String ...args) { new Main().run(); }
void run() {
int q = nextInt(), x = 0, y = 0, z = 0, k = 0, g = 0;
int[][] query = new int[q][5];
for (int i = 0; i < q; ++i) {
x = max(x, query[i][0] = nextInt());
y = max(y, query[i][1] = nextInt());
z = max(z, query[i][2] = nextInt());
k = max(k, query[i][3] = nextInt());
g = max(g, query[i][4] = nextInt());
}
int[][][][][] ans = new int[k + 2][g + 2][x + 4][y + 3][z + 2];
for (int b4 = 0; b4 <= k; ++b4)
for (int b6 = 0; b6 <= g; ++b6)
for (int a2 = 0; a2 <= x; ++a2)
for (int a3 = 0; a3 <= y; ++a3)
for (int a4 = 0; a4 <= z; ++a4) {
ans[b4 + 1][b6][a2][a3][a4 + 1] = max(ans[b4 + 1][b6][a2][a3][a4 + 1], ans[b4][b6][a2][a3][a4] + 4);
ans[b4 + 1][b6][a2][a3 + 1][a4] = max(ans[b4 + 1][b6][a2][a3 + 1][a4], ans[b4][b6][a2][a3][a4] + 3);
ans[b4 + 1][b6][a2 + 1][a3][a4] = max(ans[b4 + 1][b6][a2 + 1][a3][a4], ans[b4][b6][a2][a3][a4] + 2);
ans[b4 + 1][b6][a2 + 2][a3][a4] = max(ans[b4 + 1][b6][a2 + 2][a3][a4], ans[b4][b6][a2][a3][a4] + 4);
ans[b4][b6 + 1][a2][a3][a4 + 1] = max(ans[b4][b6 + 1][a2][a3][a4 + 1], ans[b4][b6][a2][a3][a4] + 4);
ans[b4][b6 + 1][a2][a3 + 1][a4] = max(ans[b4][b6 + 1][a2][a3 + 1][a4], ans[b4][b6][a2][a3][a4] + 3);
ans[b4][b6 + 1][a2 + 1][a3][a4] = max(ans[b4][b6 + 1][a2 + 1][a3][a4], ans[b4][b6][a2][a3][a4] + 2);
ans[b4][b6 + 1][a2 + 1][a3][a4 + 1] = max(ans[b4][b6 + 1][a2 + 1][a3][a4 + 1], ans[b4][b6][a2][a3][a4] + 6);
ans[b4][b6 + 1][a2 + 1][a3 + 1][a4] = max(ans[b4][b6 + 1][a2 + 1][a3 + 1][a4], ans[b4][b6][a2][a3][a4] + 5);
ans[b4][b6 + 1][a2][a3 + 2][a4] = max(ans[b4][b6 + 1][a2][a3 + 2][a4], ans[b4][b6][a2][a3][a4] + 6);
ans[b4][b6 + 1][a2 + 2][a3][a4] = max(ans[b4][b6 + 1][a2 + 2][a3][a4], ans[b4][b6][a2][a3][a4] + 4);
ans[b4][b6 + 1][a2 + 3][a3][a4] = max(ans[b4][b6 + 1][a2 + 3][a3][a4], ans[b4][b6][a2][a3][a4] + 6);
}
for (int i = 0; i < q; ++i)
System.out.println(ans[query[i][3]][query[i][4]][query[i][0]][query[i][1]][query[i][2]]);
}
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int nextInt() {
try {
in.nextToken();
} catch (IOException e) {
e.printStackTrace();
}
return (int) in.nval;
}
}
比赛的时候建议是上 d p \rm dp dp 的，因为很稳，不过这里的程序在极端边界数据下可能会爆掉，建议改用 s h o r t \rm short short 并对极端数据做一定的优化，例如如上程序可以看做将所有问题合并成一个问题，比赛时有剩余时间则可以改成一定策略划分成若干问题，而后用同样的方式处理，以确保在 3.0 s 3.0\mathrm s 3.0s、 512.0 M B 512.0\mathrm{MB} 512.0MB 限制下可以运行完毕。
试题 E: 最优分组
时间限制: 3.0 s 3.0\mathrm s 3.0s 内存限制: 512.0 M B 512.0\mathrm{MB} 512.0MB 本题总分： 15 15 15 分
【问题描述】
小蓝开了一家宠物店，最近有一种
X
X
X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。为了减少使用的测试剂数目，小蓝想到了一个好方法：将
N
N
N 个宠物平均分为若干组，使得每组恰好有
K
K
K 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有
K
K
K 只宠物单独检测，需要再消耗
K
K
K 支测试剂（当
K
=
1
K = 1
K=1 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。
现在我们已知小蓝的宠物被感染的概率为
p
p
p，请问
K
K
K 应该取值为多少才能使得期望的测试剂的消耗数目最少？如果有多个答案输出最小的
K
K
K。
【输入格式】
第一行，一个整数
N
N
N。
第二行，一个浮点数
p
p
p。
【输出格式】
输出一行，一个整数 K K K 表示答案。
【样例输入】
1000
0.05
【样例输出】
5
【评测用例规模与约定】
对于
30
%
30\%
30% 的评测用例：
1
≤
N
≤
10
1 ≤ N ≤ 10
1≤N≤10。
对于
60
%
60\%
60% 的评测用例：
1
≤
N
≤
1000
1 ≤ N ≤ 1000
1≤N≤1000。
对于
100
%
100\%
100% 的评测用例：
1
≤
N
≤
1
0
6
，
0
≤
p
≤
1
1 ≤ N ≤ 10^6，0 ≤ p ≤ 1
1≤N≤106，0≤p≤1。
纯送分
import java.util.Scanner;
public class Main {
public static void main(String ...args) { new Main().run(); }
void run() {
Scanner in = new Scanner(System.in);
int N = in.nextInt(), x = 1;
double p = in.nextDouble(), q = 1 - p, y = N;
for (int k = 2; k <= N; ++k) {
q = q * (1 - p);
if (N % k != 0) continue;
double g = N / k + N * (1 - q);
if (g < y) {
y = g;
x = k;
}
}
System.out.print(x);
}
}
蓝桥杯，弟中之弟，国一出来工作都找不到