BCSP-X 2024第一轮编程能力测评 (初中组)
T1. 厂房
时间限制 1s,空间限制 256MB
【问题描述】
未来人工智能时代到来了,机器人已经遍布整个工厂。工厂的传送带上依次排列着 N
个机器人,其中,第 i 个机器人的质量为 Ai。经过仔细观察,发现:
1.来自同一个家族的机器人,在这 N 个机器人中一定是连续的一段。
2.如果从第 i 个机器人到第 j 个机器人都来自同一个家族,那么 Ai 到 Aj 从小到大
排序后一定是公差大于 1 的等差数列的子序列。
OpenAI发现,不同家族的个数越少,机器人就会越团结,成功逃离工厂的概率就会越
高。我们想知道,这 N 个机器人最少来自几个不同的家族呢?
【输入格式】
第一行一个正整数 N。
接下来一行 N 个正整数,第 i 个正整数为 Ai。
【输出格式】
一行一个正整数,表示答案。
【样例输入 1】
7
1 5 11 2 6 4 7
【样例输出 1】
3
【样例说明 1】
1 5 11 是等差数列 {1,3,5,7,9,11}的子序列,
2 4 6 是等差数列 {2,4,6,8}的子序列,
7 是等差数列 {7,9,11}的子序列。
【样例输入 2】
8
4 2 6 8 5 3 1 7
【样例输出 2】
2
【样例说明 2】
2 4 6 8 是等差数列 {2,4,6,8}的子序列,
1 3 5 7 是等差数列 {1,3,5,7}的子序列。
【数据范围】
20%的数据满足, N≤10。
40%的数据满足, N≤100。
60%的数据满足, N≤1000,1≤Ai≤10^6。
另有 20%的数据满足, Ai 互不相同。
100%的数据满足, N≤100000,1≤Ai≤10^9
T2. 打孔纸带
时间限制 1s,空间限制 256MB
【问题描述】
小度捡到了一台奇怪的机器。往里面塞进去两条固定长度的打孔纸带,就会吐出一条同
样长度的打孔纸带。打印出来的纸带是没法放进机器里的。
在经过一段时间的思索之后,小度发现了这台机器的输出具有一定的规律。具体而言,
输出的每一位都是输入两个打孔纸带上同样位置值的“与”,“或”或者“异或”。
拿着手中的纸带,若有所思的小度想要知道,他最少要自己制作多少条新的打孔纸带,
才能知道这台机器的确切工作方式?
【输入格式】
第一行,包含一个整数 N,表示已有纸带的数目。
接下来 N 行,每行包含一个字符串,表示已有的纸带的情况。
【输出格式】
一行,包含一个数,需要自己制作的纸带数。
【输入样例】
2
01010101
10101010
【输出样例】
1
【数据范围】
• 对于分值为 40 的子任务 1,保证 N ≤ 50,纸带长度 ≤ 10
• 对于分值为 60 的子任务 2,保证 N ≤ 50,纸带长度 ≤ 100。
T3. 道路选
北京市中小学信息学能力测评活动BCSP-X 2024 第一轮编程能力测评(初中组)真题