第十四届蓝桥杯省赛真题 Java B 组【原卷】

小鱼儿 2024-04-06 15:40 91阅读 0赞

#### 文章目录 ####

*  发现宝藏
 *  【考生须知】
 *  试题 A: 阶乘求和
 *  试题 B: 幸运数字
 *  试题 C: 数组分割
 *  试题 D: 矩形总面积
 *  试题 E: 蜗牛
 *  试题 F: 合并区域
 *  试题  G : \\mathrm\{G\}: G: 买二赠一
 *  试题  H \\mathrm\{H\} H : 合并石子
 *  试题 I：最大开支
 *  试题  J : \\mathrm\{J\}: J: 魔法阵

## 发现宝藏 ##

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【[宝藏入口][Link 1]】。

--------------------

第十四届蓝桥杯大赛软件赛省赛 Java 大学 B 组

## 【考生须知】 ##

考试开始后, 选手首先下戟题日, 并使用考场现场公布的解压密码解压试题。

考试时间为 4 小时。考试期间选手可浏览白已已经提交的答案, 被浏览的答案允许拷贝。时间截止后, 将无法继续提交或浏览答案。

对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。

试题包含“结果填空”和“程序设计”两种题型。

结果填空题: 要求选于根据题日描述直接填写结果。求解方式不限。不要求源代码。把结果媜空的答案直接通过网页提交即可, 不要书写多余的内容。

程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。

注意: 在评炎时使用的输入数据与试炎中给出的示例数据可能是不同的。迅手的程序必须是通用的, 不能只对试卷中给定的数据有效。

所有源码必须在同一文件中。调试通过后，拷贝提交.

注意: 不要使用 package 语句。

注意: 选手代码的主类名必须为: Main, 否则会被判为无效代码。

注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。

--------------------

## 试题 A: 阶乘求和 ##

本题总分: 5 分

**【问题描述】**

令  S = 1 ! + 2 ! + 3 ! + … + 202320232023 ! S=1 !+2 !+3 !+\\ldots+202320232023 ! S=1!\+2!\+3!\+…\+202320232023!, 求  S S S 的末尾 9 位数字。

提示: 答案首位不为 0 。

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一

个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

--------------------

## 试题 B: 幸运数字 ##

本题总分: 5 分

**【问题描述】**

哈沙德数是指在某个周定的进位制当中, 可以被各位数字之和整除的正整数。例如 126是十进制下的一个哈沙德数, 因为  ( 126 ) 10   m o d   ( 1 + 2 + 6 ) = 0 ; 126 (126)\_\{10\} \\bmod (1+2+6)=0 ; 126 (126)10mod(1\+2\+6)=0;126也是八进制下的哈沙德数, 因为  ( 126 ) 10 = ( 176 ) 8 , ( 126 ) 10   m o d   ( 1 + 7 + 6 ) = 0 (126)\_\{10\}=(176)\_\{8\},(126)\_\{10\} \\bmod (1+7+6)=0 (126)10=(176)8,(126)10mod(1\+7\+6)=0;同时 126 也是 16 进制下的哈沙德数, 因为  ( 126 ) 10 = ( 7 e ) 16 , ( 126 ) 10   m o d   ( 7 + (126)\_\{10\}=(7 e)\_\{16\},(126)\_\{10\} \\bmod (7+ (126)10=(7e)16,(126)10mod(7\+  e ) = 0 e)=0 e)=0 。小蓝认为, 如果一个整数在二进制、八进制、 1 进制、十六进制下均为哈沙德数, 那么这个数字就足幸运数字, 第 1 至第 10 个幸运数字的 1 进制表示为:  1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 … 1,2,4,6,8,40,48,72,120,126 \\ldots 1,2,4,6,8,40,48,72,120,126…. 现在他照知道第 2023 个幸运数字是多少? 你只需要告诉小蓝这个整数的十进制表示即可。

**【答案提交】**

这足一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

--------------------

## 试题 C: 数组分割 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 10 分

**【问题描述】**

小蓝有一个长度为  N N N 的数组  A = \[ A 0 , A 1 , … , A N − 1 \] A=\\left\[A\_\{0\}, A\_\{1\}, \\ldots, A\_\{N-1\}\\right\] A=\[A0,A1,…,AN−1\] 。现在小蓝想要从  A A A 对应的数组下标所构成的集合  I = \{ 0 , 1 , 2 , … , N − 1 \} I=\\\{0,1,2, \\ldots, N-1\\\} I=\{ 0,1,2,…,N−1\} 中找出一个子集  R 1 R\_\{1\} R1, 那么  R 1 R\_\{1\} R1在  I I I 中的补集为  R 2 R\_\{2\} R2 。记  S 1 = ∑ r ∈ R 1 A r , S 2 = ∑ r ∈ R 2 A r S\_\{1\}=\\sum\_\{r \\in R\_\{1\}\} A\_\{r\}, S\_\{2\}=\\sum\_\{r \\in R\_\{2\}\} A\_\{r\} S1=∑r∈R1Ar,S2=∑r∈R2Ar, 我们要求  S 1 S\_\{1\} S1 和  S 2 S\_\{2\} S2 均为偶数, 请问在这种情况下共有多少种不同的  R 1 R\_\{1\} R1 。当  R 1 R\_\{1\} R1 或  R 2 R\_\{2\} R2 为空集时我们将  S 1 S\_\{1\} S1 或  S 2 S\_\{2\} S2 视为 0 。

