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

1A：空間（填空5分_單位轉換）

2B：卡片（填空5分_模擬）

3C：直線（填空10分_數學+排序）

4D：貨物擺放（填空10分_質因數）

5E：路徑（填空15分_最短路）

6F：時間顯示（編程題15分）

解析代碼（模擬）

7G：砝碼稱重（編程題20分）

解析代碼（01背包dp）

8H：楊輝三角形（編程題20分）

解析代碼（找規律）

9I：雙向排序（編程題25分）（待續）

10J：括號序列（編程題25分）（待續）

1A：空間（填空5分_單位轉換）

答案：67108864


#include <iostream>
using namespace std;int main()
{// A題：256MB存多少個32位二進制整數(4bit)// 256MB = 256 * 1024 KB = 256 * 1024 * 1024 B = 256 * 1024 * 1024 * 8 bitcout << 256 * 1024 * 1024 * 8 / 32 << endl;cout << 256 * 1024 * 1024 / 4 << endl;return 0;
}
// 答案67108864

2B：卡片（填空5分_模擬）

答案：3181



#include <iostream>
#include <vector>
using namespace std;vector<int> arr(10, 2021);bool chick(int x)
{while (x){int tmp = x % 10;if (--arr[tmp] < 0)return false;x /= 10;}return true;
}int main()
{for (int i = 1; ; ++i){if (!chick(i)) // 如果拼不出來{cout << i - 1 << endl;return 0;}}return 0;
}
// 答案3181

3C：直線（填空10分_數學+排序）

答案：40257


// C：直線
// 大致思路：依次枚舉各個點，每兩個點生成對應的斜率和截距。最后看有多少個不同的組合，即有多少條不同的直線
// 注意事項：類型為double的兩個數值a和b，即使數值相同，對應的double值也有可能不同，
// 故在cpp中比較兩個double值應判斷其abs之差是否在很小的一個范圍之內，例如1e-8
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 200000; // 直線的最大數
int n = 0;
struct Line
{double k;double b;// 結構體內嵌排序函數// 直接寫比較函數是裸的len表示當前的值，如果len<a.len，那么就是從小到大排序。// 括號中的const表示參數a對象不會被修改，最后的const表明調用函數對象不會被修改// sort默認為從小到大排序，優先隊列默認為從大到小。bool operator < (const Line& t) const  //重載<操作符。可以對兩個node使用<操作符進行比較{if (k != t.k)  // k不同的話，k小的在前return k < t.k;return b < t.b; // k相同的話，b小的在前}
}l[N];int main()
{//枚舉一下所有的點對for (int x1 = 0; x1 < 20; ++x1){for (int y1 = 0; y1 < 21; ++y1){for (int x2 = 0; x2 < 20; ++x2){for (int y2 = 0; y2 < 21; ++y2){if (x1 != x2)//避免斜率不存在的情況，總共20條豎線{double k = (double)(y2 - y1) / (x2 - x1);double b = y2 - k * x2;l[n++] = { k,b }; // 存數對}}}}}sort(l, l + n);int res = 1;for (int i = 1; i < n; ++i) // 找出截率和斜率不等的就是不同數{if (fabs(l[i].k - l[i - 1].k) > 1e-8 || fabs(l[i].b - l[i - 1].b) > 1e-8)++res;}cout << res + 20 << endl; // 加上不存在斜率的20條豎線return 0;
}
// 答案40257

4D：貨物擺放（填空10分_質因數）

? ? ? ? 思路：先獲得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分_最短路）

求最短路的問題，答案是1026837