杨校老师竞赛课之C++备战蓝桥杯初级组省赛

目录

1. 灯塔

题目描述

输入描述

输出描述

输入样例1

输出样例1

输入样例2

输出样例2

数据说明

2. 子区间

题目描述

输入描述

输出描述

输入样例

输出样例

数据说明

3. 染色

题目描述

输入描述

输出描述

输入样例1

输出样例1

输入样例2

输出样例2

数据说明

4. 路灯

题目描述

输入描述

输出描述

输入样例

输出样例

数据说明

5. 求完数

题目描述

输入描述

输出描述

样例输入

样例输出

6. 回形取数

题目描述

输入描述

输出描述

样例输入

样例输出

7. 国际挑战赛

---

1. 1. 灯塔

时间限制：2秒 内存限制：256M

题目描述

有 n 个灯塔排成一行，每一个灯塔都存储了部分能量，第 i 个灯塔的位置为 ai，能量是 bi，当第 i 个灯塔被激活后，所有在这个灯塔左边且与该灯塔距离小于等于 bi 的灯塔都会被摧毁，而该灯塔本身不会受到伤害。

陈平安从右向左依次激活每个灯塔，如果一个灯塔被摧毁了，则它无法被激活。

现在陈平安想让你帮他一个忙，陈平安决定在现有的 n 个激光塔的右边再放一个灯塔，这个灯塔的位置和威力是任意的（但必须在现有灯塔的右边）。陈平安从这个新加入的灯塔开始从右到左依次激活每个灯塔。

现在他想要知道，怎么安排这个新灯塔，可以使得被摧毁的灯塔的总数最少。

输入描述

第一行一个整数 n 表示灯塔的个数。

接下来的 n 行中的第 i 行 每行包含两个数字 ai 和 bi 表示灯塔的位置和能量。

输出描述

输出一个整数，表示最少的被摧毁的灯塔数目。

输入样例1

4

1 9

3 1

6 1

7 4

输出样例1

1

输入样例2

7

1 1

2 1

3 1

4 1

5 1

6 1

7 1

输出样例2

3

数据说明

对于 20% 的数据 n⩽1000,ai⩽1000000

对于 80% 的数据 n⩽100000,ai⩽1000000

1. 2. 子区间

时间限制：1秒 内存限制：256M

题目描述

给定一个长为 n 的序列 a，有 n×(n+1)/2 个子区间，求这些子区间里面区间和为完全平方数的子区间个数

输入描述

第一行一个整数 n

第二行 n 个数表示序列 a

输出描述

输出一个数表示答案

输入样例

 6

 0 1 0 9 1 0

输出样例

 11

数据说明

对于 20% 的数据 n⩽10

#include <iostream>using namespace std;int main() {return 0;
}

1. 3. 染色

时间限制：1秒 内存限制：512M

题目描述

陈平安需要给一个花环染色 ，花环上有 n 朵花，陈平安找到了 k 种颜料，但是每种颜料都有一个花费 wi。陈平安想要以最小的花费将花环染上颜色，但是他有一个特殊要求：花环上的连续三朵花不能是同一种颜色。

你需要帮助陈平安找出染色的最小花费。

注意 花环是环状结构

输入描述

第一行给定两个正整数 n,k (3⩽n⩽,1⩽k⩽4)表示花的个数和颜料个数。

第二行给定 k 个正整数 wi(1⩽wi⩽)表示每个颜色的花费。

输出描述

输出最小花费，如果不能染色，输出 NoNo

输入样例1

5 4

1 2 3 4

输出样例1

7

输入样例2

3 1

1

输出样例2

No

数据说明

对于 20%的数据 n⩽10

另有 80% 的数据 n⩽100000

1. 4. 路灯

时间限制：1秒 内存限制：128M

题目描述

在一片神秘的森林深处，有一条通向古老废墟的小路。这条路上有一排共n个路灯，每个路灯都有不同的状态：有的灯是熄灭的（用0表示），有的是点亮的（用1表示），还有的则是闪烁的（用2表示）。

现在问题是：在这排路灯中，找出最长的连续路灯串，其中不包含亮着的灯或者不包含灭了的灯（任意一种情况均可）。你能计算出这个长度吗？

输入描述

第一行有一个整数T 表示数据组数。 T(T≤100)

接下来每组数据中第一行一个整数 n,第二行一个长度为 n 的字符串 s 表示灯的明灭，数据满足：1⩽n,∑n⩽ ,siϵ0,1,2

输出描述

对于每组数据输出一行一个整数表示答案。

输入样例

3

10

0111122100

5

22222

5

01010

输出样例

7

5

1

数据说明

对于 20% 的数据 t⩽50,n⩽100

对于 20% 的数据 t⩽10,n⩽1000

另有 60% 的数据 t⩽100,n⩽100000

1. 5. 求完数

时间限制：1秒 内存限制：128M

因子：因子也叫因数，例如3×5=153×5=15，那么3和5是15的因子。同时15×1=1515×1=15，那么1和15也是15的因子。 1，3，5，15 这四个因子是15的所有因子。 完数：如果一个数等于不含它本身的其他因子之和，则称该数为‘完数’。如6的因子有1，2，3，6，且1+2+3= 6，因此6是完数。

题目描述

输入一个正整数N（0 < N < 10000）,输出小于N的所有完数及小于N的完数个数（个数前加 * ，例如：*2 ）。

输入描述

输入一个正整数N（0 < N < 10000）

输出描述

输出小于N的所有完数及小于N的完数个数

样例输入

100

样例输出

6

28

*2

1. 6. 回形取数

时间限制：1秒 内存限制：128M

题目描述

回形取数是沿着一个数字矩阵的左上角向右下开始移动取数，当前方没有数字或者数字已经被取过，就会左转继续移动取数，当没有数可取时，回形取数结束。图中的数字路线为：1,5,9,13,14,15,16,12,8,4,3,2,6,10,11,7。

输入描述

第一行输入一个正整数n，作为行数 第二行输入一个正整数m，作为列数 (0<n,m<=20)

输出描述

输出路线，每个数字之间用一个英文逗号隔开。

样例输入

4 4

样例输出

1,5,9,13,14,15,16,12,8,4,3,2,6,10,11,7

1. 7. 国际挑战赛

时间限制：1秒 内存限制：128M

题目描述

希望少年编程挑战国际赛就要开始了，组委会计划选出 5 人代表中国队参赛，选拔条件如下:

1、个人总分=第一场得分+第二场得分。

2、排序按总分高到低排，总分相同按第二场比赛高到低排序，总分和第二场比赛 分数都相同，按准考证号小到大排序。

3、满分选手无论几人都有资格进入国际赛 。

4、总分低于 260 分的选手没有资格进入国际赛。 （满分300分）

输入描述

        第一行 1 个整数 n，代表参赛人数。 接下来各行，每行 3 个整数 id,a,b，是每个参赛选手的准考证号、第一场比赛成绩和 第二场比赛的成绩。

输出描述

        输出若干行，每行一个整数，代表排序后有资格参加国际赛的选手准考证号。

输入样例

6

1 80 183

2 63 68

3 67 114

4 93 148

5 95 69

6 67 142

输出样例

1

数据范围 n不大于100