第十三届蓝桥杯决赛(国赛)真题 Java C 组【原卷】

文章目录

  • 发现宝藏
  • 试题 A: 斐波那契与 7
  • 试题 B: 小蓝做实验
  • 试题 C: 取模
  • 试题 D: 内存空间
  • 试题 E \mathrm{E} E : 斐波那契数组
  • 试题 F: 最大公约数
  • 试题 G: 交通信号
  • 试题 I: 打折
  • 试题 J: 宝石收集

发现宝藏

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


第十三届蓝桥杯大赛软件赛国赛
Java C 组

【考生须知】

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

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

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

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

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

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

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

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

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

注意: 不要使用 package 语句。

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

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


试题 A: 斐波那契与 7

本题总分: 5 分

【问题描述】

斐波那契数列的递推公式为: F n = F n − 1 + F n − 2 F_{n}=F_{n-1}+F_{n-2} Fn=Fn1+Fn2, 其中 F 1 = F 2 = 1 F_{1}=F_{2}=1 F1=F2=1

请问, 斐波那契数列的第 1 至 202202011200 项(含)中, 有多少项的个位是 7 。

【答案提交】

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


试题 B: 小蓝做实验

本题总分:5 分

【问题描述】

小蓝很喜欢科研, 他最近做了一个实验得到了一批实验数据, 一共是两百万个正整数。如果按照预期, 所有的实验数据 x x x 都应该满足 1 0 7 ≤ x ≤ 1 0 8 10^{7} \leq x \leq 10^{8} 107x108 。但是做实验都会有一些误差, 会导致出现一些预期外的数据, 这种误差数据 y y y 的范围是 1 0 3 ≤ y ≤ 1 0 12 10^{3} \leq y \leq 10^{12} 103y1012 。由于小蓝做实验很可靠, 所以他所有的实验数据中 99.99 % 99.99 \% 99.99% 以上都是符合预期的。小蓝的所有实验数据都在 primes.txt 中, 现在他想统计这两百万个正整数中有多少个是质数, 你能告诉他吗?

【答案提交】

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


试题 C: 取模

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

【问题描述】

给定 n , m n, m n,m, 问是否存在两个不同的数 x , y x, y x,y 使得 1 ≤ x < y ≤ m 1 \leq x<y \leq m 1x<ym n m o d x = n \bmod x= nmodx= n m o d y n \bmod y nmody

【输入格式】

输入包含多组独立的询问。

第一行包含一个整数 T T T 表示询问的组数。

接下来 T T T 行每行包含两个整数 n , m n, m n,m, 用一个空格分隔, 表示一组询问。

【输出格式】

输出 T T T 行, 每行依次对应一组询问的结果。如果存在, 输出单词 Yes; 如果不存在, 输出单词 No。

【样例输入】

3 \begin{array}{llll}3\end{array} 3

5 2 \begin{array}{llll}5&2 \end{array} 52

99 9 \begin{array}{llll}99&9 \end{array} 999

【样例输出】

N o \begin{array}{llll}No \end{array} No

N o \begin{array}{llll}No \end{array} No

Y e s \begin{array}{llll}Yes \end{array} Yes

【评测用例规模与约定】

对于 20 % 20 \% 20% 的评测用例, T ≤ 100 , n , m ≤ 1000 T \leq 100, n, m \leq 1000 T100,n,m1000;

对于 50 % 50 \% 50% 的评测用例, T ≤ 10000 , n , m ≤ 1 0 5 T \leq 10000, n, m \leq 10^{5} T10000,n,m105;

对于所有评测用例, 1 ≤ T ≤ 1 0 5 , 1 ≤ n ≤ 1 0 9 , 2 ≤ m ≤ 1 0 9 1 \leq T \leq 10^{5}, 1 \leq n \leq 10^{9}, 2 \leq m \leq 10^{9} 1T105,1n109,2m109


试题 D: 内存空间

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

【问题描述】

小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。

为了简化问题, 变量的类型只有以下三种:

