2025年第十六屆藍橋杯省賽C++ A組真題
- 1.說明
- 2.題目A：尋找質數（5分）
- 3.題目B：黑白棋（5分）
- 4. 題目C：抽獎（10分）
- 5. 題目D：紅黑樹（10分）
- 6. 題目E：黑客（15分）
- 7. 題目F：好串的數目（15分）
- 8. 題目G：地雷陣（20分）
- 9. 題目H：掃地機器人（20分）
1.說明
????真題來源于十六屆藍橋杯賽后直播間，受大風天氣影響的地區（北京、天津和河北）題目應該會變動，我這里參加的實際是河北C++研究生組。考慮到時間關系，將重點放在寫研究生組真題上，所以C++ A組題目主要放題目資料，這里的題目要是想短時間給寫出來還是太有挑戰了，之后如果研究生組的題目看的差不多了再回來補一下A組題目，好像A組題目和研究生組題目難度差不多。
2.題目A：尋找質數（5分）
????如果一個正整數只能被 1 和它本身兩個數整除，就稱為一個質數。最小的幾個質數依次是 2,3,5,7,11,13,···，請問，第 2025 個質數是多少？
#include <iostream>
#include <cmath>// 判斷一個數是否為質數
bool isPrime(int num) {if (num < 2) return false;for (int i = 2; i <= std::sqrt(num); ++i) {if (num % i == 0) return false;}return true;
}int main() {int count = 0;int num = 2;while (true) {if (isPrime(num)) {++count;if (count == 2025) {std::cout << "第 2025 個質數是: " << num << std::endl;break;}}++num;}return 0;
}
3.題目B：黑白棋（5分）
????小藍最近迷上了一款名為“黑白棋填充”的游戲。該游戲在一個方形網格棋盤上進行，其中部分格子已經填有黑色或白色的棋子，而其他格子為空，等待玩家填入棋子。游戲規則是，玩家需要按照以下規則填滿整個棋盤，才能算作勝利：
（1） 黑白棋子數量均等：在每一行和每一列中，黑色棋子和白色棋子的數量必須相等。
（2）相鄰棋子限制：在棋盤的任何一行或一列中，不能有超過兩個相同顏色的棋子連續排列（即不允許出現“黑黑黑”或“白白白”的情況）。
（3）行列唯一性：每一行的棋子排列方式必須是唯一的，不能與棋盤中的任何其他行完全相同。每一列的棋子排列方式必須是唯一的，不能與棋盤中的任何其他列完全相同。行與列之間的棋子排列不作比較，即行可以與列相同，無需滿足行列間的唯一性。
提示：二進制表示法搜索剪枝。100000000000000000001000001100001111。
4. 題目C：抽獎（10分）
????LQ 商場為了回饋廣大用戶，為在此消費的用戶提供了抽獎機會：抽獎機有三個轉輪，每個轉輪上都分布有 n 個數字圖案，標號為 1 ~ n ，按照從 1 到 n 順序轉動，當轉到第 n 個圖案時會從第一個繼續開始。獎項如下：
（1）三個相同的圖案，積分 +200 ；
（2）兩個相同的圖案，積分 +100 ；
（3）三個數字圖案，從左到右連續（例如 1,2,3 ），積分 +200 ；
（4）三個數字圖案，經過順序調整后連續（例如 2,1,3 或 3,2,1 ），積分 +100 ；
????抽獎機處于初始狀態，三個轉輪都處于第一個位置。每次開始抽獎，都會產生三個對應的隨機數 xi1,xi2 ,xi3 ，表示第 j 個轉輪會向后轉動 xij 次停下。下次抽獎時，轉輪會從上一次轉動后的位置開始繼續轉動。
????注意，一次抽獎最多只能獲得一次積分，如果同時命中多個獎項，以積分最大的那個獎項為準。請問，如果執行 m 次抽獎，總積分值是多少？
【輸入格式】
????輸入的第一行包含一個正整數 n，表示轉輪大小。
????第二行包含 n 個正整數 a 1 , a 2 , ? , a n a_1,a_2,\cdots,a_n a1?,a2?,?,an?，依次表示第一個轉輪上的數字圖案，相鄰整數之間使用一個空格分隔。
????第三行包含 n 個正整數 b 1 , b 2 , ? , b n b_1,b_2,\cdots,b_n b1?,b2?,?,bn?，依次表示第二個轉輪上的數字圖案，相鄰整數之間使用一個空格分隔。
????第四行包含 n 個正整數 c 1 , c 2 , ? , c n c_1,c_2,\cdots,c_n c1?,c2?,?,cn?，依次表示第三個轉輪上的數字圖案，相鄰整數之間使用一個空格分隔。
????第五行包含一個整數 m，表示抽獎次數。
????接下來 ( m ) 行，每行包含三個正整數 (xi1,xi2,xi3)，相鄰整數之間使用一個空格分隔。
【輸出格式】
????輸出一行包含一個整數表示答案，即 ( m ) 次抽獎累計獲得的積分的值。
【樣例輸入】
4
3 2 4 1
2 2 2 2
4 3 0 9
3
4 4 4
3 1 1
40 39 2
【樣例輸出】
300
【樣例說明】
????三個轉輪在初始狀態下都在位置 1。
????第一次抽獎，三個轉輪都轉動 4 次，都轉一整圈到達位置 1，三個轉輪上的數字圖案分別是 3、2、4，積分 +100；
????第二次抽獎，第一個轉輪轉動 3 次到達位置 4，第二個轉輪轉動 1 次到達位置 2，第三個轉輪轉動 1 次到達位置 2，三個轉輪上的數字圖案分別是 1、2、3，積分 +200；
????第三次抽獎，第一個轉輪轉動 40 次到達位置 4，第二個轉輪轉動 39 次到達位置 1，第三個轉輪轉動 2 次到達位置 4，三個轉輪上的數字圖案分別是 1、2、9，積分不增加。
????因此總積分為 300。
5. 題目D：紅黑樹（10分）
【問題描述】
????小藍最近學習了紅黑樹，紅黑樹是一種特殊的二叉樹，樹上的結點有兩種類型：紅色結點和黑色結點。
????小藍在腦海中構造出一棵紅黑樹，構造方式如下：
（1）根結點是一個紅色結點；
（2）如果當前結點 curNode 是紅色結點，那么左子結點 curNode.left 是紅色結點，右子結點 curNode.right 是黑色結點；
（3）如果當前結點 curNode 是黑色結點，那么左子結點 curNode.left 是黑色結點，右子結點 curNode.right 是紅色結點；
????此二叉樹前幾層的形態如下圖所示：
【輸入格式】
????輸入的第一行包含一個正整數 ( m )，表示小藍挑選的結點數。
????接下來 ( m ) 行，每行包含兩個正整數 (ni,ki)，用一個空格分隔，表示小藍挑選的結點是第 ni 行（從上往下數）第 ki 個（從左往右數）結點。
【輸出格式】
????輸出 ( m ) 行，每行包含一個字符串，依次表示小藍每次挑選的結點的答案。RED 表示紅色結點，BLACK 表示黑色結點。
【樣例輸入】
2
1 1
2 2
【樣例輸出】
RED
BLACK
6. 題目E：黑客（15分）
【問題描述】
????小藍正在兩臺電腦之間拷貝數據，數據是一個 (n×m) 大小的正整數矩陣，因此總共有 (n×m + 2) 個由空格分開的整數，其中前兩個整數分別為 (n) 和 (m)。然而，有黑客入侵了小藍的電腦，導致這 (n×m + 2) 個正整數的順序被打亂了，小藍想知道最多可能有多少個不同的原矩陣。
????兩個矩陣相同當且僅當它們行數相同、列數分別相同，且每個位置上的數相同。
【輸入格式】
????輸入的第一行包含一個正整數 (n×m + 2)。
????第二行包含 (n×m + 2) 個正整數 (a1,a2,…,an×m + 2)，相鄰整數之間使用一個空格分隔。
【輸出格式】
????輸出一行包含一個整數表示答案。答案可能很大，請輸出答案除以 1000000007 的余數。
【樣例輸入】
2 2 1 4 3 3
【樣例輸出】
24
7. 題目F：好串的數目（15分）
【問題描述】
????對于一個長度為 (n) 的字符串 (s = s0s1…sn-1) 來說，子串的定義是從中選出兩個下標 l,r(0 ≤ l ≤ r ≤n-1)，這之間所有的字符組合起來的一個新的字符串：(s’ = sl…sr) 就是其中一個子串。
????現在給出一個只有數字字符 0~9 組成的數字字符串，小藍想要知道在其所有的子串中，有多少個子串是好串。一個子串是好串，當且僅當它滿足以下兩個條件之一：
（1）單字符子串一定是好串，即當子串長度為 1 時，它總是好串；
（2）長度大于 1 時，可以拆分為兩個連續非遞減子串。
????其中，一個串 (p = p0p1…pn-1) 為連續非遞減子串是指，對于所有 (1≤ i < k)，滿足 (pi = pi-1) 或 (pi = pi-1+1)。即數字串中的每一個數字，要么等于上一個數字，要么等于上一個數字加 1。例如 12233、456 是連續非遞減子串。
【輸入格式】
????輸入一行包含一個字符串 (s)。
【輸出格式】
????輸出一行包含一個整數表示答案，即好串的數目。
【樣例輸入】
12258
【樣例輸出】
12
【樣例說明】
????長度為1的好串：1、2、2、5、8。它們長度都為1，都是好串。
????長度為2的好串：12、22、25、58。12可以分割為1、2兩個連續非遞減子串，其它類似。
????長度為3的好串：122、225。122可以分割為12、2兩個連續非遞減子串；225可以分割為22、5兩個連續非遞減子串。
????長度為4的好串：1225。1225可以分割為122、5兩個連續非遞減子串。
????總計12個好串。
8. 題目G：地雷陣（20分）
【問題描述】
????小藍正在平面直角坐標系中的第一象限里玩一個逃生小游戲，在第一象限中埋有 (n) 顆地雷，第 i 顆地雷的坐標為 (xi, yi)，觸發范圍為以 (xi, yi) 為圓心，半徑為 ri 的圓。一旦小藍走進了圓內就會觸發地雷導致游戲失敗。小藍初始在原點 (0,0) 上，他需要在第一象限內選擇一個方向一直往前走，如果能不觸發任何地雷即可成功通關游戲。他想知道在 [0,π/2] 中均勻隨機選擇一個方向，即在 (0°)（朝向 x 軸正方向）至 90°（朝向 y 軸正方向）之間隨機選擇一個方向，通關游戲的概率是多少？
【輸入格式】
????輸入的第一行包含一個正整數 (n)。
接下來 (n) 行，每行包含三個正整數 (xi, yi)，相鄰整數之間使用一個空格分隔。
【輸出格式】
????輸出一行包含一個實數，四舍五入保留三位小數，表示答案。
【樣例輸入】
2
1 3 1
3 1 1
【樣例輸出】
0.181
9. 題目H：掃地機器人（20分）
【問題描述】
????在一個含有 n 個點 n 條邊的無重邊無自環的連通無向圖中，有一個掃地機器人在執行清掃作業，其中結點 i 的標記 ti ∈{0, 1}，如果為 1，則說明該結點需要進行清掃，掃地機器人在到達這個結點時會順便進行清掃工作。機器人想知道，如果選定任意結點出發，每條邊只能經過一次的話，最多能清掃多少個待清掃結點？
【輸入格式】
????輸入的第一行包含一個正整數 n。
????第二行包含 n 個整數 t1, t2, … , tn，相鄰整數之間使用一個空格分隔。
????接下來 n 行，每行包含兩個正整數 ui, vi，用一個空格分隔，表示結點 ui 和結點 vi 之間有一條邊。
【輸出格式】
????輸出一行包含一個整數表示答案。
【樣例輸入】
9
1 0 1 0 0 1 1 0 1
2 8
2 9
2 5
1 5
1 3
1 4
4 5
4 6
6 7
【樣例輸出】
4
【樣例說明】
????其中一種路線：3 → 1 → 4 → 6 → 7。
????到這里就結束啦，整理不易，歡迎關注【Jerry說前后端】、點贊并分享，獲取更多前端和算法知識。
