challenging Programming questions

challenging Programming questions

1.Programming (20Points)
Problem 过冬
【题目描述】

土地上开了n朵名贵的花，但随着冬天的来临难以抵挡住寒风，勤劳的你需要给它们修建一个大棚让他们平安度过冬天。现在给你这n朵花的坐标，请你设计一个最小的正方形大棚，使得所有花能够平安度过冬天。（在正方形边上的花认为在大棚内部）

【输入输出格式】

第一行是一个整数n，表示有n朵花。

接下来有n行，每行两个整数x,y表示花的坐标。

输出一个整数，最小的正方形大棚的边长。

【样例】

输入：

5
-1 1
2 3
4 2
2 2
-4 0
输出：

8
【数据范围】

80%的数据满足1 ≤ n ≤ 103,-109 ≤ x,y ≤ 10^9；

100%的数据满足1 ≤ n ≤ 105,-109 ≤ x,y ≤ 10^9。

2.Programming (20Points)
Problem 统计区间字母个数
【题目描述】

设有一个字符串S，它全部由小写字母组成。

现在，老师想知道，字符串S从下标L到下标R的区间中，不同的小写字母各出现了多少次。（注意：字符串下标从0开始）

老师一共会向你询问Q次，每次都会告诉你区间的起始下标L和终止下标R。请你回答每次询问。

【输入描述】

第一行一个字符串S（长度 <= 1000）

第二行为一个整数Q（Q <= 100）

接下来有Q行，每行两个整数L和R。（0 <= L, R < 字符串S的长度））

【输出描述】

对于每次询问，输出一行结果，表示每种小写字母出现的次数。

输出格式为”<小写字母>:<出现次数>”，请按从a到z的次序，输出每种小写字母，以及对应出现的次数。用英文冒号分隔字母和次数，中间没有空格。

每两种小写字母的结果之间用一个空格隔开。

忽略出现次数为0的小写字母。

【样例输入】

abcdefgaaa
2
0 0
1 8
【样例输出】

a:1
a:2 b:1 c:1 d:1 e:1 f:1 g:1
【注释】

第一次询问，区间为[0, 0]，即"[a]bcdefgaaa"，因此只出现一个小写字母a。

第二次询问，区间为[1, 8]，即"a[bcdefgaa]a"，因此出现a两次，b~g各一次。

3.Programming (20Points)
Problem 素数间距
【题目描述】

“素数（也称质数）”是指在大于1的自然数中，除了1和它本身以外没有其他因数的自然数。如果两个素数之间没有其他素数，则称这两个素数为一对**“相邻素数”**。例如，2和3是一对“相邻素数”，3和7则不是“相邻素数”，因为在3和7之间有素数5。

请你编写一个程序，对于给定两个数字L和U所限定的区间，你需要

（1）找到一对“相邻素数”C1和C2（L ≤ C1 < C2 ≤ U），使得C2-C1最小。如果在这个区间中有多对“相邻素数”都是间距最小的，则选择其中C1+C2最小的一对。

（2）找到一对“相邻素数”D1和D2（L ≤ D1 < D2 ≤ U），使得D2-D1最大。如果在这个区间中有多对“相邻素数”都是间距最大的，则选择其中D1+D2最小的一对。

注意：在指定区间内可能没有“相邻素数”，此时请按题目要求输出。

【输入描述】

输入两个正整数L和U，且L < U。

【输出描述】

输出包括两行，第一行为区间内间距最小的“相邻素数”（数值小的在前，数值大的在后，中间为空格），第二行为区间内间距最大的“相邻素数”（数值小的在前，数值大的在后，中间为空格）。

若区间内没有相邻素数，则仅输出-1。

【样例输入1】

2 17
【样例输出1】

2 3
7 11
【样例输入2】

14 17
【样例输出2】

-1
【数据范围】

50%的数据满足1 ≤ L < U ≤ 10^5；

80%的数据满足1 ≤ L < U ≤ 10^6；