int: 整型变量, 一个 int 型变量占用 4 Byte 的内存空间。

long:长整型变量, 一个 long 型变量占用 8 Byte 的内存空间。

String: 字符串变量, 占用空间和字符串长度有关, 设字符串长度为 L L L,则字符串占用 L L L Byte 的内存空间, 如果字符串长度为 0 则占用 0 Byte 的内存空间。

定义变量的语句只有两种形式, 第一种形式为:

type var1=value1, var2=value2…;

定义了若干个 type 类型变量 var1、var2、开, 并且用 value1、value2 …初始化,

多个变量之间用’, ‘分隔, 语句以’; '结尾, type 可能是 int、long 或 String。例如 int a = 1 , b = 5 , c = 6 a=1, b=5, c=6 a=1,b=5,c=6; 占用空间为 12 Byte; long a = 1 , b = 5 a=1, b=5 a=1,b=5;占用空间为 16 Byte; String s 1 = s 1= s1= " ", s2=“hello”, s3=“world”;占用空间为 10 Byte。

第二种形式为:

type[] arr1=new type[size1], arr2=new type[size2] ⋯ \cdots ;

定义了若干 type 类型的一维数组变量 arr ⁡ 1 , arr ⁡ 2 ⋯ \operatorname{arr} 1, \operatorname{arr} 2 \cdots arr1,arr2, 且数组的大小为 size1、size2 是, 多个变量之间用’, ‘进行分隔, 语句以’;’ 结尾, type 只可能是 int 或 long。例如 int [] al=new int[10]; 占用的内存空间为 40

Byte; long[] a1=new long[10],a2=new long[10];占用的内存空间为 160 Byte.

已知小蓝有 T T T 条定义变量的语句, 请你帮他统计下一共占用了多少内存空间。结果的表示方式为: a G B b M B c K B d B a \mathrm{~GB} b \mathrm{MB} c \mathrm{~KB} d \mathrm{~B} a GBbMBc KBd B, 其中 a 、 b 、 c 、 d a 、 b 、 c 、 d abcd 为统计的结果, GB、MB、KB、B 为单位。优先用大的单位来表示, 1 G B = 1024 M B 1 \mathrm{~GB}=1024 \mathrm{MB} 1 GB=1024MB, 1 M B = 1024 K B , 1 K B = 1024 B 1 \mathrm{MB}=1024 \mathrm{~KB}, 1 \mathrm{~KB}=1024 \mathrm{~B} 1MB=1024 KB,1 KB=1024 B, 其中 B 表示 Byte。如果 a 、 b 、 c 、 d a 、 b 、 c 、 d abcd 中的某几个数字为 0 , 那么不必输出这几个数字及其单位。题目保证一行中只有一句定义变量的语句, 且每条语句都满足题干中描述的定义格式, 所有的变量名都是合法的且均不重复。题目中的数据很规整, 和上述给出的例子类似, 除了类型后面有一个空格, 以及定义数组时 new 后面的一个空格之外, 不会出现多余的空格。

【输入格式】

输入的第一行包含一个整数 T T T, 表示有 T T T 句变量定义的语句。

接下来 T T T 行, 每行包含一句变量定义语句。

【输出格式】

输出一行包含一个字符串, 表示所有语句所占用空间的总大小。

【样例输入 1】

1

long [ ] nums=new long [131072];

【样例输出 1】

1 M B 1 \mathrm{MB} 1MB

【样例输入 2】

4

int a = 0 , b = 0 a=0, b=0 a=0,b=0;

long x = 0 , y = 0 x=0, y=0 x=0,y=0

String s 1 = \mathrm{s} 1= s1= “hello”, s 2 = \mathrm{s} 2= s2= “world”;

long[ ] arr1=new long[100000], arr2=new long[100000];

【样例输出 2】

1 MB538KB546B

【样例说明】

