2019年藍橋杯第十屆CC++大學B組真題及代碼

1A：組隊（填空5分_手算）

2B：年號字符（填空5分_進制）

3C：數列求值（填空10分_枚舉）

4D：數的分解（填空10分）

5E：迷宮（填空15分）

6F：特別數的和（編程題15分）

解析代碼（分解數字）

7G：完全二叉樹的權值（編程題20分）

解析代碼（二叉樹的數組遍歷）

8H：等差數列（編程題20分）

解析代碼（數論_最大公約數）

9I：后綴表達式（編程題25分）

解析代碼（數學+貪心）

10J：靈能傳輸（編程題25分）

解析代碼（前綴和+貪心）

1A：組隊（填空5分_手算）

題目描述：

作為籃球隊教練，你需要從以下名單中選出 1號位至 5號位各一名球員，
組成球隊的首發陣容。
每位球員擔任 1號位至 5號位時的評分如下表所示。請你計算首發陣容 1
號位至5號位的評分之和最大可能是多少？

注意不能選同一個人，答案：490

2B：年號字符（填空5分_進制）

題目描述：

????????小明用字母 A對應數字 1，B對應 2，以此類推，用 Z對應 26。對于 27以上的數字，小明用兩位或更長位的字符串來對應，例如 AA對應27，AB對應28，AZ對應52，LQ對應329。

請問2019對應的字符串是什么？

題目分析：

????????這題就是類似于一個進制轉換，你可以回想一下十進制轉二進制如何轉換，然后再想想將十進制轉化成26進制，口訣就是除p取余

答案：BYQ


//小明用字母 A對應數字 1，B對應 2，以此類推，用 Z對應 26。對于 27以上的數字，
//小明用兩位或更長位的字符串來對應，例如 AA對應27，AB對應28，AZ對應52，LQ對應329。
//請問2019對應的字符串是什么？		
// AZ = 1 * 26 + 26 = 52。LQ = 12 * 26 + 17
// ZZ = 26 * 26 + 26
#include <iostream>
using namespace std;int main()
{int i = 0;for (char ch = 'A'; ch <= 'Z'; ++ch){i++;cout << i << " " << ch << endl;}cout << 12 * 26 + 17 << endl;cout << 329 / 26 << endl;cout << 26 * 26  << endl; // 676cout << 2019 / 676 << endl; // 2 -> Bcout << 2019 - 2 * 676 << endl; // 667cout << 667 / 26 << endl; // 25 -> Ycout << 667 - 25 * 26 << endl; // 17 -> Q // BYQreturn 0;
}

3C：數列求值（填空10分_枚舉）

題目描述：
給定數列1,1,1,3,5,9,17,…，從第4項開始，每項都是前3項的和。求
第20190324項的最后4位數字。

題目解析：

暴力循環+位數判斷。答案：4659


#include<iostream>
using namespace std;int main()
{int a = 1, b = 1, c = 1, res = 0;for(int i = 4; i <= 20190324; ++i){res = (a + b + c) % 10000;a = b;b = c;c = res;}cout << res << endl; // 答案4659return 0;
}

4D：數的分解（填空10分）

題目描述：
把 2019分解成 3個各不相同的正整數之和，并且要求每個正整數都不包
含數字2和4，一共有多少種不同的分解方法？
注意交換 3個整數的順序被視為同一種方法，例如 1000+1001+18和
1001+1000+18被視為同一種。

答案40785

