2021年第⼗⼆届蓝桥杯CC++A 组题解
A 卡⽚
问题描述
⼩蓝有许多张卡⽚，每张卡⽚上的数字都是0到9。他想从1开始拼正整数，每拼⼀个数，卡⽚就保存起来，不能再拼其他数。现在他⼿⾥的卡⽚0到9各有2021张，他想知道⾃⼰能从1拼到多少？
思路
对于每⼀个能拼的数x，统计x的每⼀位分别是什么，让x从1开始增加，直到需要⽤的某⼀卡⽚数量为0为⽌。模拟即可。代码
答案
3181
B 直线
问题描述
⼆维平⾯给出20×21个点，它们能构成多少条不同的直线？
思路
两点构成⼀直线，因此，枚举所有的点对，420个点共构成419+418+417+……+1对，即（1+419）×419÷2=87990对。除去这87990条直线中重复的直线，就是正确答案。
数据结构set具有去重的功能，因此我们可以⽤set存储结构体node，node表⽰的是直线⼀般式的三个参数，即ax+by+c=0中的a，b，c。不⽤点斜式是因为计算斜率k会带来较⼤误差。
当然，a，b，c⼀定是互素的，即gcd(a,b,c)==1，才能保证直线不重复。直接除以三个数绝对值的gcd把三元组化为最简形式即可。最后输出set.pair()。
推导 1. #include <iostream > 2. #include <algorithm > 3. using namespace std ; 4. int card [10]; 5. int main () 6. { 7. for (int i = 0; i <= 9; i ++)card [i ] = 2021; 8. bool flag = true ; 9. int num = 1; 10. for (num = 1; flag ; num ++) { 11. int x = num ; 12. while (x ) { 13. int cur = x % 10; 14. if (card [cur ])card [cur ]--; 15. else { flag = false ; break ; } 16. x /= 10; 17. } 18. } 19. cout << num - 2 << endl ; 20. return 0; 21. }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
点p1(x1,y1)，点p2(x2,y2)，斜率k=(y1-y2)/(x1-x2)。点斜式⽅程y-y1=k(x-x1)，即(y-y1)×(x1-x2)=(y1-y2)×(x-x1)，得yx1-x1y1-yx2+x2y1=xy1-xy2-x1y1+x1y2，故(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0。
其中a=y1-y2，b=x2-x1，c=x1y2-x2y1。
如果插⼊的类型是⾃定义的，不是基本类型，需要重载<；运算符，给⾃定义类型⼀个排序准则。
以上的做法是为了完全避免精度问题造成的影响，才将点斜式转化为⼀般式表⽰，否则答案将会千奇百怪。
代码
答案
40257
C 货物摆放
题⽬描述
有n箱货物，长宽⾼的⽅向上分别堆L、W、H的货物，满⾜n=L×W×H。给定n=2021041820210418，总共有多少种堆放货物的⽅案？
思路 1. #include <iostream > 2. #include <algorithm > 3. #include <set > 4. using namespace std ; 5. struct node1 { 6. int a , b , c ; 7. friend bool operator < (const node1 &A , const node1 &B )
{ 8. if (A .a == B .a )return A .b == B .b ? A .c < B .c : A .b < B .b ; 9. return A .a < B .a ; 10. } 11. }line [87991]; 12. struct node2 { 13. int x , y ; 14. }point [421]; 15. set <node1> s ; 16. int gcd (int a , int b ) { 17. return b == 0 ? a : gcd (b , a %b ); 18. } 19. int main () 20. { 21. int cnt = 0; 22. for (int i = 0; i < 20; i ++) { 23. for (int j = 0; j < 21; j ++) { 24. point [cnt ++] = { i ,j }; 25. } 26. } 27. for (int i = 0; i < cnt ; i ++) { 28. for (int j = i + 1; j < cnt ; j ++) { 29. int a = point [i ].y - point [j ].y ; 30. int b = point [j ].x - point [i ].x ; 31. int c = point [i ].x *point [j ].y - point [j ].x *point [i ].y ; 32. int GCD = gcd (abs (a ), gcd (abs (b ), abs (c ))); 33. a /= GCD , b /= GCD , c /= GCD ; 34. s .insert ({ a ,b ,c }); 35. } 36. } 37. cout << s .size () << endl ; 38. return 0; 39. }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
先求n的所有因数。已知所有分解出的因数，再让L分别取这些因数，计算每⼀个L取得的因数所对应的W×H，即n/L。因此，只需要再计算n/L的所有因数，并按照W与H的不同位置来求得W×H的所有取值⽅案，就可以对应到每⼀个L取得的因数。累加即得答案。代码
答案
2430
D 路径
问题描述
两结点数字绝对值之差⼩于等于21有边，边权为两数的最⼩公倍数。计算结点1到2021的最短路径长度。
思路
先模拟建图，可以⽤静态邻接表。
解法⼀：暴⼒跑最短路弗洛伊德算法
⽤时17秒。测得本机在⼀秒内可以完成的计算量为4.87×10^8。
代码⼀1. #include <iostream > 2. #include <algorithm > 3. #define int long long 4. using namespace std ; 5. int n = 2021041820210418; 6. int ans [100000]; 7. int cal (int x ) { 8. int t = 0; 9. for (int i = 1; i *i <= x ; i ++) { 10. if (x %i == 0) { 11. if (i *i == x )t ++; 12. else t += 2; 13. } 14. } 15. return t ; 16. } 17. signed main () 18. { 19. int cnt = 0; 20. for (int i = 1; i *i <= n ; i ++) { 21. if (n %i == 0) { 22. if (i *i == n )ans [++cnt ] = i ; 23. else ans [++cnt ] = i , ans [++cnt ] = n / i ; 24. } 25. } 26. int res = 0; 27. for (int i = 1; i <= cnt ; i ++) { 28. res += cal (ans [i ]); 29. } 30. cout << res << endl ; 31. return 0; 32. }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
解法⼆：线性DP
状态表⽰d[i]：从结点1到i的所有路径
集合划分：所有能从i的上⼀个结点j转移到结点i的路径，且j的取值范围是i-21到i-1，且j>=1。
属性：最⼩值
状态计算：d[i]=min(d[i],d[j]+g[i][j])
初始化：d[1]=0
代码⼆3. #define inf 0x3f3f3f3f 4. using namespace std ; 5. int g [2022][2022]; 6. int gcd (int a , int b ) { 7. return b == 0 ? a : gcd (b , a %b ); 8. } 9. int lcm (int a , int b ) { 10. return a *b / gcd (a , b ); 11. } 12. int main () 13. { 14. for (int i = 1; i <= 2021; i ++) { 15. for (int j = i + 1; j <= 2021; j ++) { 16. if (abs (i - j ) <= 21)g [i ][j ] = g [j ][i ] = lcm (i , j ); 17. else g [i ][j ] = g [j ][i ] = inf ; 18. } 19. } 20. for (int k = 1; k <= 2021; k ++) { 21. for (int i = 1; i <= 2021; i ++) { 22. for (int j = 1; j <= 2021; j ++) { 23. if (g [i ][k ] + g [k ][j ] < g [i ][j ]) { 24. g [i ][j ] = g [i ][k ] + g [k ][j ]; 25. } 26. } 27. } 28. } 29. cout << g [1][2021] << endl ; 30. return 0; 31. }
3
4
5
6
7
8
cstring转为int9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
答案
10266837
E 回路计数
题⽬描述
编号从1到21有21个结点，若两结点上的数互质，则两结点间存在⼀条⽆向边。初始时⼩蓝在第⼀个结点，若要恰好访问每个结点⼀次，并最终返回第⼀个结点，问存在多少种不同的访问⽅案？
思路
求最短哈密顿回路，需要⽤状态压缩DP计算。
分别重新编号为0到20，转化为标准哈密顿模型。
状态表⽰f[i][j]：所有从起点0⾛到终点j，⾛过的所有点对应的状态压缩表⽰为i的所有路径。
属性：从0到j的所有路径的数量
集合划分：根据倒数第⼆个点是哪个点来分类，即最后⼀步是从第k个点⾛到第j个点，且k可能为除j之外的任意⼀个点。
状态计算：f[i][j]=Σf[i-(1<<j)][k]
转移条件：状态i的第j位已经⾛到，i-(1<<j)这⼀状态的第k位已经⾛到，且从k到j的路径存在。
初始化：f[1][0]=1
结果：可能最终是从编号1到20的任意⼀个结点返回的0结点。
代码 3. #include <cstring > 4. using namespace std ; 5. int g [2022][2022]; 6. int gcd (int a , int b ) { 7. return b == 0 ? a : gcd (b , a %b ); 8. } 9. int lcm (int a , int b ) { 10. return a *b / gcd (a , b ); 11. } 12. int d [2022]; 13. int main () 14. { 15. for (int i = 1; i <= 2021; i ++) { 16. for (int j = i - 1; j >= i - 21 && j >= 1; j --) { 17. g [j ][i ] = lcm (i , j ); 18. } 19. } 20. memset (d , 0x3f , sizeof (d )); 21. d [1] = 0; 22. for (int i = 1; i <= 2021; i ++) { 23. for (int j = i - 1; j >= i - 21 && j >= 1; j --) { 24. d [i ] = min (d [i ], d [j ] + g [j ][i ]); 25. } 26. } 27. cout << d [2021] << endl ; 28. return 0; 29. }
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论