样例 1 , 占用的空间为 131072 × 8 = 1048576 B 131072 \times 8=1048576 \mathrm{~B} 131072×8=1048576 B, 换算过后正好是 1 M B 1 \mathrm{MB} 1MB, 其它三个单位 G B 、 K B 、 B \mathrm{GB} 、 \mathrm{~KB} 、 \mathrm{~B} GB KB B 前面的数字都为 0 , 所以不用输出。

样例 2 , 占用的空间为 4 × 2 + 8 × 2 + 10 + 8 × 100000 × 2 B 4 \times 2+8 \times 2+10+8 \times 100000 \times 2 \mathrm{~B} 4×2+8×2+10+8×100000×2 B, 换算后是 1MB538K5546B。

【评测用例规模与约定】

对于所有评测用例, 1 ≤ T ≤ 10 1 \leq T \leq 10 1T10, 每条变量定义语句的长度不会超过 1000 - 所有的变量名称长度不会超过 10 , 且都由小写字母和数字组成。对于整型变量, 初始化的值均是在其表示范围内的十进制整数, 初始化的值不会是变量.对于 String 类型的变量, 初始化的内容长度不会超过 50 , 且内容仅包含小写字母和数字, 初始化的值不会是变量. 对于数组类型变量, 数组的长度为一个整数, 范围为: [ 0 , 2 30 ] \left[0,2^{30}\right] [0,230], 数组的长度不会是变量。 T T T 条语句定义的变量所占的内存空间总大小不会超过 1 G B 1 \mathrm{~GB} 1 GB, 且大于 0 B 0 \mathrm{~B} 0 B


试题 E \mathrm{E} E : 斐波那契数组

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

【问题描述】

如果数组 A = ( a 0 , a 1 , ⋯ , a n − 1 ) A=\left(a_{0}, a_{1}, \cdots, a_{n-1}\right) A=(a0,a1,,an1) 满足以下条件, 就说它是一个斐波那契数组:

  1. n ≥ 2 n \geq 2 n2;
  2. a 0 = a 1 a_{0}=a_{1} a0=a1;
  3. 对于所有的 i ( i ≥ 2 ) i(i \geq 2) i(i2), 都满足 a i = a i − 1 + a i − 2 a_{i}=a_{i-1}+a_{i-2} ai=ai1+ai2

现在, 给出一个数组 A A A, 你可以执行任意次修改, 每次修改将数组中的某个位置的元素修改为一个大于 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,,an1, 相邻两个整数之间用一个空格分隔。

【输出格式】

输出一行包含一个整数表示最少需要修改数组 A A A 中的几个元素之后, 数组 A A A 可以变为一个斐波那契数组。

【样例输入】

5 \begin{array}{llll}5 \end{array} 5

1 2 4 4 8 \begin{array}{llll}1&2 &4&4&8\end{array} 12448

【样例输出】

3 \begin{array}{llll}3 \end{array} 3

【样例说明】

将原数组修改为 ( 1 , 1 , 2 , 3 , 5 ) (1,1,2,3,5) (1,1,2,3,5), 最少修改三个元素变成了一个斐波那契数组。

【评测用例规模与约定】

对于所有评测用例, 2 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 6 2 \leq n \leq 10^{5}, 1 \leq a_{i} \leq 10^{6} 2n105,1ai106


试题 F: 最大公约数

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

【问题描述】

给定一个数组, 每次操作可以选择数组中任意两个相邻的元素 x , y x, y x,y 并将其中的一个元素替换为 gcd ⁡ ( x , y ) \operatorname{gcd}(x, y) gcd(x,y), 其中 gcd ⁡ ( x , y ) \operatorname{gcd}(x, y) gcd(x,y) 表示 x x x y y y 的最大公约数。

请问最少需要多少次操作才能让整个数组只含 1 。

【输入格式】

输入的第一行包含一个整数 n n n, 表示数组长度。

第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_{1}, a_{2}, \cdots, a_{n} a1,a2,,an, 相邻两个整数之间用一个空格分隍。

【输出格式】