#include <iostream>
using namespace std;bool have_24(int x)
{while (x){if (x % 10 == 2 || x % 10 == 4)return true;x /= 10;}return false;
}int main()
{int res = 0;for (int i = 1; i < 2019; ++i){if (!have_24(i))for (int j = i + 1; j < 2019; ++j){if (have_24(j))continue;int k = 2019 - i - j;if (!have_24(k) && k > j) // i j k 從小到大++res;}}cout << res << endl; // 答案40785return 0;
}

? ? ? ? 思路：先獲得2021041820210418所有質因數（所以質因數也就一百多個），再通過質因數去組合從而獲得所有的正約數，最后只需在所有的正約數找3個乘積為2021041820210418就行。

答案：2430

#include <iostream>
#include <vector>using namespace std;
#define int long long
#define endl '\n'
// n比較大，會爆因子signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 2021041820210418;vector<int> v;for (int i = 1; i * i <= n; i++) // 得到n的所有約數{if (n % i == 0){v.push_back(i);if (n / i != i)v.push_back(n / i);}}//cout << v.size() << endl;int res = 0;for (auto& a : v) //枚舉一下a b c{for (auto& b : v){for (auto& c : v){if (a * b * c == n)++res;}}}cout << res << endl;return 0;
}
// 答案：2430

5E：迷宮（填空15分）

題目描述：
下圖給出了一個迷宮的平面圖，其中標記為 1 的為障礙，標記為 0 的為可
以通行的地方。
010000
000100
001001
110000
迷宮的入口為左上角，出口為右下角，在迷宮中，只能從一個位置走到這
個它的上、下、左、右四個方向之一。
對于上面的迷宮，從入口開始，可以按DRRURRDDDR 的順序通過迷宮，
一共 10 步。其中 D、U、L、R 分別表示向下、向上、向左、向右走。
對于下面這個更復雜的迷宮（30 行 50 列），請找出一種通過迷宮的方式，
其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案。
請注意在字典序中D<L<R<U。（如果你把以下文字復制到文本文件中，請務
必檢查復制的內容是否與文檔中的一致。在試題目錄下有一個文件 maze.txt，
內容與下面的文本相同）
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

????????題目解析：一道bfs類型的題目，與平常的bfs不同的是，本題要求的走的路徑，所以可以先用bfs計算出相鄰格子距離差值為1的路徑，然后遍歷該路徑，并且一定是要求題目所說的字典序來排序（在bfs中無所謂），在main函數中需要講究先后順序，所以dir數組的順序是‘D’,'U','L','R'，如果滿足相鄰的各自距離為1，那么就將該字母字母加入string ans，然后break跳出，為的是只走一次，因為是一條完整的最短路徑。

答案：

UUUULLRLLLLLLLULLLUUUDUULUUUUUUUUUUUULULULLRLLRRLLUUUULULLLLLLRLLULLUUULLLLRRLRRRRRRRDRDDRRRRLLLLRRDDDRRRRDDRRRDRRLLRLLRLRLLLULULLLLULULUUDDDUULLUULUUDUUUDDUUDDDUDUUUDUULLLLLLLLLUUUUUULL

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
char g[30][50];
int dist[30][50];char dir[] = { 'D', 'L', 'R', 'U' };
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
void bfs()
{memset(dist, -1, sizeof(dist));queue<PII> q;q.push({ 29, 49 });dist[29][49] = 0;while (!q.empty()){PII t = q.front();q.pop();for (int i = 0; i < 4; i++){int a = t.first + dx[i], b = t.second + dy[i];if (a < 0 || a >= 30 || b < 0 || b >= 50 || g[a][b] == '1' || dist[a][b] != -1)continue;q.push({ a, b });dist[a][b] = dist[t.first][t.second] + 1;}}
}int main()
{for (int i = 0; i < 30; i++){cin >> g[i];}bfs();string ans;int x = 0, y = 0;while (x != 29 || y != 49){for (int i = 0; i < 4; i++){int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= 30 || b < 0 || b >= 50 || g[a][b] == '1')continue;if (dist[x][y] == dist[a][b] + 1){ans += dir[i];x = a;y = b;break;}}}cout << ans << endl;return 0;
}

6F：特別數的和（編程題15分）

題目描述：
小明對數位中含有 2、0、1、9 的數字很感興趣（不包括前導 0），在 1 到
40 中這樣的數包括 1、2、9、10 至 32、39 和 40，共 28 個，他們的和是 574。
請問，在 1 到 n 中，所有這樣的數的和是多少？
【輸入格式】
輸入一行包含兩個整數 n。
【輸出格式】
輸出一行，包含一個整數，表示滿足條件的數的和。
【樣例輸入】
40
【樣例輸出】
574
【評測用例規模與約定】
對于 20% 的評測用例，1 ≤ n ≤ 10。
對于 50% 的評測用例，1 ≤ n ≤ 100。
對于 80% 的評測用例，1 ≤ n ≤ 1000。
對于所有評測用例，1 ≤ n ≤ 10000。
【輸出格式】
輸出一個整數代表答案。
【樣例輸入】
7
1 6 5 4 3 2 1

解析代碼（分解數字）

#include <iostream>
using namespace std;bool have_2019(int x)
{while (x){int a = x % 10;if (a == 2 || a == 0 || a == 1 || a == 9)return true;x /= 10;}return false;
}int main()
{int n = 0, sum = 0;cin >> n;for (int i = 1; i <= n; ++i){if (have_2019(i)){sum += i;}}cout << sum << endl;return 0;
}

7G：完全二叉樹的權值（編程題20分）

解析代碼（二叉樹的數組遍歷）

#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
long long arr[N];int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}int maxv = -INF;int depth = 1, res = 1;for (int i = 1; i <= n; i *= 2){long long s = 0; // 完全二叉樹每層的開頭為2^(n-1)，結尾則是 2^n - 1for (int j = i; j <= i * 2 - 1 && j <= n; j++) // j++就是同一層的下一個{s += arr[j];}if (s > maxv){maxv = s;res = depth;}depth++;}cout << res << endl;return 0;
}

