E981 算法应用 星火征途 C++ 初中组 复赛模拟题1-练习

红军的观察哨

题目描述

在红军长征途中，为了提防敌军的围追堵截，指挥部需要提前建立隐蔽的观察哨。侦察兵们绘制了一份详细的局部地形图，将这片山区划分为了 n 行 m 列的网格。其中，第 i 行第 j 列的土地初始海拔高度记录为 a_i,j（行号和列号均从 1 开始编号）。

为了获得最佳的视野，观察哨必须建立在“制高点”上。如果一块土地的海拔高度，严格大于它上下左右直接相邻的所有土地的海拔，我们就称它为一个“制高点”。（注意：位于地图边界的土地，只需和它实际存在的相邻土地进行比较即可）。

请你编写程序，帮红军指挥员计算出这片区域内一共有多少个可以建立观察哨的“制高点”。

输入

第一行包含两个正整数 n 和 m，表示地形图的行数和列数。

接下来 n 行，每行包含 m 个整数，表示对应网格的海拔高度 a(i,j) ，数字之间用一个空格分隔。

输出

输出一行，包含一个整数，表示这片地形图中“制高点”的总数量。

数据范围

对于 100% 的数据，1≤n,m≤1000,1≤a(i,j)≤10^6

输入样例1

3 3

1 2 3

1 4 2

1 1 2

输出样例1

2

输入样例2

3 3

10 2 3

1 2 2

1 1 4

输出样例2

3

输入样例3

2 3

1 1 1

1 1 1

输出样例3

0

红军的三角防线

题目描述

在红军长征途中，为了保障部队的安全和通讯畅通，指挥部决定在广袤的草地上建立一个临时的三角形防线。侦察兵已经在地图上标出了 N 个可以作为通讯哨所的候选坐标点，需要从中选取 3 个点作为三角形的顶点。为了方便快速定向通讯，这个三角形防线必须满足：有一条边与 x 轴（纬线）平行，且有另一条边与 y 轴（经线）平行。

请你帮红军指挥员计算出，在所有合法的部署方案中，三角形防线的最大面积是多少？（保证数据中至少存在一个合法的方案）。

输入

第一行包含一个整数 N。

接下来 N 行，每行包含两个整数xi和yi ，均在 -10000 ~ 10000 范围之内，描述候选坐标点。

输出

由于面积不一定为整数，输出三角形防线的最大面积的两倍。

数据范围

3≤N≤100

输入样例1

4

0 0

0 1

1 0

1 2

输出样例1

2

输入样例2

5

2 3

1 5

2 1

0 3

5 3

输出样例2

6

输入样例3

6

-7 3

-4 -1

-3 6

2 5

3 1

-4 5

输出样例3

36

红军的密电

题目描述

红军长征途中，通讯班需要向总指挥部发送关键的战报密电。为了防止敌军破译，红军的密码本是基于“素数”（质数）构建的。

根据密电规则，每次发送的校验码 N（N > 3），必须由两个素数密令 A 和 B 组合而成，并且校验码 N 必须恰好是 A 和 B 的算术平均数。也就是说：N = (A+B)/2

请你编写程序，帮助小通讯员根据给定的 N 计算出有多少组符合条件的素数 A 和 B。

输入

第一行输入一个整数 T，表示测试用例的数量。

接下来 T 行，每行包含一个整数Ni 。

输出

输出 T 行，对于输入数据中的每一个 Ni ，输出满足Ni = (Ai +Bi)/2且Ai<=Bi的 Ai 与Bi的组数。

数据范围

40% 的数据：对于 1≤i≤T，4≤Ni≤100

100% 的数据：1≤T≤100，对于 1≤i≤ T，4≤Ni≤10^7

输入样例1

4

8

4

7

21

输出样例1

2

1

2

4

输入样例2

2

1000

999

输出样例2

37

56

输入样例3

2

234543

32

输出样例3

4437

5

红军的突击行动

题目描述

在红军长征途中，先遣队发现前方狭长的山谷中，敌军沿路设立了 n 个连成一排的封锁据点。每个据点都有一定的驻军数量，我们用一个包含 n 个正整数的数组 a 来表示，其中 a[i] 代表第 i 个据点的敌军兵力。

为了以最小的代价突破封锁，红军指挥员制定了如下的“突击战术”：

首先，侦察兵会在当前剩余的所有据点中，找出兵力最多的那个据点作为主攻目标。如果兵力最多的据点有多个，为了尽可能向前推进，红军会选择最靠前（即数组中下标最大）的那个。

随后，红军发起突击，拿下该主攻据点，并顺势将它及其之后（下标>=它）的所有据点全部扫清。

请你编写程序计算，红军总共需要发起多少次“突击行动”，才能将所有据点全部拔除（即数组变为空）？

输入

第一行包含一个整数 n（数学公式: 1≤n≤10^5 ），表示初始时敌军据点的总数量。

第二行包含 n 个整数 数学公式: a1 ,a2 ,…,an（1≤ai≤10^9），依次表示从左到右每个据点的敌军兵力，数字之间用一个空格分隔。

输出

输出一行，包含一个整数，表示红军需要发起的突击行动总次数。

数据范围

2≤n≤10^5

输入样例1

5

2 1 2 3 1

输出样例1

3

输入样例2

5

2 2 2 2 2

输出样例2

5