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
總結
以上是生活随笔為你收集整理的challenging Programming questions的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： cpp_test
- 下一篇： ALGORITHM IMPORTANT