2025年第十六屆藍橋杯省賽C++ 研究生組真題
- 1.說明
- 2.題目A:數位倍數(5分)
- 3.題目B:IPv6(5分)
- 4.題目C:變換數組(10分)
- 5.題目D:最大數字(10分)
- 6.題目E:冷熱數字隊列(15分)
- 7.題目F:01串(15分)
- 8.題目G:甘蔗(20分)
- 9.題目H:原料采購(20分)
1.說明
????真題來源于十六屆藍橋杯賽后直播間,受大風天氣影響的地區(北京、天津和河北)題目應該會變動,我這里參加的實際是河北C++研究生組。考慮到時間關系,將重點放在寫研究生組真題上,但是由于算法實力有限,短時間內還不能夠將所有題解整體出來,因此部分題目只放題目,等之后解出來了再補上題解。如果還對A組題目感興趣的,可以看看2025年第十六屆藍橋杯省賽C++ A組真題,A組題目和研究生組省賽難度差不多。
2.題目A:數位倍數(5分)
【問題描述】
????請問在 1 至 202504(含)中,有多少個數的各個數位之和是 5 的整數倍。例如:5、19、8025 都是這樣的數。
#include <iostream>int main() {int count = 0;for (int i = 1; i <= 202504; ++i) {int sum = 0;int temp = i;while (temp > 0) {sum += temp % 10;temp /= 10;}if (sum % 5 == 0) {count++;}}std::cout << count << std::endl;return 0;
}
3.題目B:IPv6(5分)
【問題描述】
????小藍最近在學習網絡工程相關的知識。他最近學習到,IPv6 地址本質上是一個 128 位的二進制數,而字符串形式的 IPv6 地址是由被冒號分開的八段 16 進制數組成的,例如,下面每行是一個字符串形式的 IPv6 地址:
0000:0000:0000:0000:0000:0000:0000:0000
0000:0001:0000:0000:0000:0001:0000:0000
0000:0001:00ab:0000:0023:0000:0a00:0e00
0000:0000:00ab:0000:000a:0001:0a00:0e00
0000:0000:00ab:0000:0000:0001:0a00:0e00
????其中,每一段最長 4 位,且每一段的前導零都可以去掉(如果 4 位都為 0 需要寫成 0)。
????另外,IPv6 地址還可以將其中相鄰的值為 0 的段合并壓縮起來,用兩個冒號來表示,不過只能壓縮一段。
????例如上述地址最短的壓縮后的形式分別為
::
0:1::1:0:0
0:1:ab:23:0:a00:e00
::ab:0:a:1:a00:e00
0:0:ab::1:a00:e00
????小藍想知道,所有 IPv6 地址的最短壓縮形式的長度的和為多少?由于答案很大(甚至超過了 128 位二進制整數的范圍),請填寫答案時填寫這個總和除以10^9+7的余數。
????這里有一種暴力思路,可以提前計算出每個0-255對應的長度,存入到hash中,然后依使用6重循環拿到結果。
4.題目C:變換數組(10分)
【問題描述】
????輸入一個數組 a ,包含有 n 個元素 a1,a2,…,an。對這個數組進行 m 次變換,每次變換會將數組 a 中的每個元素 ai 轉換為 ai · bitCount(ai)。其中 bitCount(x) 表示數字 x 的二進制表示中 1 出現的次數,例如 bitCount(3)=2,因為 3 的二進制表示為 11,其中 1 出現了兩次。
????請輸出變換之后的數組內容。
【輸入格式】
????輸入的第一行包含一個正整數 n ,表示數組 a 中的元素個數。
????第二行包含 n 個整數 a1,a2,…,an,相鄰整數之間使用一個空格分隔。
????第三行包含一個整數 m,表示變換次數。
【輸出格式】
????輸出一行,包含 n 個整數,相鄰整數之間使用一個空格分隔,表示變換之后得到的數組 a。
【樣例輸入】
2
5 7
2
【樣例說明】
????5=(101)2,7=(111) 2,第一次變化后 a=[10,21]。
????10=(1010) 2,21=(10101) 2,第二次變換后 a=[20,63]。
【樣例輸出】
20 63
5.題目D:最大數字(10分)
【問題描述】
????我們有 n 個連續的整數 1,2,3,…,n,可以自由排列它們的順序。
????然后,我們把這些數字轉換成二進制表示,按照排列順序拼接形成一個新的二進制數。
????我們的目標是讓這個二進制數的值最大,并輸出這個二進制對應的十進制表示。
【輸入格式】
????輸入一行包含一個正整數 n 。
【輸出格式】
????輸出一行包含一個整數表示答案。
【樣例輸入】
3
【樣例輸出】
30
【樣例說明】
????1 的二進制為 1;2 的二進制為 10;3 的二進制為 11;其組成的最大的二進制數字為 11110,對應的十進制數字為 30。
6.題目E:冷熱數字隊列(15分)
????小藍是一名計算機專業的學生,最近他學習了《操作系統》、《數據結構》等課程,他設計了一種名為“冷熱數據隊列”的數據結構,來對數據頁進行管理。
????冷熱數據隊列 q 可以看做由兩個子隊列組成:長度為 n1 的熱數據隊列 q1 和長度為 n2 的冷數據隊列 q2 。當我們需要訪問某個數據頁 p 時:
(1)若 p 不在隊列 q 中(即既不在 q1 中,也不在 q2 中),則加載數據頁 p ,并插入到 q2 的首部。
(2)若 p 已經在隊列 q 中,則將 p 移動至 q1 首部。
(3)當 q1 或 q2 隊列容量不足時,會將其尾部的數據頁淘汰出去。
(4)當 q1 已滿,但 q2 未滿時,從 q1 中淘汰出的數據頁會移動到 q2 首部。
【輸入格式】
????輸入的第一行包含兩個正整數 n1,n2,用一個空格分隔。
????第二行包含一個整數 m ,表示操作次數。
????第三行包含 m 個正整數 v1, v2, …, vm,表示依次訪問到的數據頁的編號,相鄰整數之間使用一個空格分隔。
【輸出格式】
????輸出兩行。
????第一行包含若干個整數,相鄰整數之間使用一個空格分隔,依次表示 q1中的數據頁。
????第二行包含若干個整數,相鄰整數之間使用一個空格分隔,依次表示 q2 中的數據頁。
【樣例輸入】
3 3
10
1 2 3 4 3 2 2 1 3 4
【樣例輸出】
4 3 2
1
【樣例說明】
7.題目F:01串(15分)
【問題描述】
????給定一個由 0,1,2,3…的二進制表示拼接而成的長度無限的 01 串。其前若干位形如 011011100101110111… 。請求出這個串的前 x 位里有多少個 1 。
【輸入格式】
????輸入的第一行包含一個正整數 x 。
【輸出格式】
????輸出一行包含一個整數表示答案。
【樣例輸入】
7
【樣例輸出】
5
8.題目G:甘蔗(20分)
【問題描述】
????小藍種了一排甘蔗,甘蔗共 n 根,第 i 根甘蔗的高度為 ai 。小藍想砍一些甘蔗下來品嘗,但是他有強迫癥,不希望甘蔗的高度顯得亂糟糟的。具體來說,他給出了一個大小為 m 的整數集合 B = {b1,b2,…,bm} ,他希望在砍完甘蔗后,任意兩根相鄰的甘蔗之間的高度差 |ai - ai+1| 都要在這個集合 B 中。小藍想知道他最少需要砍多少根甘蔗(對于高度為 h 的甘蔗,他可以將其砍成 x 高度的甘蔗,x ∈{0,1,2,…,h - 1})。
【輸入格式】
????輸入的第一行包含兩個正整數 n,m,用一個空格分隔。
????第二行包含 n 個正整數 a1,a2,…,an ,相鄰整數之間使用一個空格分隔。
????第三行包含 m 個正整數 b1,b2,…,bm ,相鄰整數之間使用一個空格分隔。
【輸出格式】
????輸出一行包含一個整數表示答案。如果不能滿足條件,輸出 -1 。
【樣例輸入】
6 3
6 7 3 4 9 12
2 3 5
【樣例輸出】
2
【樣例說明】
????其中一種方案:將 a2 砍為 3,再將 a3 砍為 1。
9.題目H:原料采購(20分)
【問題描述】
????小藍負責一家工廠的原料采購。工廠有一輛運貨卡車,其容量為 m 。工廠附近的采購點都在同一條路的同一方向上,一共有 n 個,每個采購點和工廠的距離各不相同。其中,第 i 個采購點的價格為 ai ,庫存為 bi,距離為 ci。卡車每行駛一單位長度的路徑就需要額外花費 o 。(返程沒有花費,你也可以認為 o 實際是行駛兩單位長度的花費)。請計算將卡車裝滿最少需要花費多少錢,如果沒有任何方案可以裝滿請輸出 -1 。
????【輸入格式】【輸出格式】【樣例輸入】【樣例輸出】,因直播沒有給出,歡迎大家在評論區補充(或者后續官方放出來我再補充一下)。這里應該是考察背包問題。
????到這里就結束啦,整理不易,歡迎關注【Jerry說前后端】、點贊并分享,獲取更多前端和算法知識。