C/C++ 大学C组
- 试题 A: 斐波那契与 7
- 试题 B: 小蓝做实验
- 试题 C: 取模
- 试题 D: 内存空间
- 试题 E: 斐波那契数组
- 试题 F: 近似 GCD
- 试题 G: 数组个数
- 试题 H: 六六大顺
- 试题 I: 打折
- 试题 J: 替换字符
先挂题目，然后做 CB。
试题 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: 取模
时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.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 是否满足原命题。 时间限制:
1.0
s
1.0mathrm s
1.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.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。 时间限制:
1.0
s
1.0mathrm s
1.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.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 比值出现频率最高的项集，然后将其的补集替换为对应的 “广义斐波那契数列” 就行了。 时间限制:
1.0
s
1.0mathrm s
1.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.0MB 本题总分：
15
15
15 分 【问题描述】 小蓝有一个长度为
n
n
n 的数组
A
=
(
a
1
,
a
2
,
⋯
,
a
n
)
A = (a_1,a_2,cdots,a_n)
A=(a1,a2,⋯,an)，数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数组中所有元素的最大公约数。如果最多更改数组中的一个元素之后，数组的最大公约数为
g
g
g，那么称
g
g
g 为这个数组的近似
G
C
D
rm GCD
GCD。一个数组的近似
G
C
D
rm GCD
GCD 可能有多种取值。 具体的，判断
g
g
g 是否为一个子数组的近似
G
C
D
rm GCD
GCD 如下
：
：
：
1.
1.
1. 如果这个子数组的最大公约数就是
g
g
g，那么说明
g
g
g 是其近似
G
C
D
rm GCD
GCD。 小蓝想知道，数组
A
A
A 有多少个长度大于等于
2
2
2 的子数组满足近似
G
C
D
rm GCD
GCD 的值为
g
g
g。 【输入格式】 输入的第一行包含两个整数
n
,
g
n,g
n,g，用一个空格分隔，分别表示数组
A
A
A 的长度和
g
g
g 的值。 第二行包含
n
n
n 个整数
a
1
,
a
2
,
⋯
,
a
n
a_1,a_2,cdots,a_n
a1,a2,⋯,an，相邻两个整数之间用一个空格分隔。 【输出格式】 输出一行包含一个整数表示数组
A
A
A 有多少个长度大于等于
2
2
2 的子数组的近似
G
C
D
rm GCD
GCD 的值为
g
g
g。 【样例输入】 【样例输出】 【样例说明】 【评测用例规模与约定】 对于
20
%
20%
20% 的评测用例，
2
≤
n
≤
1
0
2
2≤n≤10^2
2≤n≤102； 时间限制:
1.0
s
1.0mathrm s
1.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.0MB 本题总分：
20
20
20 分 【问题描述】 小蓝有一个长度为
n
n
n 的数组
B
=
(
b
0
,
b
1
,
⋯
,
b
n
−
1
)
B = (b_0,b_1,cdots,b_{n−1})
B=(b0,b1,⋯,bn−1)，数组
B
B
B 是由另一个长度为
n
n
n 的环形数组
A
=
(
a
0
,
a
1
,
⋯
,
a
n
−
1
)
A = (a_0,a_1,cdots,a_{n−1})
A=(a0,a1,⋯,an−1) 经过一次相邻最大化操作得到的，其中
a
i
a_i
ai 与
a
i
+
1
a_{i+1}
ai+1 相邻，
a
0
a_0
a0 与
a
n
−
1
a_{n−1}
an−1 相邻。 形式化描述为
：
：
：
b
i
=
{
max
(
a
n
−
1
,
a
0
,
a
1
)
,
(
i
=
1
)
;
max
(
a
i
−
1
,
a
i
,
a
i
+
1
)
,
(
0
<
i
<
n
−
1
)
;
max
(
a
n
−
2
,
a
n
−
1
,
a
0
)
,
(
i
=
n
−
1
)
.
b_i=begin{cases}max(a_{n-1},a_0,a_1),&(i=1);\max(a_{i-1},a_i,a_{i+1}), & (0 【输入格式】 输入的第一行包含一个整数
n
n
n，表示数组长度。 第二行包含
n
n
n 个整数
b
0
,
b
1
,
⋯
,
b
n
−
1
b_0,b_1,cdots,b_{n−1}
b0,b1,⋯,bn−1，相邻两个整数之间用一个空格分隔。 【输出格式】 输出一行包含一个整数表示答案，答案可能很大，请输出答案除以
1000000007
1000000007
1000000007 后的余数。 【样例输入】 【样例输出】 【样例说明】 【评测用例规模与约定】 对于
30
%
30%
30% 的评测用例，
3
≤
n
≤
10
3≤n≤10
3≤n≤10； 时间限制:
1.0
s
1.0mathrm s
1.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.0MB 本题总分：
20
20
20 分 【问题描述】 六六大顺，本指农历六月初六。多用于祝福中年人士家庭幸福，工作顺利， 事业有成，身体健康。源自《左传》“君义，臣行，父慈，子孝，兄爱，弟敬， 此数者累谓六顺也。”
6
6
6 在我国自古以来是一个吉祥的数字，定义数列
A
=
(
a
1
,
a
2
,
⋯
,
a
i
,
⋯
)
A = (a_1,a_2,cdots,a_i,cdots)
A=(a1,a2,⋯,ai,⋯)，其中
a
1
=
6
,
a
2
=
66
,
⋯
,
a
i
=
10
⋅
a
i
−
1
+
6
a_1 = 6, a_2 = 66, cdots, a_i = 10cdot a_{i−1} + 6
a1=6,a2=66,⋯,ai=10⋅ai−1+6。 定义一个数列
B
=
(
b
1
,
b
2
,
⋯
,
b
i
,
⋯
)
B = (b_1,b_2,cdots,b_i,cdots)
B=(b1,b2,⋯,bi,⋯)，其中 $b_1 =
6
×
6
,
b
2
=
66
×
66
,
⋯
,
b
i
=
a
i
⋅
a
i
6×6, b_2 = 66×66, cdots, b_i = a_i cdot a_i
6×6,b2=66×66,⋯,bi=ai⋅ai。 现在小蓝想知道数列
B
B
B 的前
n
n
n 项的和是多少，你能帮帮小蓝吗？ 【输入格式】 输入一行包含一个正整数
n
n
n。 【输出格式】 输出一行包含一个整数表示数列
B
B
B 前
n
n
n 项的和。 【样例输入】 【样例输出】 【样例说明】 【评测用例规模与约定】 对于
20
%
20%
20% 的评测用例，
1
≤
n
≤
100
1≤n≤100
1≤n≤100； 时间限制:
2.0
s
2.0mathrm s
2.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.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； 时间限制:
1.0
s
1.0mathrm s
1.0s 内存限制:
256.0
M
B
256.0mathrm{MB}
256.0MB 本题总分：
25
25
25 分 【问题描述】 给定一个仅含小写英文字母的字符串
s
s
s，每次操作选择一个区间
[
l
i
,
r
i
]
[l_i,r_i]
[li,ri] 将
s
s
s 的该区间中的所有字母
x
i
x_i
xi 全部替换成字母
y
i
y_i
yi，问所有操作做完后，得到的字符串是什么。 【输入格式】 输入的第一行包含一个字符串
s
s
s。 第二行包含一个整数
m
m
m。 接下来
m
m
m 行，每行包含
4
4
4 个参数
l
i
,
r
i
,
x
i
,
y
i
l_i,r_i,x_i,y_i
li,ri,xi,yi，相邻两个参数之间用一个空格分隔，其中
l
i
,
r
i
l_i,r_i
li,ri 为整数，
x
i
,
y
i
x_i,y_i
xi,yi 为小写字母。 【输出格式】 输出一行包含一个字符串表示答案。 【样例输入】 【样例输出】 【评测用例规模与约定】 对于
40
%
40%
40% 的评测用例，
∣
s
∣
,
m
≤
5000
|s|,m≤5000
∣s∣,m≤5000；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: 近似 GCD
2.
2.
2. 在修改这个子数组中的一个元素之后（可以改成想要的任何值），子数组的最大公约数为
g
g
g，那么说明
g
g
g 是这个子数组的近似
G
C
D
rm GCD
GCD。5 3
1 3 6 4 10
5
满足条件的子数组有
5
5
5 个
：
：
：
[
1
,
3
]
[1,3]
[1,3]
：
：
：将
1
1
1 修改为
3
3
3 后，这个子数组的最大公约数为
3
3
3，满足条件。
[
1
,
3
,
6
]
[1,3,6]
[1,3,6]
：
：
：将
1
1
1 修改为
3
3
3 后，这个子数组的最大公约数为
3
3
3，满足条件。
[
3
,
6
]
[3,6]
[3,6]
：
：
：这个子数组的最大公约数就是
3
3
3，满足条件。
[
3
,
6
,
4
]
[3,6,4]
[3,6,4]
：
：
：将
4
4
4 修改为
3
3
3 后，这个子数组的最大公约数为
3
3
3，满足条件。
[
6
,
4
]
[6,4]
[6,4]
：
：
：将
4
4
4 修改为
3
3
3 后，这个子数组的最大公约数为
3
3
3，满足条件。
对于
40
%
40%
40% 的评测用例，
2
≤
n
≤
1
0
3
2≤n≤10^3
2≤n≤103；
对于所有评测用例，
2
≤
n
≤
1
0
5
，
1
≤
g
,
a
i
≤
1
0
9
2≤n≤10^5，1≤g,a_i ≤10^9
2≤n≤105，1≤g,ai≤109。
试题 G: 数组个数
5
8 6 1 8 8
7
可能的
A
A
A 数组有
7
7
7 个
：
：
：
(
6
,
0
,
0
,
1
,
8
)
(6,0,0,1,8)
(6,0,0,1,8)、
(
6
,
0
,
1
,
0
,
8
)
(6,0,1,0,8)
(6,0,1,0,8)、
(
6
,
0
,
1
,
1
,
8
)
(6,0,1,1,8)
(6,0,1,1,8)、
(
6
,
1
,
0
,
0
,
8
)
(6,1,0,0,8)
(6,1,0,0,8)、
(
6
,
1
,
0
,
1
,
8
)
(6,1,0,1,8)
(6,1,0,1,8)、
(
6
,
1
,
1
,
0
,
8
)
(6,1,1,0,8)
(6,1,1,0,8)、
(
6
,
1
,
1
,
1
,
8
)
(6,1,1,1,8)
(6,1,1,1,8)。
对于
60
%
60%
60% 的评测用例，
3
≤
n
≤
100
3≤n≤100
3≤n≤100；
对于所有评测用例，
3
≤
n
≤
1000
，
0
≤
b
i
≤
10
3≤n≤1000，0≤b_i ≤10
3≤n≤1000，0≤bi≤10。
试题 H: 六六大顺
3
447948
b
1
=
6
×
6
=
36
,
b
2
=
66
×
66
=
4356
,
b
3
=
666
×
666
=
443556
b_1 = 6×6 = 36,b_2 = 66×66 = 4356,b_3 = 666×666 = 443556
b1=6×6=36,b2=66×66=4356,b3=666×666=443556，所以前三项的和为
36
+
4356
+
443556
=
447948
36 + 4356 + 443556 = 447948
36+4356+443556=447948。
对于
50
%
50%
50% 的评测用例，
1
≤
n
≤
100000
1≤n≤100000
1≤n≤100000；
对于所有评测用例，
1
≤
n
≤
10000000
1≤n≤10000000
1≤n≤10000000。
试题 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: 替换字符
abcaaea
4
1 7 c e
3 3 e b
3 6 b e
1 4 a c
cbecaea
对于所有评测用例，
1
≤
∣
s
∣
,
m
≤
1
0
5
，
1
≤
l
i
≤
r
i
≤
∣
s
∣
，
x
i
,
≠
y
i
1 ≤|s|,m≤ 10^5，1 ≤l_i ≤r_i ≤|s|，x_i,neq y_i
1≤∣s∣,m≤105，1≤li≤ri≤∣s∣，xi,=yi，其中
∣
s
∣
|s|
∣s∣ 表示字符串
s
s
s 的长度。
