PDF《NOIP 模拟题》

0 ≤ ai <

1, 000, 000, 007. 接下来 m 行,每行描述一个操作.操作一定以下列之一的形式给出: ?

1 l r d,表示区间加,保证

1 ≤ l ≤ r ≤ n,0 ≤ d <

1, 000, 000, 007. ?

2 l r,表示区间询问二阶和,保证

1 ≤ l ≤ r ≤ n. 【输出格式】 输出到文件 sumsum.out 中. 对于每个区间询问二阶和,输出一行一个整数,表示所询问的二阶和除以 1, 000, 000,

007 的余数. 第4页共8页NOIP 模拟题 第13 套 二阶和(sumsum) 【样例

1 输入】

10 10

62 95

16 57

28 17

90 76

1 18

2 3

5 1

3 8

59 2

4 7

1 3

6 0

1 1

10 62

2 1

8 1

1 8

91 1

1 6

33 2

3 10

1 4

9 46 【样例

1 输出】

190 1026

5432 9428 【样例

1 解释】 每次操作的中间结果如下: 1. {a3,a5} = {16, 57, 28}, {sl,sr} = {16, 73, 101}. 2. {ai} = {62, 95, 75, 116, 87, 76, 149, 135, 1, 18}. 3. {a4,a7} = {116, 87, 76, 149}, {sl,sr} = {116, 203, 279, 428}. 4. {ai} = {62, 95, 75, 116, 87, 76, 149, 135, 1, 18}. 5. {ai} = {124, 157, 137, 178, 149, 138, 211, 197, 63, 80}. 6. {a1,a8} = {124, 157, 137, 178, 149, 138, 211, 197}, {sl,sr} = {124, 281, 418, 596, 745, 883, 1094, 1291}. 7. {ai} = {215, 248, 228, 269, 240, 229, 302, 288, 63, 80}. 8. {ai} = {248, 281, 261, 302, 273, 262, 302, 288, 63, 80}. 9. {a3,a10} = {261, 302, 273, 262, 302, 288, 63, 80}, {sl,sr} = {261, 563, 836, 1098, 1400, 1688, 1751, 1831}. 第5页共8页NOIP 模拟题 第13 套 二阶和(sumsum) 10. {ai} = {248, 281, 261, 348, 319, 308, 348, 334, 109, 80}. 【样例 2】 见选手目录下的 sumsum/sumsum2.in 与sumsum/sumsum2.ans. 【子任务】 各组测试数据的规模如下 测试点 n = m =

1 30

2 300

3 103

4 3,

000 5 5,

000 6

105 7

2 *

105 8

3 *

105 9

4 *

105 10

5 *

105 第6页共8页NOIP 模拟题 第13 套 合人问题(merge) 合人问题(merge) 【题目描述】 众所周知,小葱同学擅长合并,尤其把两个人合并成一个人.但小葱只擅长合并两 个人的情况,当有很多个人之后就会比较苦恼.现在小葱给了你 n 个人排成一个环(即 第一个人和最后一个人相邻) ,并且每个人左手和右手上各有一个数.每次你可以合并 相邻的两个人,合并这两个人的代价为他们右手的数的差的绝对值,合并之后会变成一 个新的人,新的人左手的数是原来左边的人左手的数,右手的数是原来右边的人右手的 数.现在小葱希望你通过 n ?

1 次合并把所有人合并成一个人,并且使得代价最小.求 最小代价. 【输入格式】 从文件 merge.in 中读入数据. 第........