**【输入格式】**

第一行一个整数  T T T, 表示有  T T T 组数据。

接下来输入  T T T 组数据, 每组数据包含两行: 第一行一个整数  N N N, 表示数组  A A A 的长度; 第二行输入  N N N 个整数从全至有依次为  A 0 , A 1 , … , A N − 1 A\_\{0\}, A\_\{1\}, \\ldots, A\_\{N-1\} A0,A1,…,AN−1, 相邻元素之间用空格分隔。

**【输出格式】**

对于每组数据, 输出一行, 包含一个整数表示答案, 答案可能会很大, 你需要将答案对 1000000007 进行取模后输出。

**【样例输入】**

2 \\begin\{array\}\{lll\}2\\end\{array\} 2  
 2 \\begin\{array\}\{lll\}2\\end\{array\} 2  
 6 6 \\begin\{array\}\{lll\}6&6\\end\{array\} 66  
 2 \\begin\{array\}\{lll\}2\\end\{array\} 2  
 1 6 \\begin\{array\}\{lll\}1&6\\end\{array\} 16

**【样例输出】**

4 \\begin\{array\}\{lll\}4\\end\{array\} 4  
 0 \\begin\{array\}\{lll\}0\\end\{array\} 0

**【样例说明】**

对于第一组数据, 答案为 4 。(注意: 大括号内的数字表示元素在数组中的下标。

R 1 = \{ 0 \} , R 2 = \{ 1 \} R\_\{1\}=\\\{0\\\}, R\_\{2\}=\\\{1\\\} R1=\{ 0\},R2=\{ 1\}; 此时  S 1 = A 0 = 6 S\_\{1\}=A\_\{0\}=6 S1=A0=6 为偶数,  S 2 = A 1 = 6 S\_\{2\}=A\_\{1\}=6 S2=A1=6 为偶数。

R 1 = \{ 1 \} , R 2 = \{ 0 \} R\_\{1\}=\\\{1\\\}, R\_\{2\}=\\\{0\\\} R1=\{ 1\},R2=\{ 0\}; 此时  S 1 = A 1 = 6 S\_\{1\}=A\_\{1\}=6 S1=A1=6 为偶数,  S 2 = A 0 = 6 S\_\{2\}=A\_\{0\}=6 S2=A0=6 为偶数。

R 1 = \{ 0 , 1 \} , R 2 = \{ \} ; R\_\{1\}=\\\{0,1\\\}, R\_\{2\}=\\\{\\\} ; R1=\{ 0,1\},R2=\{ \}; 此时  S 1 = A 0 + A 1 = 12 S\_\{1\}=A\_\{0\}+A\_\{1\}=12 S1=A0\+A1=12 为偶数,  S 2 = 0 S\_\{2\}=0 S2=0 为偶数。

R 1 = \{ \} , R 2 = \{ 0 , 1 \} : R\_\{1\}=\\\{\\\}, R\_\{2\}=\\\{0,1\\\}: R1=\{ \},R2=\{ 0,1\}: 此时  S 1 = 0 S\_\{1\}=0 S1=0 为偶数,  S 2 = A 0 + A 1 = 12 S\_\{2\}=A\_\{0\}+A\_\{1\}=12 S2=A0\+A1=12 为偶数。

对于第二组数据, 无论怎么选择, 都不满足条件, 所以答案为 0 。

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的评测用例,  1 ≤ N ≤ 10 1 \\leq N \\leq 10 1≤N≤10 。

对于  40 % 40 \\% 40% 的评测用例,  1 ≤ N ≤ 1 0 2 1 \\leq N \\leq 10^\{2\} 1≤N≤102 。

对于  100 % 100 \\% 100% 的评测用例,  1 ≤ T ≤ 10 , 1 ≤ N ≤ 1 0 3 , 0 ≤ A i ≤ 1 0 9 1 \\leq T \\leq 10,1 \\leq N \\leq 10^\{3\}, 0 \\leq A\_\{i\} \\leq 10^\{9\} 1≤T≤10,1≤N≤103,0≤Ai≤109 。

--------------------

## 试题 D: 矩形总面积 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 10 分

**【问题描述】**

平面上有个两个矩形  R 1 R\_\{1\} R1 和  R 2 R\_\{2\} R2, 它们各边都与坐标轴平行。设  ( x 1 , y 1 ) \\left(x\_\{1\}, y\_\{1\}\\right) (x1,y1) 和  ( x 2 , y 2 ) \\left(x\_\{2\}, y\_\{2\}\\right) (x2,y2) 依次定  R 1 R\_\{1\} R1 的左下角和右上角坐标,  ( x 3 , y 3 ) \\left(x\_\{3\}, y\_\{3\}\\right) (x3,y3) 和  ( x 4 , y 4 ) \\left(x\_\{4\}, y\_\{4\}\\right) (x4,y4) 依次定  R 2 R\_\{2\} R2 的左下角和右上角坐标, 请你计算  R 1 R\_\{1\} R1 和  R 2 R\_\{2\} R2 的总面积是多少?

注意：如果  R 1 R\_\{1\} R1 和  R 2 R\_\{2\} R2 有重叠区域, 重叠区域的面积只计算一次。

**【输入格式】**

输入只有一行, 包含 8 个整数, 依次定:  x 1 , y 1 , x 2 , y 2 , x 3 , y 3 , x 4 x\_\{1\}, y\_\{1\}, x\_\{2\}, y\_\{2\}, x\_\{3\}, y\_\{3\}, x\_\{4\} x1,y1,x2,y2,x3,y3,x4 和  y 4 y\_\{4\} y4 。

**【输出格式】**

个整数, 代表答案。

**【样例输入】**

2 1 7 4 5 3 8 6 \\begin\{array\}\{llllllll\}2 & 1 & 7 & 4 & 5 & 3 & 8 & 6\\end\{array\} 21745386

**【样例输出】**

22 \\begin\{array\}\{lll\}22\\end\{array\} 22

**【样例说明】**

样例中的两个矩形如图所示:

![在这里插入图片描述][42f0ce8335fc4d1391c8e1130c4dd075.png]

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的数据,  R 1 R\_\{1\} R1 和  R 2 R\_\{2\} R2 没有重叠区域。

对于  20 % 20 \\% 20% 的数据, 其中一个矩形完全在另一个矩形内部。

对于  50 % 50 \\% 50% 的数据, 所有坐标的取值范围是  \[ 0 , 1 0 3 \] \\left\[0,10^\{3\}\\right\] \[0,103\] 。

对于  100 % 100 \\% 100% 的数据, 所有坐标的取值范围足  \[ 0 , 1 0 5 \] \\left\[0,10^\{5\}\\right\] \[0,105\] 。

--------------------

## 试题 E: 蜗牛 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 15 分

**【问题描述】**

这天, 一只蜗牛来到了二维坐标系的原点。

在  x x x 轴上长有  n n n 根竹䇢。它们平行于  y y y 轴, 底部纵坐标为 0 , 横坐标分别为  x 1 , x 2 , … , x n x\_\{1\}, x\_\{2\}, \\ldots, x\_\{n\} x1,x2,…,xn 。竹竿的高度均为无限高, 宽度可忽略。蜗牛想要从原点走到第  n n n 个竹篎的底部也就足坐标  ( x n , 0 ) \\left(x\_\{n\}, 0\\right) (xn,0) 。它只能在  x x x 轴上或者竹竿上爬行, 在  x x x 轴上爬行速度为 1 单位每秒; 由于受到引力影响, 蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。

为了快速到达目的地, 它施展了悗法, 在第  i i i 和  i + 1 i+1 i\+1 根竹等之间建立了传送门  ( 0 < i < n ) (0<i<n) (0<i<n), 如果蜗牛位于第  i i i 根竹竿的高度为  a i a\_\{i\} ai 的位置  ( x i , a i ) \\left(x\_\{i\}, a\_\{i\}\\right) (xi,ai), 就可以瞬间到达第  i + 1 i+1 i\+1 根竹竿的高度为  b i + 1 b\_\{i+1\} bi\+1 的位置  ( x i + 1 , b i + 1 ) \\left(x\_\{i+1\}, b\_\{i+1\}\\right) (xi\+1,bi\+1), 请计算蜗牛最少需要多少秒才能到巡目的地。

**【输入格式】**

输入共  1 + n 1+n 1\+n 行, 第一行为一个正整数  n n n;

第二行为  n n n 个正整数  x 1 , x 2 , … , x n x\_\{1\}, x\_\{2\}, \\ldots, x\_\{n\} x1,x2,…,xn;

后面  n − 1 n-1 n−1 行, 每行两个正整数  a i , b i + 1 a\_\{i\}, b\_\{i+1\} ai,bi\+1 。

**【输出格式】**

输出共一行, 一个浮点数表示答案 (四舍五入保留两位小数)。

**【样例输入】**

3 \\begin\{array\}\{lll\}3\\end\{array\} 3

1 10 11 \\begin\{array\}\{lll\}1 & 10 & 11\\end\{array\} 11011

1 1 \\begin\{array\}\{lll\}1 & 1\\end\{array\} 11

2 1 \\begin\{array\}\{lll\}2 & 1\\end\{array\} 21

**【样例输出】**

4.20 \\begin\{array\}\{lll\}4.20\\end\{array\} 4.20

**【样例说明】**

蜗牛路线:

( 0 , 0 ) → ( 1 , 0 ) → ( 1 , 1 ) → ( 10 , 1 ) → ( 10 , 0 ) → ( 11 , 0 ) (0,0) \\rightarrow(1,0) \\rightarrow(1,1) \\rightarrow(10,1) \\rightarrow(10,0) \\rightarrow(11,0) (0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0), 花费时间为  1 + 1 0.7 + 1+\\frac\{1\}\{0.7\}+ 1\+0.71\+  0 + 1 1.3 + 1 ≈ 4.20 0+\\frac\{1\}\{1.3\}+1 \\approx 4.20 0\+1.31\+1≈4.20

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的数据, 保证  n ≤ 15 n \\leq 15 n≤15;

对于  100 % 100 \\% 100% 的数据, 保证  n ≤ 1 0 5 , a i , b i ≤ 1 0 4 , x i ≤ 1 0 9 n \\leq 10^\{5\}, a\_\{i\}, b\_\{i\} \\leq 10^\{4\}, x\_\{i\} \\leq 10^\{9\} n≤105,ai,bi≤104,xi≤109 。

--------------------

## 试题 F: 合并区域 ##

时间限制:  2.0 s 2.0 \\mathrm\{~s\} 2.0s 内存限制: 512.0MB 本题总分: 15 分

**【问题描述】**

小蓝在玩一款种地游戏。现在他被分配给了两块大小均为  N × N N \\times N N×N 的正方形区域。这两块区域都按照  N × N N \\times N N×N 的规格进行了均等划分, 划分成了若干块面积相同的小区域, 其中每块小区域要么足岩石, 要么就足土壤, 在垂直或者水平方问上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进行合并, 他想知道合并以后可以得到的最大的一块土地的面积定多少 (土地的面积就足土地中土增小区域的块数)？

在进行合并时, 小区域之间必须对齐。可以在两块方形区域的任何一条边上进行合并, 可以对两块方形区域进行 90 度、 180 度、 270 度、 360 度的旋转,但不可以进行上下或左右翻转, 并月.两块方形区域不㕽以发牛重叠。

**【输入格式】**

第一行一个整数  N N N 表示区域大小。

接下来  N N N 行表示第一块区域, 每行  N N N 个值为 0 或 1 的整数, 相邻的整数之间用空格进行分隔。值为 0 表示这块小区域是岩石, 值为 1 表示这块小区域是土壤。

再接下来  N N N 行表示第二块区域, 每行  N N N 个值为 0 或 1 的整数, 相邻的整数之间用空格进行分隔。值为 0 表示这块小区域是岩石, 值为 1 表示这块小区域是土壤。

**【输出格式】**

一个整数表示将两块区域合并之后可以产生的最大的土地面积。

**【样例输入】**

4 \\begin\{array\}\{llll\}4\\end\{array\} 4

0 1 1 0 \\begin\{array\}\{llll\}0 & 1 & 1 & 0\\end\{array\} 0110

1 0 1 1 \\begin\{array\}\{llll\}1 & 0 & 1 & 1\\end\{array\} 1011

1 0 1 0 \\begin\{array\}\{llll\}1 & 0 & 1 & 0\\end\{array\} 1010

1 1 1 0 \\begin\{array\}\{llll\}1 & 1 & 1 & 0\\end\{array\} 1110

0 0 1 0 \\begin\{array\}\{llll\}0 & 0 & 1 & 0\\end\{array\} 0010

0 1 1 0 \\begin\{array\}\{llll\}0 & 1 & 1 & 0\\end\{array\} 0110

1 0 0 0 \\begin\{array\}\{llll\}1 & 0 & 0 & 0\\end\{array\} 1000

1 1 1 1 \\begin\{array\}\{llll\}1 & 1 & 1 & 1\\end\{array\} 1111

**【样例输出】**

15 \\begin\{array\}\{llll\}15\\end\{array\} 15

**【样例说明】**  
![在这里插入图片描述][b1779a11b36840a4b5d0415c9a96a3ce.png]

第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳的合并方式, 此时最大的土地面积为 15 。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的数据，  1 ≤ N ≤ 5 1 \\leq N \\leq 5 1≤N≤5 。

对于  60 % 60 \\% 60% 的数据,  1 ≤ N ≤ 15 1 \\leq N \\leq 15 1≤N≤15 。

对于  100 % 100 \\% 100% 的数据,  1 ≤ N ≤ 50 1 \\leq N \\leq 50 1≤N≤50 。

--------------------

## 试题  G : \\mathrm\{G\}: G: 买二赠一 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 20 分

**【问题描述】**

某商场有  N N N 件商品, 其中第  i i i 件的价格是  A i A\_\{i\} Ai 。现在该商场正在进行 “买二赠一” 的优惠活动, 具体规则是:

每购买 2 件商品, 假设其中较便宜的价格足  P P P (如果两件商品价格一样,则  P P P 等于其中一件商品的价格), 就可以从剩余商品中任选一件价格不超过  P 2 \\frac\{P\}\{2\} 2P的商品, 免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品, 但是每件商品只能被购买或免费获得一次。

小朋想知道如果要拿下所有商品 (包含购买和免费狄得), 至少要化费多少钱?

**【输入格式】**

第一行包含一个整数  N N N 。

第二行包含  N N N 个整数, 他表  A 1 , A 2 , A 3 , … , A N A\_\{1\}, A\_\{2\}, A\_\{3\}, \\ldots, A\_\{N\} A1,A2,A3,…,AN 。

**【输出格式】**

输出一个整数, 代表答案。

【样例输入】

7 \\begin\{array\}\{lllllll\} 7\\end\{array\} 7

1 4 2 8 5 7 1 \\begin\{array\}\{lllllll\}1 & 4 & 2 & 8 & 5 & 7 & 1\\end\{array\} 1428571

**【样例输出】**

25 \\begin\{array\}\{lllllll\}25\\end\{array\} 25

**【样例说明】**

小明可以先购买价格 4 和 8 的商品, 免费获得一件价格为 1 的商品; 再后买价格为 5 和 7 的商品, 免费获得价格为 2 的商品; 最后单独购买剩下的一件价格为 1 的商品。总计花费  4 + 8 + 5 + 7 + 1 = 25 4+8+5+7+1=25 4\+8\+5\+7\+1=25 。不存在花费更低的方案。

【评测用例规模与约定】

对于  30 % 30 \\% 30% 的数据,  1 ≤ N ≤ 20 1 \\leq N \\leq 20 1≤N≤20 。

对于  100 % 100 \\% 100% 的数据,  1 ≤ N ≤ 5 × 1 0 5 , 1 ≤ A i ≤ 1 0 9 1 \\leq N \\leq 5 \\times 10^\{5\}, 1 \\leq A\_\{i\} \\leq 10^\{9\} 1≤N≤5×105,1≤Ai≤109 。

--------------------

## 试题  H \\mathrm\{H\} H : 合并石子 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 20 分

**【问题描述】**

在染面从左至右横向摆放着  N N N 堆石子。每一堆石子都有着相同的商色, 颜色可能是颜色 0 , 颜色 1 或者颜色 2 中的其中一种。

现在要对石了进行合并, 规定每次只能选择位真相邻并且.颜色相同的两堆石了进行合并。合并后新堆的相对位置保持不变, 新堆的石了数目为所选择的两堆石子数日之和, 并且新堆石子的颜色也会发生循环式的变化。具休来说:两堆颜色 0 的石子合并后的石子堆为颜色 1 , 两堆颜色 1 的石子合并后的石子堆为颜色 2 , 两堆颜色 2 的石子合并后的石子堆为颜色 0 。木次合并的花费为所选择的两堆石子的数日之和。

掵出  N N N 堆石子以及他们的初始颜色, 请问最少可以将它们合并为多少堆石子? 如果有多种營案, 选择其中合并总花费最小的一种, 合并总花费指的足在所有的合并操作山, 产牛的合并优费的总和。

**【输入格式】**

第一行一个正整数  N N N 表示石了堆数。

第二行包含  N N N 个用空格分隔的正整数, 表示从左至右每一堆石子的数目。

第二行包含  N N N 个值为 0 或 1 或 2 的整数表示每堆石头的颜色。

**【输出格式】**

一行包含两个整数, 用空格分隔。其中第一个整数表示合并后数目最少的石头堆数, 第二个整数表示对应的最小优费。

**【样例输入】**

5 \\begin\{array\}\{llllll\}5\\end\{array\} 5

5 10 1 8 6 \\begin\{array\}\{llllll\}5& 10 & 1 & 8 & 6\\end\{array\} 510186

1 1 0 2 2 \\begin\{array\}\{llllll\}1 & 1 & 0 & 2 & 2\\end\{array\} 11022

**【样例输出】**

2 44 \\begin\{array\}\{llllll\}2 & 44\\end\{array\} 244

**【样例说明】**

![在这里插入图片描述][12e94648df08478592fdae9c4dc605bc.png]

上图亚示了两种不同的合并方式。其山节点山标朋了每一堆的石了数目,在方括号山标注了当前堆石了的颜色属性。在图的这种合并方式坟终剩下了两堆石了, 所, 生的合并总化费为  15 + 14 + 15 = 44 15+14+15=44 15\+14\+15=44; 右图的这种合并方式最终也剩下了两堆石了, 但, 生的合并总化费为  14 + 15 + 25 = 54 14+15+25=54 14\+15\+25=54 。综上所述, 我们选择合并花费为 44 的这种方式作为答案。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例,  1 ≤ N ≤ 10 1 \\leq N \\leq 10 1≤N≤10 。

对于  50 % 50 \\% 50% 的评测用例,  1 ≤ N ≤ 50 1 \\leq N \\leq 50 1≤N≤50 。

对于  100 % 100 \\% 100% 的评测用例,  1 ≤ N ≤ 300 , 1 ≤ 1 \\leq N \\leq 300,1 \\leq 1≤N≤300,1≤ 每堆石子的数目  ≤ 1000 \\leq 1000 ≤1000 。

--------------------

## 试题 I：最大开支 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 25 分

**【问题描述】**

小蓝所在学校周边新开业了一家游乐园, 小蓝作为班长, 打算组织大家去游乐园玩。已知一共有  N N N 个人参加这次活动, 游乐园有  M M M 个娱乐项目, 每个项目都需要买门票后才可进去游玩。门票的价格并不足周定的, 团则的人越多单价越便宣, 当团钊的人数大于某个阇值时, 这些团钊的人便可以免费进入项日进行游玩。这  M M M 个娱乐项日足独立的, 所以只有选择了同一个项目的人才可以参与这个项日的团购。第  i i i 个项目的门票价格  H i H\_\{i\} Hi 与团则的人数  X X X 的关系可以看作定一个函数:

H i ( X ) = max ⁡ ( K i × X + B i , 0 ) H\_\{i\}(X)=\\max \\left(K\_\{i\} \\times X+B\_\{i\}, 0\\right) Hi(X)=max(Ki×X\+Bi,0)

max ⁡ \\max max 表示取二者之山的最大值。当  H i = 0 H\_\{i\}=0 Hi=0 时说朋可购人数达到了此项目的免单划值

这  N N N 个人可以根据白已的喜好选择  M M M 个娱乐项日中的一种, 或者有些人对这些娱乐项日都没有兴趣, 也可以选择不去任何一个项日。每个人最多只会选择一个娱乐项日, 如果多个人选择了同一个娱乐项日, 那么他们都将享受对应的团购价格。小䍀想知道他至少需要准各多少钱, 使得无论大家如何选择,他都有能力文付得起所有  N N N 个人则买娱乐项目的门票钱。

**【输入格式】**

第一行两个整数  N 、 M N 、 M N、M, 分別表示参加活动的人数和娱乐项目的个数。

接下来  M M M 行, 每行两个整数, 其中第  i i i 行为  K i 、 B i K\_\{i\} 、 B\_\{i\} Ki、Bi, 表示第  i \\mathrm\{i\} i 个游乐地点的门票函数中的参数。

**【输出格式】**

一个整数, 表示小蓝至少需要准备多少钱, 使得大家无论如何选择项目,自己都支付得起。

**【样例输入】**

4 2 \\begin\{array\}\{ll\}4 & 2\\end\{array\} 42

− 4 10 \\begin\{array\}\{ll\}-4 & 10\\end\{array\} −410

− 2 7 \\begin\{array\}\{ll\}-2 &7\\end\{array\} −27

**【样例输出】**

12 \\begin\{array\}\{ll\}12\\end\{array\} 12

**【样例说明】**

样例中有 4 个人, 2 个娱乐项目, 我们用一个二元组  ( a , b ) (a, b) (a,b) 表示  a a a 个人选择了第一个娱乐项目,  b b b 个人选择了第二个娱乐项目, 那么就有  4 − a − b 4-a-b 4−a−b 个人没有选择任何项日, 方案  ( a , b ) (a, b) (a,b) 对应的门票花费为  max ⁡ ( − 4 × a + 10 , 0 ) × a + \\max (-4 \\times a+10,0) \\times a+ max(−4×a\+10,0)×a\+  max ⁡ ( − 2 × b + 7 , 0 ) × b \\max (-2 \\times b+7,0) \\times b max(−2×b\+7,0)×b, 所有的可能如下所示:

<table> 
 <thead> 
  <tr> 
   <th align="center"><span><span><span> a \mathbf{a} </span><span><span><span style="height: 0.4444em;"></span><span>a</span></span></span></span></span></th> 
   <th align="center"><span><span><span> b \mathbf{b} </span><span><span><span style="height: 0.6944em;"></span><span>b</span></span></span></span></span></th> 
   <th align="center">花费</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">0</td> 
   <td align="center">0</td> 
   <td align="center">0</td> 
  </tr> 
  <tr> 
   <td align="center">0</td> 
   <td align="center">1</td> 
   <td align="center">5</td> 
  </tr> 
  <tr> 
   <td align="center">0</td> 
   <td align="center">2</td> 
   <td align="center">6</td> 
  </tr> 
  <tr> 
   <td align="center">0</td> 
   <td align="center">3</td> 
   <td align="center">3</td> 
  </tr> 
  <tr> 
   <td align="center">0</td> 
   <td align="center">4</td> 
   <td align="center">0</td> 
  </tr> 
  <tr> 
   <td align="center">1</td> 
   <td align="center">0</td> 
   <td align="center">6</td> 
  </tr> 
  <tr> 
   <td align="center">1</td> 
   <td align="center">1</td> 
   <td align="center">11</td> 
  </tr> 
  <tr> 
   <td align="center">1</td> 
   <td align="center">2</td> 
   <td align="center">12</td> 
  </tr> 
  <tr> 
   <td align="center">1</td> 
   <td align="center">3</td> 
   <td align="center">9</td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="center">0</td> 
   <td align="center">4</td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="center">1</td> 
   <td align="center">9</td> 
  </tr> 
  <tr> 
   <td align="center">2</td> 
   <td align="center">2</td> 
   <td align="center">10</td> 
  </tr> 
  <tr> 
   <td align="center">3</td> 
   <td align="center">0</td> 
   <td align="center">0</td> 
  </tr> 
  <tr> 
   <td align="center">3</td> 
   <td align="center">1</td> 
   <td align="center">5</td> 
  </tr> 
  <tr> 
   <td align="center">4</td> 
   <td align="center">0</td> 
   <td align="center">0</td> 
  </tr> 
 </tbody> 
</table>

其中当  a = 1 , b = 2 a=1, b=2 a=1,b=2 时花费最大, 为 12 。此时 1 个人去第一个项目, 所以

第一个项目的单价为  10 − 4 = 6 10-4=6 10−4=6, 在这个项目上的花费为  6 × 1 = 6 : 2 6 \\times 1=6: 2 6×1=6:2 个人去第二个项目, 所以第二个项目得单价为  7 − 2 × 2 = 3 7-2 \\times 2=3 7−2×2=3, 在这个项目上的花费为  2 × 3 = 6 2 \\times 3=6 2×3=6; 还有 1 个人没去任何项目, 不用统计：总花费为 12 , 这是花费最大的一种方案, 所以答案为 12 。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例,  1 ≤ N , M ≤ 10 1 \\leq N, M \\leq 10 1≤N,M≤10 。

对于  50 % 50 \\% 50% 的评测用例,  1 ≤ N , M ≤ 1000 1 \\leq N, M \\leq 1000 1≤N,M≤1000 。

对于  100 % 100 \\% 100% 的评测用例,  1 ≤ N , M , B i ≤ 1 0 5 , − 1 0 5 ≤ K i < 0 1 \\leq N, M, B\_\{i\} \\leq 10^\{5\},-10^\{5\} \\leq K\_\{i\}<0 1≤N,M,Bi≤105,−105≤Ki<0 。

--------------------

## 试题  J : \\mathrm\{J\}: J: 魔法阵 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 25 分

**【问题描述】**

魔法师小蓝为了营救自己的朋友小  Q \\mathrm\{Q\} Q, 来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有  N N N 个结点  M M M 条边的无向图, 结点编号为  0 , 1 , 2 , … , N − 1 0,1,2, \\ldots, N-1 0,1,2,…,N−1,图中没有重边和自环。敌人在每条边上都布置了陷吽, 每条边都有一个伤害属性  w w w, 每当小蓝经过一条边时就会受到这条边对应的  w w w 的伤害。小蓝从结点 0 出发, 沿着边行走, 想要到达结点  N − 1 N-1 N−1 营救小  Q \\mathrm\{Q\} Q 。

小蓝有一种特殊的魔法可以使用, 假设一条路径按照顺序依次经过了以下  L L L 条边:  e 1 , e 2 , … , e L e\_1, e\_2, \\ldots, e\_L e1,e2,…,eL (可以出现重复的边), 那么期间小蓝受到的总伤害就是  P = ∑ i = 1 L w ( e i ) , w ( e i ) P=\\sum\_\{i=1\}^L w\\left(e\_i\\right), w\\left(e\_i\\right) P=∑i=1Lw(ei),w(ei) 表示边  e i e\_i ei 的伤害属性。如果  L ≥ K L \\geq K L≥K, 那么小蓝就可以从这  L L L 条边当中选出连续出现的  K K K 条边  e c , e c + 1 , … , e c + K − 1 e\_c, e\_\{c+1\}, \\ldots, e\_\{c+K-1\} ec,ec\+1,…,ec\+K−1 并免去在这  K K K 条边行走期间所受到的伤害, 即使用魔法之后路径总伤害变为  P ′ = P − ∑ i = c c + K − 1 w ( e i ) P^\{\\prime\}=P-\\sum\_\{i=c\}^\{c+K-1\} w\\left(e\_i\\right) P′=P−∑i=cc\+K−1w(ei) 。注意必须恰好选出连续出现的  K K K 条边, 所以当  L < K L<K L<K 时无法使用魔法。

小蓝最多只可以使用一次上述的魔法, 请问从结点 0 出发到结点  N − 1 N-1 N−1 受到的最小伤害是多少? 题目保证至少存在一条从结点 0 到  N − 1 N-1 N−1 的路径。

**【输入格式】**

第一行输入三个整数,  N , K , M N, K, M N,K,M, 用空格分隔。  
接下来  M M M 行, 每行包含三个整数  u , v , w u, v, w u,v,w, 表示结点  u u u 与结点  v v v 之间存在一条伤害属性为  w w w 的无向边。

**【输出格式】**

输出一行, 包含一个整数, 表示小蓝从结点 0 到结点  N − 1 N-1 N−1 受到的最小伤宫。

**【样例输入 1】**

4 2 3 \\begin\{array\}\{lll\}4 & 2 & 3\\end\{array\} 423

0 1 2 \\begin\{array\}\{lll\}0 & 1 & 2\\end\{array\} 012

1 2 1 \\begin\{array\}\{lll\}1 & 2& 1\\end\{array\} 121

2 3 4 \\begin\{array\}\{lll\}2 & 3 & 4\\end\{array\} 234

**【样例输出 1】**

2 \\begin\{array\}\{lll\} 2\\end\{array\} 2

**【样例输入 2】**

2 5 1 \\begin\{array\}\{lll\}2 & 5 & 1\\end\{array\} 251

0 1 1 \\begin\{array\}\{lll\}0 & 1 & 1\\end\{array\} 011

**【样例输出 2】**

0 \\begin\{array\}\{lll\}0 \\end\{array\} 0

**【样例说明】**

样例 1 , 存在路径:  0 → 1 → 2 → 3 , K = 2 0 \\rightarrow 1 \\rightarrow 2 \\rightarrow 3, K=2 0→1→2→3,K=2, 如果在  0 → 1 → 2 0 \\rightarrow 1 \\rightarrow 2 0→1→2 上梿用庵法, 那么答案就是  0 + 0 + 4 = 4 0+0+4=4 0\+0\+4=4 : 如果在  1 → 2 → 3 1 \\rightarrow 2 \\rightarrow 3 1→2→3 上使用魔法, 那么答案就是  2 + 0 + 0 = 2 2+0+0=2 2\+0\+0=2 。再也找不到比 2 还小的答案了, 所以答案就是 2 。

样例 2, 存在路徖:  0 → 1 → 0 → 1 → 0 → 1 , K = 5 0 \\rightarrow 1 \\rightarrow 0 \\rightarrow 1 \\rightarrow 0 \\rightarrow 1, K=5 0→1→0→1→0→1,K=5, 这条路径总计佁好

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评议用例，  1 ≤ N ≤ 20 1 \\leq N \\leq 20 1≤N≤20 。  
对于  50 % 50 \\% 50% 的评测用例,  1 ≤ N ≤ 100 1 \\leq N \\leq 100 1≤N≤100 。  
对于  100 % 100 \\% 100% 的评测用例，  1 ≤ N ≤ 1000 , 1 ≤ M ≤ N × ( N − 1 ) 2 , 1 ≤ K ≤ 10 1 \\leq N \\leq 1000,1 \\leq M \\leq \\frac\{N \\times(N-1)\}\{2\}, 1 \\leq K \\leq 10 1≤N≤1000,1≤M≤2N×(N−1),1≤K≤10,  0 ≤ u , v ≤ N − 1 , 1 ≤ w ≤ 1000 0 \\leq u, v \\leq N-1,1 \\leq w \\leq 1000 0≤u,v≤N−1,1≤w≤1000 。

[Link 1]: https://www.captainbed.cn/dl
[42f0ce8335fc4d1391c8e1130c4dd075.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/e33f928d0ad04feaa7871ef3bbb973e5.png
[b1779a11b36840a4b5d0415c9a96a3ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/26aa542635454f2ca8649b9e089f53bc.png
[12e94648df08478592fdae9c4dc605bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/9c318ddde48047e58b85b94cd81758fe.png