2019年藍橋杯第十屆軟件類省賽

C/C++ 大 學 A 組

試題 A: 平方和

本題總分：5 分

【問題描述】

小明對數位中含有 2、0、1、9 的數字很感興趣，在 1 到 40 中這樣的數包括 1、2、9、10 至 32、39 和 40，共 28 個，他們的和是 574，平方和是 14362。注意，平方和是指將每個數分別平方后求和。

請問，在 1 到 2019 中，所有這樣的數的平方和是多少？

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一 個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

提示：如果你編寫程序計算，發現結果是負的，請仔細檢查自己的程序， 不要懷疑考場的編程軟件。

試題 B: 數列求值

本題總分：5 分

【問題描述】

給定數列 1, 1, 1, 3, 5, 9, 17, …，從第 4 項開始，每項都是前 3 項的和。求

第 20190324 項的最后 4 位數字。

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個 4 位整數(提示：答案的千位不為 0)，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

試題 C: 最大降雨量

本題總分：10 分

【問題描述】

由于沙之國長年干旱，法師小明準備施展自己的一個神秘法術來求雨。

這個法術需要用到他手中的 49 張法術符，上面分別寫著 1 至 49 這 49 個

數字。法術一共持續 7 周，每天小明都要使用一張法術符，法術符不能重復使用。

每周，小明施展法術產生的能量為這周 7 張法術符上數字的中位數。法術

施展完 7 周后，求雨將獲得成功，降雨量為 7 周能量的中位數。

由于干旱太久，小明希望這次求雨的降雨量盡可能大，請大最大值是多少？

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一 個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

試題 D: 迷宮

本題總分：10 分

【問題描述】

下圖給出了一個迷宮的平面圖，其中標記為 1 的為障礙，標記為 0 的為可以通行的地方。

010000

000100

001001

110000

迷宮的入口為左上角，出口為右下角，在迷宮中，只能從一個位置走到這 個它的上、下、左、右四個方向之一。

對于上面的迷宮，從入口開始，可以按DRRURRDDDR 的順序通過迷宮， 一共 10 步。其中 D、U、L、R 分別表示向下、向上、向左、向右走。

對于下面這個更復雜的迷宮(30 行 50 列)，請找出一種通過迷宮的方式，其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案。請注意在字典序中D

01010101001011001001010110010110100100001000101010

00001000100000101010010000100000001001100110100101

01111011010010001000001101001011100011000000010000

01000000001010100011010000101000001010101011001011

00011111000000101000010010100010100000101100000000

11001000110101000010101100011010011010101011110111

00011011010101001001001010000001000101001110000000

10100000101000100110101010111110011000010000111010

00111000001010100001100010000001000101001100001001

11000110100001110010001001010101010101010001101000

00010000100100000101001010101110100010101010000101

11100100101001001000010000010101010100100100010100

00000010000000101011001111010001100000101010100011

10101010011100001000011000010110011110110100001000

10101010100001101010100101000010100000111011101001

10000000101100010000101100101101001011100000000100

10101001000000010100100001000100000100011110101001

00101001010101101001010100011010101101110000110101

11001010000100001100000010100101000001000111000010

00001000110000110101101000000100101001001000011101

10100101000101000000001110110010110101101010100001

00101000010000110101010000100010001001000100010101

10100001000110010001000010101001010101011111010010

00000100101000000110010100101001000001000000000010

11010000001001110111001001000011101001011011101000

00000110100010001000100000001000011101000000110011

10101000101000100010001111100010101001010000001000

10000010100101001010110000000100101010001011101000

00111100001000010000000110111000000001000000001011

10000001100111010111010001000110111010101101111000

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一 個字符串，包含四種字母 D、U、L、R，在提交答案時只填寫這個字符串，填寫多余的內容將無法得分。

試題 E: RSA 解密

本題總分：15 分

【問題描述】

RSA 是一種經典的加密算法。它的基本加密過程如下。

