当前位置：首页 > article >正文

2024年9月青少年软件编程（C语言/C++）等级考试试卷（九级）

article 2024/12/28 18:30:34

青少年软件编程（C 语言）等级考试试卷（九级）

1、两个序列的故事
给定两个整数序列 A = a 1 , a 2 , … , a n 与 B = b 1 , b 2 , … , b n , 我们称 A 中长度为 (r-l+1 )
的连续子序列 a l , a l+1 , … , a r (1 ≤ l ≤ r ≤ n) 是好的，如果 min(a l , a l+1 , …, a r ) ≥ b r-l+1 。
对于所有 1 ≤ k ≤ n 请求出 A 中是否有长度为 k 的好的连续子序列。
时间限制： 1 1 000
内存限制： 2621 44
输入
第一行输入一个整数 n (1 ≤ n ≤ 5 × 1 0 5 ) 表示两个序列的长度。第二行输入 n 个整数
a 1 , a 2 , …, a n (1 ≤ a i ≤ 1 0 6 ) 表示序列 A。第三行输入 n 个整数 b 1 , b 2 , …, b n (1 ≤ b i ≤
1 0 6 ) 表示序列 B。
输出
在一行中输出长度为 n 的字符串 s 1 s 2 … s n 。若 A 中存在长度为 k 的好的连续子序列
则 s k = 1 ，否则 s k = 0。
样例输入
样例#1：
5
1 3 2 5 3
6 3 3 2 3
样例#2：
1
1000000
1000000
样例#3：
1
1
1000000
样例输出
样例#1：
01010
样例#2：
1
样例#3：
0
2、水果安全
有些水果不能一起吃，否则会出问题。例如香蕉和哈密瓜不能一起吃，否则会引起肾虚。
现给定一长串不能一起吃的水果禁忌清单，还有一大篮子水果，你的任务是从篮子里挑
出能随便组合且安全食用的水果。
时间限制： 1 4000
内存限制： 2621 44
输入
输入在第一行中给出两个正整数： N 为禁忌数量， M 为篮子里的水果数量，均不超过
1 00。最后给出两大块信息。第一块包含 N 行，每行给出一对不能一起吃的水果。题
目保证每一对都不同。第二块包含 M 行，每行给出一种水果的编号和价格。水果编号
是一个 3 位数字，价格是不超过 1 000 的正整数。一行中的数字间以空格分隔。
输出
首先在一行中输出可以安全食用的水果的最大数量。在下一行输出所有这些安全的水果，
按编号升序。编号间必须以一个空格分隔，行首尾不得有多余空格。最后第三行输出这
些水果的总价。解有可能不唯一，你需要输出数量最大的解；如果有并列，则输出总
价最低的解。题目保证这样的解是唯一的。
样例输入
16 20
001 002
003 004
004 005
005 006
006 007
007 008
008 003
009 010
009 011
009 012
009 013
010 014
011 015
012 016
012 017
013 018
020 99
019 99
018 4
017 2
016 3
015 6
014 5
013 1
012 1
011 1
010 1
009 10
008 1
007 2
006 5
005 3
004 4
003 6
002 1
001 2
样例输出
12
002 004 006 008 009 014 015 016 017 018 019 020
239