8H：等差數列（編程題20分）

題目描述：
????????數學老師給小明出了一道等差數列求和的題目。但是粗心的小明忘記了一部分的數列，只記得其中 N 個整數。現在給出這 N 個整數，小明想知道包含這 N 個整數的最短的等差數列有幾項？

【輸入格式】
輸入的第一行包含一個整數 N。
第二行包含 N 個整數 A 1 ,A 2 ,··· ,A N 。(注意 A 1 ～ A N 并不一定是按等差數
列中的順序給出)

【輸出格式】
輸出一個整數表示答案。

【樣例輸入】
5
2 6 4 10 20

【樣例輸出】
10

【樣例說明】
包含 2、6、4、10、20 的最短的等差數列是 2、4、6、8、10、12、14、16、
18、20。

【評測用例規模與約定】
對于所有評測用例，2 ≤ N ≤ 100000，0 ≤ Ai ≤ 10^9 。

解析代碼（數論_最大公約數）

題目概述：給出一段序列，求出滿足該段序列的最短等差數列的長度

既然要求的是最短的等差數列的長度，那么就要要求公差比較大，那么這個序列就短
那么問題來了：公差怎么取？

????????如果公差取得比較大，那么很有可能就不滿足等差序列這個條件了：比如下面這個例子

2 ?4 ? 8 ?（如果公差取4，那么2->4，就不滿足公差為4，這個性質了->不滿足等差數列）

????????綜上所述：我們要求的是一個數列中滿足題意的最小的公差即可，那么現在的問題就轉為了：如何求上述的特殊公差？

????????根據數據范圍我們可以直到這個算法不能寫O(N^2)。2 ≤ N ≤ 100000（兩層循環會超時）0 ≤ Ai≤ 10^9

????????優化：首先遍歷一遍數組是跑不了了，要做的優化就是求最小的公差那部分，有沒有一種可能，可以用另外一種方式求公差，那就是歐幾里得算法求公約數，為什么可以這樣寫？為說明會聯想到公約數？

????????因為在等差數列中，首項為a1，剩下的數均可表示為a1+nd，那么是不是只需要同時減去a[0]，也就是首項，那么剩下的數均可表示為nd，那么n不同，d一定相同，那么就完美滿足了最大公約數這個性質了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
int main()
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}sort(a, a + n); // 排序是為了讓首項為a[0]int d = 0; // 0與任何數的最大公約數都是它的本身for (int i = 1; i < n; i++){//d = gcd(d, a[i] - a[0]); // 減去首項a1d = __gcd(d, a[i] - a[0]); // 減去首項a1，Linux或另一些編譯器能用，藍橋杯也能，VS2022不能}if (!d)printf("%d\n", n); // 如果公約數為0.那么就證明這時一個常數數列elseprintf("%d\n", (a[n - 1] - a[0]) / d + 1); // 公式return 0;
}

9I：后綴表達式（編程題25分）

題目描述：
給定 N 個加號、M 個減號以及 N + M + 1 個整數 A 1 ,A 2 ,··· ,A N+M+1 ，小
明想知道在所有由這 N 個加號、M 個減號以及 N + M +1 個整數湊出的合法的
后綴表達式中，結果最大的是哪一個？
請你輸出這個最大的結果。
例如使用1 2 3 + -，則 “2 3 + 1 -” 這個后綴表達式結果是 4，是最大的。
【輸入格式】
第一行包含兩個整數 N 和 M。
第二行包含 N + M + 1 個整數 A 1 ,A 2 ,··· ,A N+M+1 。
【輸出格式】
輸出一個整數，代表答案。
【樣例輸入】
1 1
1 2 3
【樣例輸出】
4
【評測用例規模與約定】
對于所有評測用例，0 ≤ N, M ≤ 100000，?10^9 ≤ A i ≤ 10^9 。

解析代碼（數學+貪心）

題目解析：

????????后綴表達式：可以任意添加括號進行優先計算，所以可以把所有的負號，變成只有一個負號，那么就讓負號對應那個最小的值，得到的總和就是最大的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;#define int long long
#define endl '\n'signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 0, m = 0;cin >> n >> m;int k = n + m + 1; // n = k - m - 1vector<int> arr(k);for (int i = 0; i < k; ++i){cin >> arr[i];}int sum = 0;if(m == 0){for (int i = 0; i < k; i++){sum += arr[i];}}else // 有負號，能把負數變為正數{sort(arr.begin(), arr.end());//int index = 0; // 百分之70的分//while (arr[index] < 0 && m--)//{//	sum += -arr[index++];//}//while (m--)//{//	sum -= arr[index++];//}//while(index < k)//{//	sum += arr[index++];//}sum = arr[k - 1] - arr[0]; // 只保留一個減號for (int i = 1; i < k - 1; i++){sum += abs(arr[i]);}}cout << sum << endl;return 0;
}

