BCSP-X 2024第一轮C++编程能力测评(初中组)真题

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. 道路选