输出一行包含一个整数, 表示最少操作次数。如果无论怎么操作都无法满足要求, 输出 -1 。

【样例输入】

2 \begin{array}{llll}2 \end{array} 2

4 6 9 \begin{array}{llll}4&6&9\end{array} 469

【样例输出】

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

【评测用例规模与约定】

对于 30 % 30 \% 30% 的评测用例, n ≤ 500 , a i ≤ 1000 n \leq 500, a_{i} \leq 1000 n500,ai1000

对于 50 % 50 \% 50% 的评测用例, n ≤ 5000 , a i ≤ 1 0 6 n \leq 5000, a_{i} \leq 10^{6} n5000,ai106;

对于所有评测用例, 1 ≤ n ≤ 100000 , 1 ≤ a i ≤ 1 0 9 1 \leq n \leq 100000,1 \leq a_{i} \leq 10^{9} 1n100000,1ai109


试题 G: 交通信号

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

【问题描述】

LQ 市的交通系统可以看成由 n n n 个结点和 m m m 条有向边组成的有向图. 在每条边上有一个信号灯,会不断按绿黄红黄绿黄红黄… 的顺序循环 (初始时刚好变到绿灯)。当信号灯为绿灯时允许正向通行, 红灯时允许反向通行, 黄灯时不允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立, 其中黄灯的持续时长等同于走完路径的耗时。当走到一条边上时, 需要观察边上的信号灯,如果允许通行则可以通过此边, 在通行过程中不再受信号灯的影响: 否则需要等待, 直到允许通行。

请问从结点 s s s 到结点 t t t 所需的最短时间是多少, 如果 s s s 无法到达 t t t 则输出 -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 所需的最短时间。

【样例输入】

4 4 1 4 \begin{array}{llll}4 & 4 & 1 & 4\end{array} 4414

1 2 1 2 6 \begin{array}{lllll}1 & 2 & 1 & 2 & 6\end{array} 12126

4 2 1 1 5 \begin{array}{llllll}4 & 2 & 1 & 1 & 5\end{array} 42115

1 3 1 1 1 \begin{array}{llllll}1 & 3 & 1 & 1 & 1\end{array} 13111

3 4 1 99 1 \begin{array}{lllll}3 & 4 & 1 & 99 & 1\end{array} 341991

【样例输出】

11 \begin{array}{llll}11\end{array} 11

【评测用例规模与约定】

对于 40 % 40 \% 40% 的评测用例, n ≤ 500 , 1 ≤ g i , r i , d i ≤ 100 n \leq 500,1 \leq g_{i}, r_{i}, d_{i} \leq 100 n500,1gi,ri,di100

对于 70 % 70 \% 70% 的评测用例, n ≤ 5000 n \leq 5000 n5000

对于所有评测用例, 1 ≤ n ≤ 100000 , 1 ≤ m ≤ 200000 , 1 ≤ s , t ≤ n 1 \leq n \leq 100000,1 \leq m \leq 200000,1 \leq s, t \leq n 1n100000,1m200000,1s,tn, 1 ≤ u i , v i ≤ n , 1 ≤ g i , r i , d i ≤ 1 0 9 1 \leq u_{i}, v_{i} \leq n, 1 \leq g_{i}, r_{i}, d_{i} \leq 10^{9} 1ui,vin,1gi,ri,di109

试题 H \mathrm{H} H : 点亮

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

【问题描述】

小蓝最近迷上了一款名为 《点亮》的迷题游戏, 游戏在一个 n × n n \times n n×n 的格子棋盘上进行, 棋盘由黑色和白色两种格子组成, 玩家在白色格子上放置灯泡, 确保任意两个灯泡不会相互照射, 直到整个棋盘上的白色格子都被点亮(每个谜题均为唯一解)。灯泡只会往水平和垂直方向发射光线, 照亮整行和整列, 除非它的光线被黑色格子挡住。黑色格子上可能有从 0 到 4 的整数数字, 表示与其上下左右四个相邻的白色格子共有几个奵泡; 也可能没有数字, 这表示可以在上下左右四个相邻的白色格子处任意选择几个位置放置灯泡。游戏的目标是选择合适的位置放置灯泡, 使得整个棋盘上的白色格子都被照亮。