10J：靈能傳輸（編程題25分）

【樣例輸入】

3
3
5 -2 3
4
0 0 0 0
3
1 2 3
【樣例輸出】
3
0
3
【樣例說明】
對于第一組詢問：
對 2 號高階圣堂武士進行傳輸操作后 a1?= 3，a2 = 2，a3 = 1。答案為 3。
對于第二組詢問：
這一組高階圣堂武士擁有的靈能都正好可以讓他們達到最佳戰斗狀態。

【樣例輸入】
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
【樣例輸出】
5
7
4

解析代碼（前綴和+貪心）

該題實際上要求通過何種靈能傳輸可以使得該序列的最大值最小
而由前綴和可知一個有序的前綴和序列其max(s[i]-s[i-1])的最大值可以達到最小
（關于這個點大家可以畫個圖理解一下）
通過對幾個樣例的觀察可以發現一個規律

1.對于ai有
1.a[i]>0時 a[i-1]=a[i-1]+a[i] 則 s[i-1]= 原來的s[i]
a[i]=a[i]-2*a[i] 則原s[i]= s[i-1] + a[i]
則現s[i]= 現s[i-1] - a[i]= 原s[i]- a[i]=原s[i-1]
a[i+1]=a[i+1]+a[i] 參考上述推導可得 s[i+1]=原s[i+1]

這意味著除了s[0]和s[n]以外1~n的任何s[i]可以進行相互交互從而得到一個有序的序列
而a[i]=s[i]-s[i-1]
也就意味著可以通過交換s[i]的方式得到靈能傳輸后最終結果

        for (int i = 1;i <= n;i++){cin >> a[i];s[i] = s[i - 1] + a[i];}sort(s, s + 1 + n);

如果s[0],s[n]也可以正常交換的話那么這題的推導到這步就可以結束了
我們可以通過直接計算max(s[i]-s[i-1]的值獲得最大值的最小值
但問題在于 s[0],s[n]
即我們最終得到的一個序列并不一定是單調的
所以接下來我們就要通過一系列操作解決不單調序列的問題

2.通過上述分析可以明確想要求得本題的最優解應使得所求序列盡量保持單調
通過畫圖可知一個有兩個拐點的曲線重疊部分最小時單調部分最多
而一個曲線符合下列情況時符合要求：
1.左端點小于右端點即要求s[0]<s[n]

        LL s0 = s[0], sn = s[n];if (s0 > sn)swap(s0, sn);

2.極小值在極大值左邊
該點要求我們在后續選點的時
應s[0]向左取 s[n]向右取因為只有這樣才能取得兩邊的極值

        int l = 0, r = n; // 構造重疊部分最小的序列for (int i = s0; i >= 0; i -= 2){f[l++] = s[i], st[i] = true;}for (int i = sn; i <= n; i += 2){f[r--] = s[i], st[i] = true;}for (int i = 0; i <= n; ++i){if (st[i] == false)f[l++] = s[i];}

這樣以后就可以保證序列為f為重疊部分最小的前綴和序列

        LL res = 0;for (int i = 1;i <= n;i++){res = max(res, abs(f[i] - f[i - 1]));}cout << res << endl;

res即為所求結果，以下為完整代碼。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 3e5 + 10;
#define endl '\n'
//由于a[]可能達到1e9所以需要使用到LL
typedef long long LL;LL a[N];    //用于存放初始靈能值
LL s[N];    //用于存放前綴和
LL f[N];    //用于存放最終的有序序列
bool st[N];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){int n;cin >> n;s[0] = 0;// 注意這一步不要忘了for (int i = 1;i <= n;i++){cin >> a[i];s[i] = s[i - 1] + a[i];}LL s0 = s[0], sn = s[n];if (s0 > sn)swap(s0, sn);sort(s, s + 1 + n);for (int i = 0; i <= n; ++i) // 找到排序后 s0,sn的位置{if (s0 == s[i]){s0 = i;break;}}for (int i = 0; i <= n; ++i){if (sn == s[i]){sn = i;break;}}memset(st, false, sizeof st);int l = 0, r = n; // 構造重疊部分最小的序列for (int i = s0; i >= 0; i -= 2){f[l++] = s[i], st[i] = true;}for (int i = sn; i <= n; i += 2){f[r--] = s[i], st[i] = true;}for (int i = 0; i <= n; ++i){if (st[i] == false)f[l++] = s[i];}LL res = 0;for (int i = 1;i <= n;i++){res = max(res, abs(f[i] - f[i - 1]));}cout << res << endl;}return 0;
}