第十二届蓝桥杯2021年C++A组省赛题解
生活随笔
收集整理的這篇文章主要介紹了
第十二届蓝桥杯2021年C++A组省赛题解
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 注
- 考生須知
- 試題A：卡片
- 試題B：直線
- 題解
- 代碼（set + map）
- 試題C：貨物擺放
- 題解
- 代碼
- 試題D：路徑
- 題解
- 代碼
- 試題E：回路計數
- 題解
- 代碼
- 試題F：砝碼稱重
- 題解
- 代碼
- 試題G：異或數列
- 題解
- 代碼
- 試題H：左孩子右兄弟
- 代碼
- 試題I：括號序列
- 題解
- 試題J：分果果
注
官方題解：藍橋杯近 3 年省賽真題講解（C&C++ 大學 A 組）_數據結構 - 藍橋云課
歷屆真題：藍橋杯大賽歷屆真題 - C&C++ 大學 A 組 - 藍橋云課
考生須知
試題A：卡片
#include<bits/stdc++.h> using namespace std;int cnt[15];int main() {for(int i = 0 ; i <= 9 ; i ++ ) cnt[i] = 2021;for(int i = 1 ; ; i ++ ){int k = i;while(k != 0){if( cnt[k % 10] != 0 ) cnt[k % 10] --;else{cout << i - 1;return 0;}k /= 10;}} }試題B：直線
題解
-
注意map是數組類型，按key值查詢value值，因此是二維的，而set是集合，沒有value值，因此是一維的。
- set<pair<double, double> > ss; map<pair<double, double>, int> mp; //必須要有一個int或者其他類型的value值
-
這道題的本質是對所有的直線進行一個去重處理，因此map和set都可以使用，set更簡單點。
-
需要著重注意的是細節類問題
- 每一條直線對應一個唯一的斜率和截距，二者都是double類型的，因此最好直接求其結果，不要交替復用，以免精度不夠。
- 坐標是整數值，k和b都是double值，因此不要忘記強轉類型。
- 討論所有情況中有垂直x軸的直線（斜率不存在），防止除零錯誤（continue）。
代碼（set + map）
//set #include<bits/stdc++.h> using namespace std; set<pair<double, double> > ss;pair<int, int> point[500]; int idx;int main() {for(int i = 0 ; i < 20 ; i ++ )for(int j = 0 ; j < 21 ; j ++ )point[idx ++] = {i, j};for(int i = 0 ; i < idx ; i ++ )for(int j = i + 1 ; j < idx ; j ++ ){int x1 = point[i].first, y1 = point[i].second;int x2 = point[j].first, y2 = point[j].second;if(x2 == x1) continue;double k = (double)(y2 - y1)/(x2 - x1);double b = (double)(x2*y1 - x1*y2)/(x2 - x1);ss.insert({k, b});}cout << ss.size() + 20;return 0; }// map #include<bits/stdc++.h> using namespace std; map<pair<double, double>, int> mp;pair<int, int> point[500]; int idx;int ans = 20;int main() {for(int i = 0 ; i < 20 ; i ++ )for(int j = 0 ; j < 21 ; j ++ )point[idx ++] = {i, j};for(int i = 0 ; i < idx ; i ++ )for(int j = i + 1 ; j < idx ; j ++ ){int x1 = point[i].first, y1 = point[i].second;int x2 = point[j].first, y2 = point[j].second;if(x2 == x1) continue;double k = (double)(y2 - y1)/(x2 - x1);double b = (double)(x2*y1 - x1*y2)/(x2 - x1);if(mp[{k, b}] == 0){mp[{k, b}] = 1;ans ++;}}cout << ans;return 0; }試題C：貨物擺放
題解
- 一個數由三個數的乘積組成，求不同乘積方案數。
- 最暴力的辦法應該是三層循環，從1到n遍歷，然后統計i*j*k == n的count。然后數據量太大，考慮優化。
- 首先需要開longlong。
- 然后應該想到沒必要遍歷1到n之間的所有數。
- 應該想到的是不論由幾個數相乘而得，其中的每一個數都必然出自他的因數中。因此可以預處理出其所有因數，然后暴力尋找不同組合。
代碼
#include<bits/stdc++.h> using namespace std;typedef long long ll;vector<ll> vv;ll n = 2021041820210418;ll ans = 0;int main() {for(ll i = 1 ; i < sqrt(n) ; i ++ ){if(n % i == 0){vv.push_back(i);if(n / i != i)vv.push_back(n / i);}}int len = vv.size();for(ll i = 0 ; i < len ; i ++ )for(ll j = 0 ; j < len ; j ++ )for(ll k = 0 ; k < len ; k ++ )if(vv[i] * vv[j] * vv[k] == n) ans ++;cout << ans;return 0; }試題D：路徑
題解
- dijkstra算法搜索最短路，鄰接矩陣就可以
- 需要知道 a和b的最小公倍數 = a乘b除以a和b的最大公約數 最大公約數(a, b) = a * b / gcd(a, b) 。
代碼
#include<bits/stdc++.h> using namespace std;const int N = 2022;int g[N][N];int gcd(int x, int y) {return x == 0 ? y : gcd(y % x, x); }int dist[N]; bool st[N];int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 1 ; i <= 2021 ; i ++ ){int t = -1;for(int j = 1 ; j <= 2021 ; j ++ )if(!st[j] && (t == -1 || dist[j] < dist[t]))t = j;st[t] = true;for(int j = 1 ; j <= 2021 ; j ++ )dist[t] = min(dist[t], dist[j] + g[j][t]);}return dist[2021]; }int main() {memset(g, 0x3f, sizeof g);for(int i = 1 ; i <= 2021 ; i ++ )for(int j = i + 1 ; j <= 2021 ; j ++ ){if(abs(i - j) <= 21){g[i][j] = g[j][i] = i * j / gcd(i, j);}}cout << dijkstra();return 0; }試題E：回路計數
題解
同類題目題解見AcWing 91. 最短Hamilton路徑 - AcWing
- 注意：位運算的優先級較低，因此一定要帶括號，或者預先定義一個變量來存儲。
- f[state][j] 表示按state方案走，最終到達j點的所有走法
代碼
//881012367360 //集合表示：f[state][j] 表示按state方案走，最終到達j點的所有走法 // 如state = 0001100101，j = 0，則有6種不同走法，CFGA,CGFA,GCFA,GFCA,FGAC,FCGA。（其中第0~n-1個點由對應的A~Z表示） //屬性：count //初始化：f[1][0] = 1； 表示按state = 000..001時，走到第0個節點的方案是一種，A。（即從0點出發） //結果，要求從0出發回到0的哈夫曼回路，則需要累加從0出發走所有節點一次后最終停留的節點 //🎈如果需要求從任意點出發，最終回到0的哈夫曼回路，則需要初始化所有可出發點（除去0），然后結果只需要f[(1 << 21)][0]即可 // 反向考慮的話，做法與本題相同#include <bits/stdc++.h> using namespace std;const int N = 21, M = 1 << N;bool g[N][N]; long long f[M][N];int main() { for(int i = 1; i <= 21 ; i ++ )for(int j = 1 ; j <= 21 ; j ++ )if(__gcd(i, j) == 1) g[i - 1][j - 1] = true;f[1][0] = 1; for(int i = 1 ; i < M ; i ++ )for(int j = 0 ; j < 21 ; j ++ )if(i >> j & 1)for(int k = 0 ; k < 21 ; k ++ )if(g[k][j] && (i >> k & 1))f[i][j] += f[i - (1 << j)][k];long long res = 0;for(int i = 0 ; i <= 20 ; i ++ )res += f[M - 1][i];cout << res << '\n';return 0; }試題F：砝碼稱重
題解
- 狀態表示f[i, j]
- 集合： 從前i個砝碼中選擇重量恰好為j
- 屬性：是否存在
- 狀態計算與劃分：
- 狀態劃分：每一個砝碼都有三種情況
- 不加入
- 加入到左邊
- 加入到右邊
- 狀態計算：只要當前狀態可由三種前導狀態計算得來，那么當前狀態就是可以實現的，即當前重量的組合是存在的，置為1即可
- 狀態劃分：每一個砝碼都有三種情況
- 初始化：dp[0] = 1，表示0重量是可以測得的，其他所有狀態均由此轉化而來。
- 結果：前n個砝碼中，可以拼湊出的不同重量的種類數。即從1到m（總重）統計可以拼湊重量數。
代碼
#include<bits/stdc++.h> using namespace std;const int N = 100010;int n, m; int w[105]; int dp[100010];int main() {cin >> n;for(int i = 1; i <= n ; i ++ ){cin >> w[i];m += w[i];}dp[0] = 1;for(int i = 1 ; i <= n ; i ++ )for(int j = m ; j >= 0 ; j -- ){dp[j] = dp[j] || dp[abs(j - w[i])];if(j + w[i] <= m) dp[j] = dp[j] || dp[j + w[i]];}int ans = 0;for(int i = 1 ; i <= m ; i ++ )ans += dp[i];cout << ans;return 0; }試題G：異或數列
題解
- **當從X1⊕X2⊕X3⊕……⊕Xn = 0 的時候，必定是平局。**證明如下：
- 假設最終兩位的數是a和b，那么a⊕b = X1⊕X2⊕X3⊕……⊕Xn = 0， 二者異或為0，說明二者相等，即平局。
- 然后從高位到低位依次判斷，直至分出勝負，決策如下：
- one表示當前位1的個數，zero表示當前位0的個數，one + zero = n。即n個數的某一位要么是1要么是0。
| 偶數 | 隨便 | 下一位做決定 |
| 1 | 隨便 | 先手勝利 |
| 大于1的奇數 | 偶數 | 先手勝利 |
| 大于1的奇數 | 奇數 | 后手勝利 |
- 有關后手勝利的解釋：后手的人一定會優先使用0，最終先手的人無0可用，只能用1，而被迫做出對自己不利的選擇，輸掉回合。
代碼
#include <iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 2e5 + 10;int main() {int T;cin >> T;while(T -- ){int n;int a[N];cin >> n;int sum = 0;for(int i = 0 ; i < n ; i ++ ){cin >> a[i];sum ^= a[i];}if(sum == 0){puts("0");continue;}for(int j = 20 ; j >= 0 ; j -- ){int one = 0, zero = 0;for(int i = 0 ; i < n ; i ++ ){if(a[i] >> j & 1) one ++;else zero ++;}if(one % 2 == 1){if(zero % 2 == 1 && one != 1) puts("-1");else puts("1");break;}}}return 0; }試題H：左孩子右兄弟
代碼
#include <iostream> #include<algorithm> #include<cstring> using namespace std;const int N = 1e5 + 10;int n; int h[N], e[N], ne[N], idx, s[N]; int dp[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++; }void dfs(int u, int far) {int ans = 0;for(int i = h[u] ; i != -1 ; i = ne[i]){int j = e[i];if(j == far) continue;dfs(j, u);ans = max(ans, dp[j] + 1);}//尋找兄弟節點需要注意細節問題 //1.根節點：0 //2.一層節點：父節點出邊數 - 1 //3.其他節點：父節點出邊數 - 2 //ps：為何減2？（父節點的父節點也算父節點的出邊） int cnt = 0;if(far)for(int i = h[far] ; i != -1 ; i = ne[i] )if(e[i] > far && e[i] != u) cnt ++;dp[u] = ans + cnt; }int main() { memset(h, -1, sizeof h);cin >> n;for(int i = 2 ; i <= n ; i ++ ){int a;cin >> a;add(i, a), add(a, i);}dfs(1, 0);cout << dp[1] << '\n';return 0; }試題I：括號序列
題解
詳細講解見：AcWing 3420. 括號序列 - AcWing
- 一個括號序列合法的兩個條件
- 左右括號數量相同。
- 任意前綴中左括號數不小于右括號數。
試題J：分果果
總結
以上是生活随笔為你收集整理的第十二届蓝桥杯2021年C++A组省赛题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 移动端H5开发基础
- 下一篇： 极客日报第 73 期：Twitter 正