例如, 有一个黑色格子处数字为 4 , 这表示它周围必须有 4 个灯泡, 需要在他的上、下、左、右处分别放置一个灯泡: 如果一个黑色格子处数字为 2 , 它的上下左右相邻格子只有 3 个格子是白色格子, 那么需要从这三个白色格子中选择两个来放置灯泡; 如果一个黑色格子没有标记数字, 且其上下左右相邻格子全是白色格子, 那么可以从这 4 个白色格子中任选出 0 至 4 个来放置灯泡。

题目保证给出的数据是合法的, 黑色格子周围一定有位置可以放下对应数量的奵泡。且保证所有谜题的解都是唯一的。

现在,给出一个初始的棋盘局面,请在上面放置好灯泡,使得整个棋盘上的白色格子被点亮。

【输入格式】

输入的第一行包含一个整数 n n n, 表示棋盘的大小。

接下来 n n n 行, 每行包含 n n n 个字符, 表示给定的棋盘。字符. 表示对应的格子为白色, 数字字符 0 、 1 、 2 、 3 、 4 0 、 1 、 2 、 3 、 4 01234 表示一个有数字标识的黑色格子, 大写字母 X 表示没有数字标识的黑色格子。

【输出格式】

输出 n n n 行, 每行包含 n n n 个字符, 表示答案。大写字母 ○ 表示对应的格子包含奵泡, 其它字符的意义与输入相同。

【样例输入】

在这里插入图片描述

【样例输出】

在这里插入图片描述

【样例说明】

答案对应的棋盘布局如下图所示:

在这里插入图片描述

【评测用例规模与约定】

对于所有评测用例, 2 ≤ n ≤ 5 2 \leq n \leq 5 2n5, 且棋盘上至少有 15 % 15 \% 15% 的格子是黑色格子。


试题 I: 打折

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

【问题描述】

小蓝打算采购 n n n 种物品, 每种物品各需要 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 ⌋ \left\lfloor\frac{b \cdot p j}{100}\right\rfloor 100bpj 。其它时间需按原价购买。

小蓝很仙, 他只能选择一天的时间去采购这些物品。请问, 他最少需要花多少钱才能买到需要的所有物品。

题目保证小蓝一定能买到需要的所有物品。

【输入格式】

输入的第一行包含两个整数 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 至 n n n 编号。

【输出格式】

输出一行包含一个整数表示小蓝需要花费的最少的钱数。

【样例输入】

2 2 \begin{array}{llll}2& 2 \end{array} 22

1 2 89 1 \begin{array}{llll}1 & 2 & 89 & 1\end{array} 12891

9 7 \begin{array}{llll}9&7\end{array} 97

3 4 77 1 \begin{array}{llll}3 & 4 & 77 & 1\end{array} 34771

2 15 \begin{array}{llll}2 &15 \end{array} 215

【样例输出】

101 \begin{array}{llll}101\end{array} 101

【评测用例规模与约定】

对于 40 % 40 \% 40% 的评测用例, n , m ≤ 500 , s i ≤ t i ≤ 100 , ∑ c i ≤ 2000 n, m \leq 500, s_{i} \leq t_{i} \leq 100, \sum c_{i} \leq 2000 n,m500,siti100,ci2000;

对于 70 % 70 \% 70% 的评测用例, n , m ≤ 5000 , ∑ c i ≤ 20000 n, m \leq 5000, \sum c_{i} \leq 20000 n,m5000,ci20000;

