Java 大学C组
- 试题 A: 斐波那契与 7
- 试题 B: 小蓝做实验
- 试题 C: 取模
- 试题 D: 内存空间
- 试题 E: 斐波那契数组
- 试题 F: 最大公约数
- 试题 G: 交通信号
- 试题 H: 点亮
- 试题 I: 打折
- 试题 J: 宝石收集
试题 A: 斐波那契与 7
本题总分： 5 5 5 分
【问题描述】
斐波那契数列的递推公式为 ： ： ： F n = F n − 1 + F n − 2 F_n = F_{n−1} + F_{n−2} Fn=Fn−1+Fn−2，其中 F 1 = F 2 = 1 F_1 = F_2 = 1 F1=F2=1。
请问，斐波那契数列的第 1 1 1 至 202202011200 202202011200 202202011200 项（含）中，有多少项的个位是 7 7 7。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。
26960268160
找循环节
找到斐波那契数列在个位上的循环节，然后将答案拆分成三部分就完事了。
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) { new Test().run(); }
long N = 202202011200L;
void run() {
Map map = new HashMap();
int[] cnt = new int[100];
map.put(01, 1);
int i, j, F1 = 0, F2 = 1, F3 = 0;
for (i = 2; ; ++i) {
F3 = (F1 + F2) % 10;
cnt[i] = cnt[i - 1];
if (F3 == 7) ++cnt[i];
if (map.containsKey(F2 * 10 + F3)) break;
map.put(F2 * 10 + F3, i);
F1 = F2;
F2 = F3;
}
j = map.get(F2 * 10 + F3);
System.out.print(
cnt[j - 1] +
((N - j + 1) / (i - j)) * (cnt[i] - cnt[j]) +
cnt[(int)(N % (i - j)) - j + 1]
);
}
}
试题 B: 小蓝做实验
本题总分： 5 5 5 分
【问题描述】
小蓝很喜欢科研，他最近做了一个实验得到了一批实验数据，一共是两百万个正整数。如果按照预期，所有的实验数据 x x x 都应该满足 1 0 7 ≤ x ≤ 1 0 8 10^7 ≤ x ≤ 10^8 107≤x≤108。但是做实验都会有一些误差，会导致出现一些预期外的数据，这种误差数据 y y y 的范围是 1 0 3 ≤ y ≤ 1 0 12 10^3 ≤ y ≤ 10^{12} 103≤y≤1012 。由于小蓝做实验很可靠，所以他所有的实验数据中 99.99 % 99.99% 99.99% 以上都是符合预期的。小蓝的所有实验数据都在 p r i m e s . t x t mathrm{primes.txt} primes.txt 中，现 在他想统计这两百万个正整数中有多少个是质数，你能告诉他吗？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
342693
欧拉筛
首先排除 M i l l e r mathrm{Miller} Miller- R o b i n mathrm{Robin} Robin，一般 T T T 次询问的题目， T T T 越大，对单次询问响应的复杂度要求越高，于是考虑欧拉筛线性筛出不大于 1 e 8 1e8 1e8 的质数， O ( 1 ) O(1) O(1) 响应 99.99 % 99.99% 99.99% 的询问，而剩下询问中， y y y 不会大于 1 e 16 1e16 1e16，利用因数的对称性，可以在 O ( y ) O(sqrt y) O(y ) 的复杂下响应。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.FileInputStream;
public class Test {
public static void main(String[] args) { new Test().run(); }
int i, N = (int)1e8, M = 0, cnt = 0;
void run() {
boolean[] composite = new boolean[N + 1];
int[] prime = new int[(int)(1.1 * N / Math.log(N))];
for (int n = 2; n <= N; ++n) {
if (!composite[n])
prime[M++] = n;
for (int i = 0; i < M; ++i) {
if (prime[i] * n > N) break;
composite[prime[i] * n] = true;
if (n % prime[i] == 0) break;
}
}
try (BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("primes.txt")))) {
while (true) {
String line = in.readLine();
if (line == null) break;
long n = Long.parseLong(line);
if (n > 1e8) {
for (i = 0; prime[i] <= 1e6; ++i)
if (n % prime[i] == 0) break;
if (prime[i] > 1e6) ++ cnt;
} else if (!composite[(int)n]) ++cnt;
}
} catch (Exception e) {
e.printStackTrace();
}
System.out.print(cnt);
}
}
试题 C: 取模
时间限制: 3.0 s 3.0mathrm s 3.0s 内存限制: 512.0 M B 512.0mathrm{MB} 512.0MB 本题总分： 10 10 10 分
【问题描述】
给定
n
,
m
n,m
n,m，问是否存在两个不同的数
x
,
y
x,y
x,y 使得
1
≤
x
<
y
≤
m
1 ≤ x < y≤m
1≤x 【输入格式】 输入包含多组独立的询问。 第一行包含一个整数
T
T
T 表示询问的组数。 接下来
T
T
T 行每行包含两个整数
n
,
m
n,m
n,m，用一个空格分隔，表示一组询问。 【输出格式】 输出
T
T
T 行，每行依次对应一组询问的结果。如果存在，输出单词
Y
e
s
mathrm{Yes}
Yes；如果不存在，输出单词
N
o
mathrm{No}
No。 【样例输入】 【样例输出】 【评测用例规模与约定】 对于
20
%
20%
20% 的评测用例，
T
≤
100
，
n
,
m
≤
1000
T ≤100 ，n,m≤1000
T≤100，n,m≤1000； 假定
n
≥
m
n geq m
n≥m，转换命题为，给定两个整数
n
,
m
n,m
n,m，
n
≥
1
,
m
≥
2
n geq 1,m geq 2
n≥1,m≥2，问
k
=
1
,
2
,
⋯
,
m
k = 1, 2, cdots,m
k=1,2,⋯,m，
n
mod
k
n operatorname{mod} k
nmodk 是否恰取遍
[
0
,
m
−
1
]
[0, m-1]
[0,m−1]， 更近一步引出等价命题，
n
mod
k
≡
k
−
1
n operatorname{mod} k equiv k-1
nmodk≡k−1 是否在
k
∈
[
1
,
m
)
k in [1,m)
k∈[1,m) 下都成立，因为
n
mod
1
≡
0
n operatorname{mod} 1 equiv 0
nmod1≡0，
n
mod
2
n operatorname{mod} 2
nmod2 若想使上述命题为真，只能取
1
1
1，以此类推。 于是有同余方程组，当
n
n
n 满足下列方程组时，无论如何也找不到两个不同的数
x
,
y
x,y
x,y 使得
1
≤
x
<
y
≤
m
1 ≤ x < y≤m
1≤x 这启发了我们，只需枚举不超过
13
13
13 个数（
13
!
≥
1
e
9
13! geq 1e9
13!≥1e9），就可以判断
n
,
m
n,m
n,m 是否满足上列同余式，继而判断
n
,
m
n,m
n,m 是否满足原命题。 时间限制:
3.0
s
3.0mathrm s
3.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
10
10
10 分 【问题描述】 小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。 为了简化问题，变量的类型只有以下三种：
i
n
t
：
mathrm{int}：
int：整型变量，一个
i
n
t
mathrm{int}
int 型变量占用
4
B
y
t
e
4 mathrm{Byte}
4 Byte 的内存空间。 定义变量的语句只有两种形式，第一种形式为
：
：
：
t
y
p
e
v
a
r
1
=
v
a
l
u
e
1
,
v
a
r
2
=
v
a
l
u
e
2
⋯
;
mathrm{type var1=value1}, mathrm{var2=value2}cdots;
type var1=value1, var2=value2⋯; 定义了若干个
t
y
p
e
mathrm{type}
type 类型变量
v
a
r
1
mathrm{var1}
var1、
v
a
r
2
mathrm{var2}
var2、
⋯
cdots
⋯，并且用
v
a
l
u
e
1
mathrm{value1}
value1、
v
a
l
u
e
2
⋯
mathrm{value2}cdots
value2⋯ 初始化， 多个变量之间用
’
,
’
’,’
’,’ 分隔，语句以
’
;
’
’;’
’;’ 结尾，
t
y
p
e
rm type
type 可能是
i
n
t
rm int
int、
l
o
n
g
rm long
long 或
S
t
r
i
n
g
rm String
String。例如
i
n
t
a
=
1
,
b
=
5
,
c
=
6
;
rm int a=1, b=5, c=6;
inta=1, b=5, c=6; 占用空间为
12
B
y
t
e
12 rm Byte
12 Byte；
l
o
n
g
a
=
1
,
b
=
5
;
rm long a=1, b=5;
long a=1, b=5; 占用空间为
16
B
y
t
e
16 rm Byte
16 Byte；
S
t
r
i
n
g
s
1
=
”
”
,
s
2
=
”
h
e
l
l
o
”
,
s
3
=
”
w
o
r
l
d
”
;
rm String s1=””, s2=”hello”, s3=”world”;
String s1=””, s2=”hello”, s3=”world”; 占用空间为
10
B
y
t
e
10 rm Byte
10 Byte。 第二种形式为
：
：
：
t
y
p
e
[
]
a
r
r
1
=
n
e
w
t
y
p
e
[
s
i
z
e
1
]
,
a
r
r
2
=
n
e
w
t
y
p
e
[
s
i
z
e
2
]
⋯
;
rm type[:] arr1=new type[size1],arr2=new type[size2]cdots;
type[] arr1=new type[size1],arr2=new type[size2]⋯; 定义了若干
t
y
p
e
rm type
type 类型的一维数组变量
a
r
r
1
rm arr1
arr1、
a
r
r
2
⋯
rm arr2cdots
arr2⋯，且数组的大小为
s
i
z
e
1
rm size1
size1、
s
i
z
e
2
⋯
rm size2cdots
size2⋯，多个变量之间用
’
,
’
’,’
’,’ 进行分隔，语句以
’
;
’
’;’
’;’ 结尾，
t
y
p
e
rm type
type 只可能是
i
n
t
rm int
int 或
l
o
n
g
rm long
long。例如
i
n
t
[
]
a
1
=
n
e
w
i
n
t
[
10
]
;
rm int[:] a1=new int[10];
int[] a1=new int[10]; 占用的内存空间为
40
B
y
t
e
40 rm Byte
40 Byte；
l
o
n
g
[
]
a
1
=
n
e
w
l
o
n
g
[
10
]
,
a
2
=
n
e
w
l
o
n
g
[
10
]
;
rm long[:] a1=new long[10], a2=new long[10];
long[] a1=new long[10], a2=new long[10]; 占用的内存空间为
160
B
y
t
e
160 rm Byte
160 Byte。 已知小蓝有
T
T
T 条定义变量的语句，请你帮他统计下一共占用了多少内存空间。结果的表示方式为
：
：
：
a
G
B
b
M
B
c
K
B
d
B
amathrm{GB}bmathrm{MB}cmathrm{KB}dmathrm B
aGBbMBcKBdB，其中
a
a
a、
b
b
b、
c
c
c、
d
d
d 为统计的结果，
G
B
rm GB
GB、
M
B
rm MB
MB、
K
B
rm KB
KB、
B
rm B
B 为单位。优先用大的单位来表示，
1
G
B
=
1024
M
B
rm 1GB=1024MB
1GB=1024MB，
1
M
B
=
1024
K
B
rm 1MB=1024KB
1MB=1024KB，
1
K
B
=
1024
B
rm 1KB=1024B
1KB=1024B，其中
B
B
B 表示
B
y
t
e
rm Byte
Byte。如果
a
a
a、
b
b
b、
c
c
c、
d
d
d 中的某几个数字为
0
0
0，那么不必输出这几个数字及其单位。题目保证一行中只有一句定义变量的语句，且每条语句都满足题干中描述的定义格式，所有的变量名都是合法的且均不重复。题目中的数据很规整，和上述给出的例子类似，除了类型后面有一个空格，以及定义数组时
n
e
w
rm new
new 后面的一个空格之外，不会出现多余的空格。 【输入格式】 输入的第一行包含一个整数
T
T
T ，表示有
T
T
T 句变量定义的语句。 接下来
T
T
T 行，每行包含一句变量定义语句。 【输出格式】 输出一行包含一个字符串，表示所有语句所占用空间的总大小。 【样例输入 1】 【样例输出 1】 【样例输入 2】 【样例输出 2】 【样例说明】 【评测用例规模与约定】 对于所有评测用例，
1
≤
T
≤
10
1 ≤ T ≤ 10
1≤T≤10，每条变量定义语句的长度不会超过
1000
1000
1000。所有的变量名称长度不会超过
10
10
10，且都由小写字母和数字组成。对于整型变 量，初始化的值均是在其表示范围内的十进制整数，初始化的值不会是变量。 对于
S
t
r
i
n
g
rm String
String 类型的变量，初始化的内容长度不会超过
50
50
50，且内容仅包含小写 字母和数字，初始化的值不会是变量。对于数组类型变量，数组的长度为一个 整数，范围为
：
：
：
[
0
,
2
30
]
[0,2^{30}]
[0,230]，数组的长度不会是变量。
T
T
T 条语句定义的变量所占的内存空间总大小不会超过
1
G
B
1 rm GB
1 GB，且大于
0
B
0 rm B
0 B。 时间限制:
3.0
s
3.0mathrm s
3.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
15
15
15 分 【问题描述】 如果数组
A
=
(
a
0
,
a
1
,
⋯
,
a
n
−
1
)
A = (a_0,a_1,cdots ,a_{n−1})
A=(a0,a1,⋯,an−1) 满足以下条件，就说它是一个斐波那契数组
：
：
：
1.
1.
1.
n
≥
2
n≥2
n≥2； 现在，给出一个数组
A
A
A ，你可以执行任意次修改，每次修改将数组中的某个位置的元素修改为一个大于
0
0
0 的整数。请问最少修改几个元素之后，数组
A
A
A 会变成一个斐波那契数组。 【输入格式】 输入的第一行包含一个整数
n
n
n，表示数组
A
A
A 中的元素个数。 第二行包含
n
n
n 个整数
a
0
,
a
1
,
⋯
,
a
n
−
1
a_0,a_1, cdots,a_{n−1}
a0,a1,⋯,an−1，相邻两个整数之间用一个空格分隔。 【输出格式】 输出一行包含一个整数表示最少需要修改数组
A
A
A 中的几个元素之后，数组
A
A
A 可以变为一个斐波那契数组。 【样例输入】 【样例输出】 【样例说明】 【评测用例规模与约定】 对于所有评测用例，
2
≤
n
≤
1
0
5
，
1
≤
a
i
≤
1
0
6
2≤n≤10^5 ，1≤a_i ≤10^6
2≤n≤105，1≤ai≤106。 首先，
F
31
>
1
e
6
F_{31} > 1e6
F31>1e6，而
1
≤
a
i
≤
1
0
6
1≤a_i ≤10^6
1≤ai≤106，于是无论
a
0
,
a
1
a_0,a_1
a0,a1 取哪个正整数，从
A
A
A 的第
30
30
30 项开始，所有的元素都需要修改， 同时，令
G
G
G 为
G
1
=
G
2
=
g
G_1 =G_2 =g
G1=G2=g 的 “广义斐波那契数列”（这个名词其实已经被定义了），观察
F
F
F 与
G
G
G 各项
:
:
:
G
1
=
g
F
1
G_1 = gF_1
G1=gF1 于是我们只需统计
A
A
A 中，与
F
F
F 比值出现频率最高的项集，然后将其的补集替换为对应的 “广义斐波那契数列” 就行了。 时间限制:
3.0
s
3.0mathrm s
3.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
15
15
15 分 【问题描述】 给定一个数组，每次操作可以选择数组中任意两个相邻的元素
x
,
y
x,y
x,y 并将其中的一个元素替换为
gcd
(
x
,
y
)
gcd(x,y)
gcd(x,y)，其中
gcd
(
x
,
y
)
gcd(x,y)
gcd(x,y) 表示
x
x
x 和
y
y
y 的最大公约数。 请问最少需要多少次操作才能让整个数组只含
1
1
1。 【输入格式】 输入的第一行包含一个整数
n
n
n，表示数组长度。 第二行包含
n
n
n 个整数
a
1
,
a
2
,
⋯
,
a
n
a_1, a_2, cdots, a_n
a1,a2,⋯,an，相邻两个整数之间用一个空格分隔。 【输出格式】 输出一行包含一个整数，表示最少操作次数。如果无论怎么操作都无法满足要求，输出
−
1
−1
−1。 【样例输入】 【样例输出】 【评测用例规模与约定】 对于
30
%
30%
30% 的评测用例，
n
≤
500
，
a
i
≤
1000
n≤500，a_i ≤1000
n≤500，ai≤1000； 有
gcd
(
a
,
1
)
=
gcd
(
1
,
a
)
=
1
gcd(a,1) = gcd(1,a) = 1
gcd(a,1)=gcd(1,a)=1， 故当有任意
i
i
i，
a
i
=
1
a_i = 1
ai=1 时，从
i
i
i 开始向周围 “扩散”，则只需
n
−
为
1
的
元
素
个
数
n - 为 1 的元素个数
n−为 1 的元素个数 次操作，就能让整个数组只含
1
1
1，当
gcd
(
a
i
,
a
i
+
1
)
=
1
gcd(a_i,a_{i + 1}) = 1
gcd(ai,ai+1)=1 时也是同理。 当
A
A
A 中不存在相邻两数互质的情况时，考虑找到一对
i
,
j
i,j
i,j，满足
gcd
(
a
i
,
a
i
+
1
,
⋯
,
a
j
)
=
1
gcd(a_i,a_{i+1},cdots,a_j) = 1
gcd(ai,ai+1,⋯,aj)=1，且
j
−
i
j - i
j−i 最小，线段树维护
gcd
gcd
gcd，做一遍滑动窗口就完了。 时间限制:
3.0
s
3.0mathrm s
3.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
20
20
20 分 【问题描述】
L
Q
rm LQ
LQ 市的交通系统可以看成由
n
n
n 个结点和
m
m
m 条有向边组成的有向图。在每条边上有一个信号灯，会不断按绿黄红黄绿黄红黄… 的顺序循环 (初始时刚好变到绿灯)。当信号灯为绿灯时允许正向通行，红灯时允许反向通行，黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立，其中黄灯的持续时长等同于走完路径的耗时。当走到一条边上时，需要观察边上的信号灯，如果允许通行则可以通过此边，在通行过程中不再受信号灯的影响；否则需要等待，直到允许通行。 请问从结点
s
s
s 到结点
t
t
t 所需的最短时间是多少，如果
s
s
s 无法到达
t
t
t 则输出
−
1
−1
−1。 【输入格式】 输入的第一行包含四个整数
n
,
m
,
s
,
t
n,m,s,t
n,m,s,t，相邻两个整数之间用一个空格分隔。 接下来
m
m
m 行，每行包含五个整数
u
i
,
v
i
,
g
i
,
r
i
,
d
i
u_i,v_i,g_i,r_i,d_i
ui,vi,gi,ri,di，相邻两个整数之间用一个空格分隔，分别表示一条边的起点，终点，绿灯、红灯的持续时长和距离（黄灯的持续时长）。 【输出格式】 输出一行包含一个整数表示从结点
s
s
s 到达
t
t
t 所需的最短时间。 【样例输入】 【样例输出】 【评测用例规模与约定】 对于
40
%
40%
40% 的评测用例，
n
≤
500
n≤500
n≤500，
1
≤
g
i
,
r
i
,
d
i
≤
100
1≤g_i,r_i,d_i ≤100
1≤gi,ri,di≤100； 时间限制:
3.0
s
3.0mathrm s
3.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
20
20
20 分 【问题描述】 小蓝最近迷上了一款名为《点亮》的谜题游戏，游戏在一个
n
×
n
n×n
n×n 的格子棋盘上进行，棋盘由黑色和白色两种格子组成，玩家在白色格子上放置灯泡，确保任意两个灯泡不会相互照射，直到整个棋盘上的白色格子都被点亮（每个谜题均为唯一解）。灯泡只会往水平和垂直方向发射光线，照亮整行和整列，除非它的光线被黑色格子挡住。黑色格子上可能有从
0
0
0 到
4
4
4 的整数数字，表示与其上下左右四个相邻的白色格子共有几个灯泡；也可能没有数字，这表示可以在上下左右四个相邻的白色格子处任意选择几个位置放置灯泡。游戏的目标是选择合适的位置放置灯泡，使得整个棋盘上的白色格子都被照亮。 例如，有一个黑色格子处数字为
4
4
4，这表示它周围必须有
4
4
4 个灯泡，需要在他的上、下、左、右处分别放置一个灯泡；如果一个黑色格子处数字为
2
2
2，它的上下左右相邻格子只有
3
3
3 个格子是白色格子，那么需要从这三个白色格子中选择两个来放置灯泡；如果一个黑色格子没有标记数字，且其上下左右相邻格子全是白色格子，那么可以从这
4
4
4 个白色格子中任选出
0
0
0 至
4
4
4 个来放置灯泡。 题目保证给出的数据是合法的，黑色格子周围一定有位置可以放下对应数量的灯泡。且保证所有谜题的解都是唯一的。 现在，给出一个初始的棋盘局面，请在上面放置好灯泡，使得整个棋盘上的白色格子被点亮。 【输入格式】 输入的第一行包含一个整数
n
n
n，表示棋盘的大小。 接下来
n
n
n 行，每行包含
n
n
n 个字符，表示给定的棋盘。字符 . 表示对应的格子为白色，数字字符
0
0
0、
1
1
1、
2
2
2、
3
3
3、
4
4
4 表示一个有数字标识的黑色格子，大写字母
X
rm X
X 表示没有数字标识的黑色格子。 【输出格式】 输出
n
n
n 行，每行包含
n
n
n 个字符，表示答案。大写字母
O
rm O
O 表示对应的格子包含灯泡，其它字符的意义与输入相同。 【样例输入】 【样例输出】 【样例说明】 【评测用例规模与约定】 对于所有评测用例，
2
≤
n
≤
5
2≤n≤5
2≤n≤5，且棋盘上至少有
15
%
15%
15% 的格子是黑色格子。 时间限制:
5.0
s
5.0mathrm s
5.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
25
25
25 分 【问题描述】 小蓝打算采购
n
n
n 种物品，每种物品各需要
1
1
1 个。 小蓝所住的位置附近一共有
m
m
m 个店铺，每个店铺都出售着各种各样的物品。 第
i
i
i 家店铺会在第
s
i
s_i
si 天至第
t
i
t_i
ti 天打折，折扣率为
p
i
p_i
pi，对于原件为
b
b
b 的物品，折后价格为
⌊
b
⋅
p
j
100
⌋
lfloorfrac {bcdot p_j}{100}rfloor
⌊100b⋅pj⌋。其它时间需按原价购买。 小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花多少钱才能买到需要的所有物品。 题目保证小蓝一定能买到需要的所有物品。 【输入格式】 输入的第一行包含两个整数
n
,
m
n,m
n,m，用一个空格分隔，分别表示物品的个数和店铺的个数。 接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包含四个整数
s
i
,
t
i
,
p
i
,
c
i
s_i,t_i, p_i,c_i
si,ti,pi,ci，相邻两个整数之间用一个空格分隔，分别表示商店优惠的起始和结束时间、折扣率以及商店内的商品总数。之后接
c
i
c_i
ci 行，每行包含两个整数
a
j
,
b
j
a_j,b_j
aj,bj，用一个空格分隔，分别表示该商店的第
j
j
j 个商品的类型和价格。商品的类型由
1
1
1 至
n
n
n 编号。 【输出格式】 输出一行包含一个整数表示小蓝需要花费的最少的钱数。 【样例输入】 【样例输出】 【评测用例规模与约定】 对于
40
%
40%
40% 的评测用例，
n
,
m
≤
500
，
s
i
≤
t
i
≤
100
，
Σ
c
i
≤
2000
n,m≤500，s_i ≤t_i ≤100，Sigma c_i ≤2000
n,m≤500，si≤ti≤100，Σci≤2000； 时间限制:
5.0
s
5.0mathrm s
5.0s 内存限制:
512.0
M
B
512.0mathrm{MB}
512.0MB 本题总分：
25
25
25 分 【问题描述】 小蓝最近迷上了一款收集宝石的游戏，在游戏中给出了一幅藏宝图，藏宝图可以看做是由
n
n
n 个顶点组成的一个有向图，顶点编号为
0
,
1
,
2
,
⋯
,
n
−
1
0,1,2, cdots,n−1
0,1,2,⋯,n−1。每个顶点有且仅有一颗宝石，可能是红宝石或蓝宝石。 小蓝有一次收集宝石的机会，他可以任意选择一个顶点当做起点，沿着有向边前进，经过的顶点上的宝石都会被自动收集（包括起点和终点），直到前方无路可走或者小蓝想退出时停止本次收集。小蓝可以多次经过同一个顶点，但只会在第一次到达顶点时获得宝石，后面再次到达时不会再获得宝石。 收集结束后，小蓝可以用手中的宝石合成紫晶宝石：一颗红宝石加一颗蓝宝石就可以合成一颗紫晶宝石。 小蓝想在收集结束后合成尽可能多的紫晶宝石，请帮他规划出一条最优路径，告诉他最多可以合成多少颗紫晶宝石。 【输入格式】 输入的第一行包含一个整数
n
n
n，表示有顶点的个数。 第二行包含一个由
0
0
0、
1
1
1 组成的长度为
n
n
n 的字符串，从左至右依次表示第
0
0
0 至
n
−
1
n−1
n−1 个顶点处宝石的种类，
0
0
0 表示红宝石，
1
1
1 表示蓝宝石。 第三行包含一个整数
m
m
m ，表示图中有
m
m
m 条有向边。 接下来
m
m
m 行，每行包含两个整数
s
,
t
s,t
s,t，用一个空格分隔，表示一条从
s
s
s 到
t
t
t 的有向边。 【输出格式】 输出一行包含一个整数，表示小蓝最多能合成几颗紫晶宝石。 【样例输入】 【样例输出】 【样例说明】 样例如上图所示，选择
0
0
0 号顶点作为起点，按照
0
→
1
→
2
→
3
→
1
→
2
→
4
0 → 1 → 2 → 3 → 1 → 2 → 4
0→1→2→3→1→2→4 的行进路线，可以获得
3
3
3 颗红宝石和
2
2
2 颗蓝宝石，最终可以合成
2
2
2 颗紫晶宝石；他也可以按照
1
→
2
→
3
→
1
→
2
→
4
1 → 2 → 3 → 1 → 2 → 4
1→2→3→1→2→4 行进，结果也是
2
2
2。找不到比
2
2
2 更大的答案了。 【评测用例规模与约定】 对于所有的评测用例，
1
≤
n
≤
2000
，
0
≤
m
≤
1
0
5
，
0
≤
s
≤
n
−
1
，
0
≤
t
≤
n
−
1
1 ≤ n ≤ 2000，0 ≤ m ≤ 10^5，0 ≤ s ≤ n − 1，0≤t≤n−1
1≤n≤2000，0≤m≤105，0≤s≤n−1，0≤t≤n−1。3
1 2
5 2
999 99
No
No
Yes
对于
50
%
50%
50% 的评测用例，
T
≤
10000
，
n
,
m
≤
1
0
5
T ≤10000 ，n,m≤10^5
T≤10000，n,m≤105；
对于所有评测用例，
1
≤
T
≤
1
0
5
，
1
≤
n
≤
1
0
9
，
2
≤
m
≤
1
0
9
1≤T ≤10^5 ，1≤n≤10^9 ，2≤m≤10^9
1≤T≤105，1≤n≤109，2≤m≤109。
中国剩余定理
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.io.PrintWriter;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
PrintWriter out = new PrintWriter(System.out);
for (int T = nextInt(); T-- > 0;) {
int n = nextInt(), m = nextInt();
boolean flag = false;
if (m > 13) m = 13;
for (int k = 2; k <= m; ++k)
if (n % k != k - 1) flag = true;
out.println(flag ? "Yes" : "No");
}
out.flush();
}
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: 内存空间
l
o
n
g
：
mathrm{long}：
long：长整型变量，一个
l
o
n
g
mathrm{long}
long 型变量占用
8
B
y
t
e
8 mathrm{Byte}
8 Byte 的内存空间。
S
t
r
i
n
g
：
mathrm{String}：
String：字符串变量，占用空间和字符串长度有关，设字符串长度为
L
L
L，则字符串占用
L
B
y
t
e
L mathrm{Byte}
L Byte 的内存空间，如果字符串长度为
0
0
0 则占用
0
B
y
t
e
0 mathrm{Byte}
0 Byte 的内存空间。1
long[] nums=new long[131072];
1MB
4
int a=0,b=0;
long x=0,y=0;
String s1="hello",s2="world";
long[] arr1=new long[100000],arr2=new long[100000];
1MB538KB546B
样例
1
1
1，占用的空间为
131072
×
8
=
1048576
B
131072×8 = 1048576 mathrm B
131072×8=1048576 B，换算过后正好是
1
M
B
1 rm MB
1 MB，其 它三个单位
G
B
rm GB
GB、
K
B
rm KB
KB、
B
rm B
B 前面的数字都为
0
0
0 ，所以不用输出。
样例
2
2
2，占用的空间为
4
×
2
+
8
×
2
+
10
+
8
×
100000
×
2
B
4×2 + 8×2 + 10 + 8×100000×2 mathrm B
4×2+8×2+10+8×100000×2 B，换算后是
1
M
B
538
K
B
546
B
1mathrm{MB}538mathrm{KB}546mathrm B
1MB538KB546B。
// 模拟题，没有写的价值。
试题 E: 斐波那契数组
2.
2.
2.
a
0
=
a
1
a_0 = a_1
a0=a1；
3.
3.
3. 对于所有的
i
(
i
≥
2
)
i(i≥2)
i(i≥2)，都满足
a
i
=
a
i
−
1
+
a
i
−
2
a_i = a_{i−1} + a_{i−2}
ai=ai−1+ai−2。5
1 2 2 4 8
3
将原数组修改为
(
1
,
1
,
2
,
3
,
5
)
(1,1,2,3,5)
(1,1,2,3,5)，最少修改三个元素变成了一个斐波那契数组。
G
2
=
g
F
2
G_2 = gF_2
G2=gF2
G
3
=
g
F
1
+
g
F
2
=
g
(
F
1
+
F
2
)
=
g
F
3
G_3 = gF_1 + gF_2 = g(F_1 + F_2) = gF_3
G3=gF1+gF2=g(F1+F2)=gF3
⋮
quad vdots
⋮
G
n
=
g
(
F
n
−
1
+
F
n
−
2
)
=
g
F
n
G_n = g(F_{n-1} + F_{n-2}) = gF_n
Gn=g(Fn−1+Fn−2)=gFnimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.TreeMap;
import java.util.Map;
public class Main {
public static void main(String[] args) { new Main().run(); }
double[] fib = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040 };
void run() {
Map
试题 F: 最大公约数
3
4 6 9
4
对于
50
%
50%
50% 的评测用例，
n
≤
5000
，
a
i
≤
1
0
6
n≤5000，a_i ≤10^6
n≤5000，ai≤106；
对于所有评测用例，
1
≤
n
≤
100000
，
1
≤
a
i
≤
1
0
9
1≤n≤100000，1≤a_i ≤10^9
1≤n≤100000，1≤ai≤109。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
public class Main {
public static void main(String[] args) { new Main().run(); }
int n, m = 0;
void run() {
build(1, 1, n = nextInt());
if (m > 0) System.out.print(n - m);
else {
m = n + 1;
for (int i = 1, j = 1; j <= n; ++j) {
while (i < j && gcd(i + 1, j) == 1) ++i;
if (gcd(i, j) == 1) m = Math.min(j - i, m);
}
System.out.print(m < n ? n + m - 1 : -1);
}
}
int[] gcd = new int[400096];
void build(int rt, int L, int R) {
if (L == R) {
gcd[rt] = nextInt();
if (gcd[rt] == 1) ++m;
} else {
build(rt << 1, L, L + R >> 1);
build(rt << 1 | 1, L + R + 2 >> 1, R);
gcd[rt] = calc(gcd[rt << 1], gcd[rt << 1 | 1]);
}
}
int gcd(int L, int R) { return queryGCD(1, 1, n, L, R); }
int queryGCD(int rt, int L, int R, int l, int r) {
if (L >= l && R <= r) return gcd[rt];
int mid = L + R >> 1, gcd = 0;
if (l <= mid)
gcd = queryGCD(rt << 1, L, mid, l, r);
if (r > mid)
if (gcd == 0) gcd = queryGCD(rt << 1 | 1, mid + 1, R, l, r);
else gcd = calc(gcd, queryGCD(rt << 1 | 1, mid + 1, R, l, r));
return gcd;
}
int calc(int a, int b) { return b == 0 ? a : calc(b, a % b); }
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int nextInt() {
try {
in.nextToken();
} catch (IOException e) {
e.printStackTrace();
}
return (int)in.nval;
}
}
试题 G: 交通信号
4 4 1 4
1 2 1 2 6
4 2 1 1 5
1 3 1 1 1
3 4 1 99 1
11
对于
70
%
70%
70% 的评测用例，
n
≤
5000
n≤5000
n≤5000；
对于所有评测用例，
1
≤
n
≤
100000
，
1
≤
m
≤
200000
，
1
≤
s
,
t
≤
n
，
1
≤
u
i
,
v
i
≤
n
，
1
≤
g
i
,
r
i
,
d
i
≤
1
0
9
1 ≤ n ≤ 100000，1 ≤ m ≤ 200000，1 ≤ s,t ≤ n，1≤u_i,v_i ≤n，1≤g_i,r_i,d_i ≤10^9
1≤n≤100000，1≤m≤200000，1≤s,t≤n，1≤ui,vi≤n，1≤gi,ri,di≤109。
// 挺没意思的，不想写了，被学校干厌学了
试题 H: 点亮
5
.....
.2.4.
..4..
.2.X.
.....
...O.
.2O4O
.O4O.
.2OX.
O....
答案对应的棋盘布局如下图所示
：
：
：
// BF可解，过
试题 I: 打折
2 2
1 2 89 1
1 97
3 4 77 1
2 15
101
对于
70
%
70%
70% 的评测用例，
n
,
m
≤
5000
，
Σ
c
i
≤
20000
n,m≤5000，Sigma c_i ≤20000
n,m≤5000，Σci≤20000；
对于所有评测用例，
1
≤
n
,
m
≤
100000
，
1
≤
c
i
≤
n
，
Σ
c
i
≤
400000
，
1
≤
s
i
≤
t
i
≤
1
0
9
，
1
<
p
i
<
100
，
1
≤
a
j
≤
n
，
1
≤
b
j
≤
1
0
9
1 ≤ n,m ≤ 100000，1 ≤ c_i ≤ n，Sigma c_i ≤ 400000，1 ≤ s_i ≤t_i ≤10^9，1 < p_i < 100，1≤a_j ≤n，1≤b_j ≤10^9
1≤n,m≤100000，1≤ci≤n，Σci≤400000，1≤si≤ti≤109，1
// 单调结构优化一下随便过
试题 J: 宝石收集
6
000111
6
0 1
1 2
3 1
2 3
2 4
2 5
2