首先生成兩個質數 p, q，令 n = p · q，設 d 與 (p ? 1) · (q ? 1) 互質，則可找到 e 使得 d · e 除 (p ? 1) · (q ? 1) 的余數為 1。

n, d, e 組成了私鑰，n, d 組成了公鑰。

當使用公鑰加密一個整數 X 時(小于 n)，計算 C = Xd mod n，則 C 是加密后的密文。

當收到密文 C 時，可使用私鑰解開，計算公式為 X = Ce mod n。例如，當 p = 5, q = 11, d = 3 時，n = 55, e = 27。

若加密數字 24，得 243 mod 55 = 19。解密數字 19，得 1927 mod 55 = 24。

現在你知道公鑰中 n = 1001733993063167141, d = 212353，同時你截獲了別人發送的密文 C = 20190324，請問，原文是多少？

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一 個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

試題 F: 完全二叉樹的權值

時間限制: 1.0s內存限制: 256.0MB本題總分：15 分

【問題描述】

給定一棵包含 N 個節點的完全二叉樹，樹上每個節點都有一個權值，按從上到下、從左到右的順序依次是 A1, A2, · · · AN，如下圖所示：

現在小明要把相同深度的節點的權值加在一起，他想知道哪個深度的節點權值之和最大？如果有多個深度的權值和同為最大，請你輸出其中最小的深度。

注：根的深度是 1。

【輸入格式】

第一行包含一個整數 N。

第二行包含 N 個整數 A1, A2, · · · AN 。

【輸出格式】

輸出一個整數代表答案。

【樣例輸入】

7

1 6 5 4 3 2 1

【樣例輸出】

2

【評測用例規模與約定】

對于所有評測用例，1 ≤ N ≤ 100000，?100000 ≤ Ai ≤ 100000。

試題 G: 外賣店優先級

時間限制: 1.0s內存限制: 256.0MB本題總分：20 分

【問題描述】

“飽了么”外賣系統中維護著 N 家外賣店，編號 1 ～ N。每家外賣店都有一個優先級，初始時 (0 時刻) 優先級都為 0。

每經過 1 個時間單位，如果外賣店沒有訂單，則優先級會減少 1，最低減到 0；而如果外賣店有訂單，則優先級不減反加，每有一單優先級加 2。

如果某家外賣店某時刻優先級大于 5，則會被系統加入優先緩存中；如果優先級小于等于 3，則會被清除出優先緩存。

給定 T 時刻以內的 M 條訂單信息，請你計算 T 時刻時有多少外賣店在優先緩存中。

【輸入格式】

第一行包含 3 個整數 N、M 和 T 。

以下 M 行每行包含兩個整數 ts 和 id，表示 ts 時刻編號 id 的外賣店收到一個訂單。

【輸出格式】

輸出一個整數代表答案。

【樣例輸入】

2 6 6

1 1

5 2

3 1

6 2

2 1

6 2

【樣例輸出】

1

【樣例解釋】

6 時刻時，1 號店優先級降到 3，被移除出優先緩存；2 號店優先級升到 6， 加入優先緩存。所以是有 1 家店 (2 號) 在優先緩存中。

【評測用例規模與約定】

對于 80% 的評測用例，1 ≤ N, M, T ≤ 10000。

對于所有評測用例，1 ≤ N, M, T ≤ 100000，1 ≤ ts ≤ T ，1 ≤ id ≤ N。

試題 H: 修改數組

時間限制: 1.0s內存限制: 256.0MB本題總分：20 分

【問題描述】

給定一個長度為 N 的數組 A = [A1, A2, · · · AN]，數組中有可能有重復出現的整數。

現在小明要按以下方法將其修改為沒有重復整數的數組。小明會依次修改

A2, A3, · · · , AN。