100%的数据满足1 ≤ L < U ≤ 10^9,且(U-L) ≤ 10^6；

4.Programming (25Points)
Problem 矩阵查询
【题目描述】

给你一个n*m的矩阵A=(a_ij)，矩阵左上角坐标为(1,1)，右下角坐标为(n,m)。现在有三种对矩阵的 *** 作：

1.A x1 y1 x2 y2 d，表示在左上角坐标为(x1,y1)右下角坐标为(x2,y2)的矩形中所有数加d，即，对于所有(x1 ≤ i ≤ x2,y1≤ j ≤ y2)，执行a_ij=a_ij+d；

2.E x1 x2，表示将第x1行元素与第x2行元素交换；

3.Q x y，表示询问矩阵中坐标为(x,y)处的值为多少，即a_xy的值。

例如，给定矩阵 A=

[1,2,3]

[4,5,6]

[7,8,9]

（看成3*3矩阵，下同）

对于 *** 作“A 1 1 2 2 1”，矩阵A变为：

[2,3,3]

[5,6,6]

[7,8,9]

接着对于 *** 作“E 1 3”，矩阵A变为：

[7,8,9]

[5,6,6]

[2,3,3]

对于 *** 作“Q 3 3”，输出3。

【输入输出格式】

第一行两个整数n，m，表示矩阵有n行m列。

接下来的n行，每行m个数，表示矩阵里元素的初始值。

第n+2行有一个整数q，表示 *** 作的次数。

接下来的q行是对 *** 作的描述。

对于每个询问输出结果。

【样例】

输入：

3 4
1 2 3 4
5 6 7 8
9 10 11 12
5
A 1 1 1 2 -1
E 2 3
A 3 3 3 3 2
Q 2 2
Q 3 1
输出：

10
5
【数据范围】

50%的数据满足1 ≤ n,m ≤10：|a_ij| ≤ 200,000,q ≤ 10；

100%的数据满足1 ≤ n,m ≤100：|a_ij| ≤ 200,000,q ≤ 100,|d| ≤ 1000；

5.Programming (15Points)
Problem 擀面皮
【题目描述】

有一块1x1的方形面团（不考虑面团的厚度），其口感值为0。擀面师傅要将其擀成一个N x M（纵向长N，横向宽M）的面皮。师傅的擀面手法娴熟，每次下手，要么横向擀一下（使得横向长度增加1），要么纵向擀一下（使得纵向长度增加1）。此外，当面团（皮）的大小为a x b时，往横向擀一下会使得面的口感值上升H_ab，而往纵向擀一下则会使口感值上升V_ab。

现在，请你来将1x1的面团擀成N x M面皮。显然，从1x1的面团擀成N x M的面皮有多种不同的 *** 作序列可以实现，不同 *** 作序列下得到的最终面皮口感值也可能是不同的。请问最终得到的N x M面皮，口感值最高可为多少？

【输入描述】

第一行两个整数N，M，表示要擀出来面皮的大小（纵向长N，横向宽M）。

接下来有N行，每行M个数。第a行第b列的数值H_ab，表示当面皮大小为a x b时，横向擀一下后，面皮口感的上升值。

再接下来有N行，每行M个数。第a行第b列的数值V_ab，表示当面皮大小为a x b时，纵向擀一下后，面皮口感的上升值。 （0 < N, M < 1000，0 <= H_ab, V_ab <= 1000）

【输出描述】

输出最终得到的N x M面皮的最高的口感值。

【样例输入1】

2 3
1 2 3
4 5 6
11 12 13
14 15 16
【样例输出1】

20
【样例1解释】

一共三种擀面方法：

纵横横：11+4+5=20

横纵横：1+12+5=18

横横纵：1+2+13=16

【样例输入2】

3 3
1 0 2
2 0 2
2 2 0
0 2 2
1 2 1
2 1 2
【样例输出2】

7
【样例2解释】

最优擀面方法为:横(1) + 纵(2) + 纵(2) + 横(2) = 7