对于所有评测用例, 1 ≤ n , m ≤ 100000 , 1 ≤ c i ≤ n , ∑ c i ≤ 400000 1 \leq n, m \leq 100000,1 \leq c_{i} \leq n, \sum c_{i} \leq 400000 1n,m100000,1cin,ci400000, 1 ≤ s i ≤ t i ≤ 1 0 9 , 1 < p i < 100 , 1 ≤ a j ≤ n , 1 ≤ b j ≤ 1 0 9 1 \leq s_{i} \leq t_{i} \leq 10^{9}, 1<p_{i}<100,1 \leq a_{j} \leq n, 1 \leq b_{j} \leq 10^{9} 1siti109,1<pi<100,1ajn,1bj109


试题 J: 宝石收集

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

【问题描述】

小蓝最近迷上了一欨收集宝石的游戏, 在游戏中给出了一幅藏宝图, 藏宝图可以看做是由 n n n 个顶点组成的一个有向图, 顶点编号为 0 , 1 , 2 , ⋯ , n − 1 0,1,2, \cdots, n-1 0,1,2,,n1 。每个顶点有且仅有一颗宝石,可能是红宝石或蓝宝石。

小蓝有一次收集宝石的机会, 他可以任意选择一个顶点当做起点, 沿着有向边前进, 经过的顶点上的宝石都会被自动收集 (包括起点和终点), 直到前方无路可走或者小蓝想退出时停止本次收集。小蓝可以多次经过同一个顶点, 但只会在第一次到达顶点时获得宝石, 后面再次到达时不会再获得宝石。

收集结束后, 小蓝可以用手中的宝石合成紫晶宝石: 一颗红宝石加一颗蓝宝石就可以合成一颗紫晶宝石。

小蓝想在收集结束后合成尽可能多的紫晶宝石, 请帮他规划出一条最优路径, 告诉他最多可以合成多少颗紫晶宝石。

【输入格式】

输入的第一行包含一个整数 n n n, 表示有顶点的个数。

第二行包含一个由 0 、 1 0 、 1 01 组成的长度为 n n n 的字符串, 从左至右依次表示第 0 至 n − 1 n-1 n1 个顶点处宝石的种类, 0 表示红宝石, 1 表示蓝宝石。

第三行包含一个整数 m m m ,表示图中有 m m m 条有向边。

接下来 m m m 行, 每行包含两个整数 s , t s, t s,t, 用一个空格分隔, 表示一条从 s s s t t t 的有向边。

【输出格式】

输出一行包含一个整数, 表示小蓝最多能合成几颗紫晶宝石。

【样例输入】

6 \begin{array}{llll}6\end{array} 6

000111 \begin{array}{llll}000111\end{array} 000111

6 \begin{array}{llll}6\end{array} 6

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

1 2 \begin{array}{llll}1&2\end{array} 12

3 1 \begin{array}{llll}3&1\end{array} 31

2 3 \begin{array}{llll}2&3\end{array} 23

2 4 \begin{array}{llll}2&4\end{array} 24

2 5 \begin{array}{llll}2&5\end{array} 25

【样例输出】

2 \begin{array}{llll}2\end{array} 2

【样例说明】

在这里插入图片描述

样例如上图所示, 选择 0 号顶点作为起点, 按照 0 → 1 → 2 → 3 → 1 → 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 01231 2 → 4 2 \rightarrow 4 24 的行进路线, 可以获得 3 颗红宝石和 2 颗蓝宝石, 最终可以合成 2 颗紫晶宝石: 他也可以按照 1 → 2 → 3 → 1 → 2 → 4 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4 123124 行进, 结果也是 2 。找不到比 2 更大的答案了。

【评测用例规模与约定】

对于所有的评测用例, 1 ≤ n ≤ 2000 , 0 ≤ m ≤ 1 0 5 , 0 ≤ s ≤ n − 1 1 \leq n \leq 2000,0 \leq m \leq 10^{5}, 0 \leq s \leq n-1 1n2000,0m105,0sn1, 0 ≤ t ≤ n − 1 0 \leq t \leq n-1 0tn1

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3029689.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

如何在 CentOS 上安装并配置 Redis