當修改 Ai 時，小明會檢查 Ai 是否在 A1 ～ Ai?1 中出現過。如果出現過，則小明會給 Ai 加上 1 ；如果新的 Ai 仍在之前出現過，小明會持續給 Ai 加 1 ，直到 Ai 沒有在 A1 ～ Ai?1 中出現過。

當 AN 也經過上述修改之后，顯然 A 數組中就沒有重復的整數了。現在給定初始的 A 數組，請你計算出最終的 A 數組。

【輸入格式】

第一行包含一個整數 N。

第二行包含 N 個整數 A1, A2, · · · , AN 。

【輸出格式】

輸出 N 個整數，依次是最終的 A1, A2, · · · , AN。

【樣例輸入】

5

2 1 1 3 4

【樣例輸出】

2 1 3 4 5

【評測用例規模與約定】

對于 80% 的評測用例，1 ≤ N ≤ 10000。

對于所有評測用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。

試題 I: 糖果

時間限制: 1.0s內存限制: 256.0MB本題總分：25 分

【問題描述】

糖果店的老板一共有 M 種口味的糖果出售。為了方便描述，我們將 M 種口味編號 1 ～ M。

小明希望能品嘗到所有口味的糖果。遺憾的是老板并不單獨出售糖果，而 是 K 顆一包整包出售。

幸好糖果包裝上注明了其中 K 顆糖果的口味，所以小明可以在買之前就知道每包內的糖果口味。

給定 N 包糖果，請你計算小明最少買幾包，就可以品嘗到所有口味的糖果。

【輸入格式】

第一行包含三個整數 N、M 和 K。

接下來 N 行每行 K 這整數 T1, T2, · · · , TK，代表一包糖果的口味。

【輸出格式】

一個整數表示答案。如果小明無法品嘗所有口味，輸出 ?1。

【樣例輸入】

6 5 3

1 1 2

1 2 3

1 1 3

2 3 5

5 4 2

5 1 2

【樣例輸出】

2

【評測用例規模與約定】

對于 30% 的評測用例，1 ≤ N ≤ 20 。

對于所有評測樣例，1 ≤ N ≤ 100，1 ≤ M ≤ 20，1 ≤ K ≤ 20，1 ≤ Ti ≤ M。

試題 J: 組合數問題

時間限制: 1.0s內存限制: 256.0MB本題總分：25 分

【問題描述】

給 n, m, k， 求 有 多 少 對 (i, j) 滿 足 1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 且 C j ≡

0(mod k)，k 是質數。其中 C j 是組合數，表示從 i 個不同的數中選出 j 個組成

一個集合的方案數。

【輸入格式】

第一行兩個數 t, k，其中 t 代表該測試點包含 t 組詢問，k 的意思與上文中相同。

接下來 t 行每行兩個整數 n, m，表示一組詢問。

【輸出格式】

輸出 t 行，每行一個整數表示對應的答案。由于答案可能很大，請輸出答案除以 109 + 7 的余數。

【樣例輸入】

1 2

3 3

【樣例輸出】

1

【樣例說明】

在所有可能的情況中，只有 C1 = 2 是 2 的倍數。

【樣例輸入】

2 5

4 5

6 7

【樣例輸出】

0

7

【樣例輸入】

3 23

23333333 23333333

233333333 233333333

2333333333 2333333333

【樣例輸出】

851883128

959557926

680723120

【數據規模和約定】

對于所有評測用例，1 ≤ k ≤ 108, 1 ≤ t ≤ 105, 1 ≤ n, m ≤ 1018，且 k 是質數。評測時將使用 10 個評測用例測試你的程序，每個評測用例的限制如下：

評測用例編號tn, mk

1, 2≤ 1≤ 2000≤ 100

3, 4≤ 105≤ 2000≤ 100

5, 6, 7≤ 100≤ 1018≤ 100

8, 9, 10≤ 105≤ 1018≤ 108

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的蓝桥杯大学组python试题_第十届蓝桥杯2019年C/C++ 大学A组省赛试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。