试题 G: 蜂巢
时间限制
: 1.0s
内存限制
: 512.0MB
本题总分：
20
分
【问题描述】
蜂巢由大量的六边形拼接而成，定义蜂巢中的方向为：
0
表示正西方向，
1
表示西偏北
60
◦
，
2
表示东偏北
60
◦
，
3
表示正东，
4
表示东偏南
60
◦
，
5
表示西
偏南
60
◦
。
对于给定的一点
O
，我们以
O
为原点定义坐标系，如果一个点
A
由
O
点
先向
d
方向走
p
步再向
(
d
+ 2)
mod
6
方向（
d
的顺时针
120
◦
方向）走
q
步到
达，则这个点的坐标定义为
(
d
,
p
,
q
)
。在蜂窝中，一个点的坐标可能有多种。
下图给出了点
B
(0
,
5
,
3)
和点
C
(2
,
3
,
2)
的示意。
给定点
(
d
1
,
p
1
,
q
1
)
和点
(
d
2
,
p
2
,
q
2
)
，请问他们之间最少走多少步可以到达？
【输入格式】
输入一行包含
6
个整数
d
1
,
p
1
,
q
1
,
d
2
,
p
2
,
q
2
表示两个点的坐标，相邻两个整
数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示两点之间最少走多少步可以到达。
【样例输入】
0 5 3 2 3 2
试题
G:
蜂巢
10
第十三届蓝桥杯大赛软件赛省赛
Python
大学
C
组
【样例输出】
7
【评测用例规模与约定】
对于
25
%
的评测用例，
p
1
,
p
2
≤
10
3
；
对于
50
%
的评测用例，
p
1
,
p
2
≤
10
5
；
对于
75
%
的评测用例，
p
1
,
p
2
≤
10
7
；
对于所有评测用例，
0
≤
d
1
,
d
2
≤
5
，
0
≤
q
1
<
p
1
≤
10
9
，
0
≤
q
2
<
p
2
≤
10
9
。
试题 H: 重新排序
时间限制
: 1.0s
内存限制
: 512.0MB
本题总分：
20
分
【问题描述】
给定一个数组
A
和一些查询
L
i
,
R
i
，求数组中第
L
i
至第
R
i
个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查
询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可
以增加多少
?
【输入格式】
输入第一行包含一个整数
n
。
第二行包含
n
个整数
A
1
,
A
2
,
· · ·
,
A
n
，相邻两个整数之间用一个空格分隔。
第三行包含一个整数
m
表示查询的数目。
接下来
m
行，每行包含两个整数
L
i
、
R
i
，相邻两个整数之间用一个空格分
隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5
1 2 3 4 5
2
1 3
2 5
【样例输出】
4
试题
H:
重新排序
12
第十三届蓝桥杯大赛软件赛省赛
Python
大学
C
组
【样例说明】
原来的和为
6 + 14 = 20
，重新排列为
(1
,
4
,
5
,
2
,
3)
后和为
10 + 14 = 24
，增
加了
4
。
【评测用例规模与约定】
对于
30
%
的评测用例，
n
,
m
≤
50
；
对于
50
%
的评测用例，
n
,
m
≤
500
；
对于
70
%
的评测用例，
n
,
m
≤
5000
；
对于所有评测用例，
1
≤
n
,
m
≤
10
5
，
1
≤
A
i
≤
10
6
，
1
≤
L
i
≤
R
i
≤
10
6
。
试题 I: 青蛙过河
时间限制
: 1.0s
内存限制
: 512.0MB
本题总分：
25
分
【问题描述】
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里
的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。
不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就
会下降
1
，当石头的高度下降到
0
时小青蛙不能再跳到这块石头上（某次跳跃
后使石头高度下降到
0
是允许的）。
小青蛙一共需要去学校上
x
天课，所以它需要往返
2
x
次。当小青蛙具有
一个跳跃能力
y
时，它能跳不超过
y
的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完
x
次课。
【输入格式】
输入的第一行包含两个整数
n
,
x
，分别表示河的宽度和小青蛙需要去学校
的天数。请注意
2
x
才是实际过河的次数。
第二行包含
n
−
1
个非负整数
H
1
,
H
2
,
· · ·
,
H
n
−
1
，其中
H
i
>
0
表示在河中与
小青蛙的家相距
i
的地方有一块高度为
H
i
的石头，
H
i
= 0
表示这个位置没有石
头。
【输出格式】
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
【样例输入】
5 1
1 0 1 0
试题
I:
青蛙过河
14
第十三届蓝桥杯大赛软件赛省赛
Python
大学
C
组
【样例输出】
4
【样例解释】
由于只有两块高度为
1
的石头，所以往返只能各用一块。第
1
块石头和对
岸的距离为
4
，如果小青蛙的跳跃能力为
3
则无法满足要求。所以小青蛙最少
需要
4
的跳跃能力。
【评测用例规模与约定】
对于
30
%
的评测用例，
n
≤
100
；
对于
60
%
的评测用例，
n
≤
1000
；
对于所有评测用例，1
≤
n
≤
10
5
,
1
≤
x
≤
10
9
,
1
≤
H
i
≤
10
4
。\
试题 J: 因数平方和
时间限制
: 1.0s
内存限制
: 512.0MB
本题总分：
25
分
【问题描述】
记
f
(
x
)
为
x
的所有因数的平方的和。例如：
f
(12) = 1
2
+ 2
2
+ 3
2
+ 4
2
+ 6
2
+
12
2
。
定义
g
(
n
) =
∑
n
i
=1
f
(
i
)
。给定
n
,
求
g
(
n
)
除以
10
9
+ 7
的余数。
【输入格式】
输入一行包含一个正整数
n
。
【输出格式】
输出一个整数表示答案
g
(
n
)
除以
10
9
+ 7
的余数。
【样例输入】
100000
【样例输出】
394827960
【评测用例规模与约定】
对于
20
%
的评测用例，
n
≤
10
5
。
对于
30
%
的评测用例，
n
≤
10
7
。
对于所有评测用例，
1
≤
n
≤
10
9
。