如何在 CentOS 上安装并配置 Redis 但是太阳&#xff0c;他每时每刻都是夕阳也都是旭日。当他熄灭着走下山去收尽苍凉残照之际&#xff0c;正是他在另一面燃烧着爬上山巅散烈烈朝晖之时。 ——史铁生 环境准备 本教程将在 CentOS 7 或 CentOS 8 上进行。确保你的系统已更新到最…

【数据结构】队列详解(Queue)

文章目录 有关队列的概念队列的结点设计及初始化队列的销毁判空和计数入队操作出队操作 有关队列的概念 队列:只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c;队列具有先进先出FIFO(First In First Out)入队列:进行插入操作的一端…

【C++】详细版 RAII技术的应用之智能指针(智能指针发展历程和简单模拟实现介绍)

目录 前言 一、智能指针有什么用&#xff1f; 二、什么是RAII(智能指针的底层思想)&#xff1f; 三、智能指针的发展历程以及模拟实现 1.auto_ptr&#xff08;C98&#xff09; 2.unique_ptr&#xff08;C11&#xff09; 3.shared_ptr&#xff08;C11&#xff09; 前言 C中…

Linux修炼之路之初识操作系统+基础指令(1)

目录 引言 一&#xff1a;对操作系统(OS)的简单了解 1.操作系统(OS) 是什么 2.操作系统好坏的衡量标准 3.操作系统存在的重要性 4.理解所有在计算机上的操作 二&#xff1a;Linux与windows操作的特点区别 三&#xff1a;基础指令 1.ls 指令 1.使用 2.常用选项 2.…

2024-AIDD-人工智能药物设计-AlphaFold3

AlphaFold3&#xff5c;万字长文解读 AlphaFold3预测所有分子相互作用准确结构 AlphaFold3 自2021年AlphaFold2问世以来&#xff0c;科研工作者们便开始利用这一蛋白结构预测模型来详细描绘众多蛋白质的结构、探索新药。近日&#xff0c;Google DeepMind公司推出了其最新产品…

关于JAVA-JSP电子政务网实现参考论文(论文 + 源码)

【免费】关于JAVA-JSP电子政务网.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89292355关于JAVA-JSP电子政务网 摘 要 当前阶段&#xff0c;伴随着社会信息技术的快速发展&#xff0c;使得电子政务能够成为我国政府职能部门进行办公管理的一个重要内容&#x…

日本OTC机械手维修需要注意哪些问题呢?

随着工业4.0时代的到来&#xff0c;机器人在制造业中的应用越来越广泛。OTC&#xff08;Over The Counter&#xff09;机器人作为工业机器人的一种&#xff0c;以其高效、精准、稳定的特点受到众多企业的青睐。然而&#xff0c;在实际使用过程中&#xff0c;可能会出现一些OTC机…

每日一题——力扣27. 移除元素(举一反三)

题目链接&#xff1a;https://leetcode.cn/problems/remove-element/description/ 菜鸡写法&#xff1a; // 函数定义&#xff0c;移除数组nums中所有值为val的元素&#xff0c;并返回新的数组长度 int removeElement(int* nums, int numsSize, int val) {// 如果数组长度为…

【智能优化算法】金豺狼优化算法(Golden jackal optimization,GJO)

金豺狼优化(Golden jackal optimization,GJO)是期刊“Expert Systems with Applications”&#xff08;中科院一区IF 8.3&#xff09;的2022年智能优化算法 01.引言 金豺狼优化(Golden jackal optimization,GJO)旨在为解决实际工程问题提供一种替代的优化方法。GJO的灵感来自金…

c++:(map和set的底层简单版本,红黑树和AVL树的基础) 二叉搜索树(BST)底层和模拟实现

文章目录 二叉搜索树的概念二叉搜索树的操作二叉搜索树的查找find 二叉搜索树的模拟实现构造节点insertfinderase(细节巨多,面试可能会考)a.叶子节点b.有一个孩子左孩子右孩子 c.有两个孩子注意: erase代码 中序遍历 二叉搜索树的应用k模型k模型模拟实现的总代码 k-value模型k-…

