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

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⩽

10^5

,1⩽k⩽4)表示花的个数和颜料个数。

第二行给定 k 个正整数 wi(1⩽wi⩽

10^9

)表示每个颜色的花费。

输出描述

输出最小花费，如果不能染色，输出 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⩽

10^5

,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