高校教务选课管理系统开发方案

一、项目背景与目标 &#xff08;一&#xff09;项目背景 随着高校教育规模的扩大&#xff0c;教务管理变得越来越复杂&#xff0c;传统的手工管理方式已经无法满足现代高校的需求。因此&#xff0c;开发一套高效、便捷的高校教务选课管理系统显得尤为重要。该系统将涵盖学生…

基于Springboot+Vue的Java项目-车辆管理系统开发实战(附演示视频+源码+LW)

大家好&#xff01;我是程序员一帆&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &am…

公司活动想找媒体报道宣传怎样联系媒体?

作为公司宣传负责人,我深知媒体报道对于企业活动宣传的重要性。然而,在过去,每当有重要活动需要媒体曝光时,我总会被繁琐的媒体联系工作所困扰。 那时,我需要一家家地查询媒体联系方式,发送邮件、打电话,甚至亲自前往媒体机构进行沟通。然而,这样的过程不仅费时费力,而且效率低…

C++ 抽象与封装

一 抽象 抽象实例&#xff1a;时钟 数据抽象&#xff1a; 具有表面当前时间的时、分、秒 行为抽象&#xff1a; 具有设置时间和显示时间两个最基本的功能。 抽象实例&#xff1a;人 数据抽象&#xff1a;姓名、年龄、性别等。 行为抽象&#xff1a; 生物属性&#xff1a;吃…

宏集Panorama SCADA软件获BACnet BTL认证

Panorama 获得BACnet BTL认证 建筑物的组件&#xff08;空调系统、照明传感器等&#xff09;能否使用共同通讯协议&#xff1f;这正是标准化 BACnet协议&#xff08;Building Automation and Control Networks&#xff09;所提供的功能。该协议旨在实现建筑物中各种设备和系统…

更新、简略高效的用git(Gitee篇)

前提&#xff1a;因为很多编译软件虽然可以连接git&#xff0c;但是操作起来还是比较懵&#xff0c;不同软件有不同的上传git的方式&#xff0c;而且有的连着GitHub有的是Gitee&#xff0c;那么使用Git Bash无疑是万无一失的方式 然后这一篇也仅针对上传Gitee&#xff0c;上传G…

【C++】学习笔记——优先级队列

文章目录 十、优先级队列1. priority_queue的介绍2. 优先级队列如何使小的数据优先级高3. 仿函数介绍4. priority_queue的模拟实现 补&#xff1a; 反向迭代器未完待续 十、优先级队列 1. priority_queue的介绍 优先级队列 其实也不属于队列&#xff0c;它跟 stack 和 queue …

【智能优化算法】卷尾猴搜索算法(Capuchin search algorithm,CapSA)

【智能优化算法】卷尾猴搜索算法(Capuchin search algorithm,CapSA)是期刊“NEURAL COMPUTING & APPLICATIONS”&#xff08;IF 6.0&#xff09;的2021年智能优化算法 01.引言 【智能优化算法】卷尾猴搜索算法(Capuchin search algorithm,CapSA)用于解决约束和全局优化问…

Ubuntu 安装 samba 实现文件共享

1. samba的安装: sudo apt-get install samba sudo apt-get install smbfs2. 创建共享目录 mkdir /home/share sudo chmod -R 777 /home/share3. 创建Samba配置文件: 3.1 保存现有的配置文件 sudo cp /etc/samba/smb.conf /etc/samba/smb.conf.bak3.2 打开现有的文件 sudo…

安卓开发--按键跳转页面

前面已经介绍了一个空白按键工程的建立以及响应方式&#xff0c;可以参考这里&#xff1a;安卓开发–新建工程&#xff0c;新建虚拟手机&#xff0c;按键事件响应。 安卓开发是页面跳转是基础&#xff01;&#xff01;&#xff01;所以本篇博客介绍利用按键实现页面跳转。 前…