• 第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结


    目录

    个人总结

    C/C++ 组真题

    握手问题

    小球反弹

    好数

    R 格式

    宝石组合

    数字接龙

    爬山

    拔河

    ​编辑

    再总结及后续规划


    个人总结

    第一次参加蓝桥杯,大二,以前都在在学技术,没有系统的学过算法。所以,还是花了挺多时间去备战的,因为暑假想找实习,就想拿个奖写简历上。备战了大概一个多月,学了一些基础的算法(dfs bfs 动态规划为主),刷了快200道题吧,但还是因为缺少经验,比赛时有点茫然了,然后大概率是寄了。

    C/C++ 组真题

    握手问题

    这道第一题相对于去年还算是比较简单,排列 + 特殊情况处理即可

    (50 * 49) / 2 - (6*7) / 2 = 1204,答案应该是正确的

    小球反弹

    这个应该是错了哈哈,答案是 1100325199.77,但和这个值挺像的,可惜只看答案。

    前两道题都是数学问题,唉,后悔没有静下心来看第二题了。

    好数

    这道题直接暴力模拟即可,数据量没有很大。

    1. #include
    2. using namespace std;
    3. int N;
    4. int main()
    5. {
    6. cin >> N;
    7. int Count = 0; // 记录总个数
    8. for (int i = 1; i <= N; i++)
    9. {
    10. // 判断某一个数是否是 好数
    11. int n = i; // 用 n 记录 i
    12. int flag = 1; // 1 此时计算的是 i 的奇数位, 0 表示此时计算的是 i 的偶数位
    13. int ret = 1; // 记录当前数否为 好数
    14. while (n > 0)
    15. {
    16. int end = n % 10;
    17. if (flag == 1)
    18. {
    19. if (end % 2 == 0)
    20. {
    21. ret = 0;
    22. break;
    23. }
    24. flag = 0;
    25. }
    26. else // flag = 0
    27. {
    28. if (end % 2 != 0)
    29. {
    30. ret = 0;
    31. break;
    32. }
    33. flag = 1;
    34. }
    35. n /= 10;
    36. }
    37. if (ret == 1) Count++;
    38. }
    39. cout << Count << endl;
    40. return 0;
    41. }

    R 格式

     

    这道题看起来挺简单的,但如果要拿满分的话,需要使用字符串模拟,我直接使用 long long 了,应该能拿 50% 的分。

    long long  50%代码

    1. #include
    2. using namespace std;
    3. double d;
    4. int n;
    5. long long func(int n)
    6. {
    7. long long ret = 1;
    8. while (n--)
    9. {
    10. ret *= 2;
    11. }
    12. return ret;
    13. }
    14. int main()
    15. {
    16. cin >> n >> d;
    17. cout << (long long)(func(n) * d + 0.5) << endl;
    18. return 0;
    19. }

    宝石组合

     这道题没有学过网上的那些公式算法,第一个想到的是暴击解法,时间复杂度O(N^3),但思考了一会,发现是可以用哈希表来优化的,时间复杂度可以降到 O(N^2)。不过貌似依然过不了很多数据,第二个比较麻烦的点就是如果 S 相同的情况下要按字典序排顺序。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. long long N;
    6. long long nums[100010];
    7. long long func(long long a, long long b, long long c = 1)
    8. {
    9. long long Max = max(a, max(b, c));
    10. long long i = 0;
    11. for (i = Max; i >= 0; i += Max)
    12. {
    13. if (i % a == 0 && i % b == 0 && i % c == 0) break;
    14. }
    15. return i;
    16. }
    17. long long get_S(long long a, long long b, long long c)
    18. {
    19. long long tmp = a * b * c * func(a, b ,c);
    20. long long ret = tmp / (func(a, b) * func(a, c) * func(b, c));
    21. return ret;
    22. }
    23. int main()
    24. {
    25. cin >> N;
    26. for (long long i = 1; i <= N; i++) cin >> nums[i];
    27. unordered_map<long long, pair<long long, long long>> hash;
    28. for (long long i = 2; i <= N; i++)
    29. {
    30. for (long long j = i - 1; j >= 1; j--)
    31. hash[nums[i] * nums[j]] = { j, i };
    32. }
    33. long long ret[3] = {100010, 100010, 100010};
    34. long long S = 0;
    35. for (long long i = 1; i <= N; i++)
    36. {
    37. for (auto& e : hash)
    38. {
    39. if (e.second.first != i && e.second.second != i)
    40. {
    41. long long tmp = get_S(nums[i], nums[e.second.first], nums[e.second.second]);
    42. if (tmp > S)
    43. {
    44. S = tmp;
    45. ret[0] = nums[i];
    46. ret[1] = nums[e.second.first];
    47. ret[2] = nums[e.second.second];
    48. }
    49. else if (tmp == S)
    50. {
    51. if (ret[0] > nums[i])
    52. {
    53. ret[0] = nums[i];
    54. ret[1] = nums[e.second.first];
    55. ret[2] = nums[e.second.second];
    56. }
    57. else if (nums[i] == ret[0] && ret[1] > nums[e.second.first])
    58. {
    59. ret[0] = nums[i];
    60. ret[1] = nums[e.second.first];
    61. ret[2] = nums[e.second.second];
    62. }
    63. else if (nums[i] == ret[0] && ret[1] == nums[e.second.first] && ret[2] > nums[e.second.second])
    64. {
    65. ret[0] = nums[i];
    66. ret[1] = nums[e.second.first];
    67. ret[2] = nums[e.second.second];
    68. }
    69. }
    70. }
    71. }
    72. }
    73. cout << ret[0] << " " << ret[1] << " " << ret[2] << endl;
    74. return 0;
    75. }

    数字接龙

    这道题,打眼一看是 dfs ,觉得自己会,就开始做,没想到做到最后,不会判断路径是否交叉,有点懵逼了,就直接将得到的所有可以走完的路径按字典序排序后取了第一个,最后估计还没有直接输出 - 1的人得的分多。还是比赛经验不够,应该先好好看完题再开始写代码的。

    这里就不放我的错代码了,唉,看到正确答案就在自己负责调试的 vector 里,却没有办法去除错错误的答案...

    知乎正确答案:

    1. #include
    2. #include
    3. using namespace std;
    4. const int N = 11;
    5. int a[N][N];
    6. int dt[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
    7. int n, k;
    8. vector<int> path;
    9. vector<int> res;
    10. bool ban[N][N][N][N];
    11. bool vis[N][N];
    12. void dfs(int sx, int sy)
    13. {
    14. if (!res.empty()) return;
    15. if (sx == n - 1 && sy == n - 1)
    16. {
    17. if (path.size() == n * n - 1) res = path;
    18. return;
    19. }
    20. if (path.size() == n * n - 1) return;
    21. for (int i = 0; i < 8; i++)
    22. {
    23. if (!res.empty()) return;
    24. int dx = dt[i][0], dy = dt[i][1];
    25. int x = sx + dx, y = sy + dy;
    26. if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && a[x][y] == (a[sx][sy] + 1) % k)
    27. {
    28. if (dx != 0 && dy != 0 && ban[sx + dx][sy][sx][sy + dy]) continue;
    29. ban[sx][sy][x][y] = ban[x][y][sx][sy] = true;
    30. vis[x][y] = true;
    31. path.push_back(i);
    32. dfs(x, y);
    33. path.pop_back();
    34. vis[x][y] = false;
    35. ban[sx][sy][x][y] = ban[x][y][sx][sy] = false;
    36. }
    37. }
    38. }
    39. int main()
    40. {
    41. scanf("%d%d", &n, &k);
    42. for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);
    43. vis[0][0] = true;
    44. dfs(0, 0);
    45. if (!res.empty())
    46. {
    47. for (auto x : res) printf("%d", x);
    48. }
    49. else
    50. {
    51. puts("-1");
    52. }
    53. return 0;
    54. }

    爬山

     由于上一题浪费了太多时间,这道题也没有认真看,想了一下动态规划,感觉有点复杂,凭感觉写了一下...出来后看了答案才发现是 优先级队列 + 贪心

    这是知乎上的贪心答案,但这个做法对于有的测试用例也是过不了的,我感觉还是应该用动态规划哈哈。

    1. int main()
    2. {
    3. priority_queue<int> heap;
    4. scanf("%d%d%d",&n,&P,&Q);
    5. for(int i=1;i<=n;i++) scanf("%d",&a[i]),heap.push(a[i]);
    6. while(P||Q)
    7. {
    8. auto x=heap.top();
    9. heap.pop();
    10. if(P&&Q)
    11. {
    12. int yl=_sqrt(x);
    13. int y2=x/2;
    14. if(y2<=yl)
    15. {
    16. Q--;
    17. heap.push(y2);
    18. }
    19. else
    20. {
    21. P--;
    22. heap.push(yl);
    23. }
    24. }
    25. else if(P)
    26. {
    27. int yl=_sqrt(x);
    28. P--;
    29. heap.push(yl);
    30. }
    31. else
    32. {
    33. int y2=x/2;
    34. Q--;
    35. heap.push(y2);
    36. }
    37. }
    38. ll res=0;
    39. while(!heap.empty())
    40. {
    41. int x=heap.top();
    42. heap.pop();
    43. res+=x;
    44. }
    45. printf("%lld\n",res);
    46. return 0;
    47. }

    拔河

    这道题看都没看,唉,应该先看一下的......,起码得个暴力分

    标准答案:指针 + 二分

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. typedef long long ll;
    6. const int N = 1003;
    7. int a[N];
    8. int n;
    9. ll s[N];
    10. int main()
    11. {
    12. scanf("%d", &n);
    13. for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
    14. multiset S;
    15. for (int l = 1; l <= n; l++)
    16. {
    17. for (int r = l + 1; r <= n; r++)
    18. {
    19. S.insert(s[r] - s[l]);
    20. }
    21. }
    22. ll res = 0x3f3f3f3f;
    23. for (int r = 1; r < n; r++)
    24. {
    25. for (int l = 0; l < r; l++)
    26. {
    27. ll val = s[r] - s[l];
    28. auto it = S.lower_bound(val);
    29. if (it != S.end())
    30. {
    31. ll ans = abs(*it - val);
    32. res = min(res, ans);
    33. }
    34. if (it != S.begin())
    35. {
    36. it--;
    37. ll ans = abs(*it - val);
    38. res = min(res, ans);
    39. }
    40. }
    41. for (int r2 = r + 1; r2 <= n; r2++)
    42. {
    43. S.erase(S.find(s[r2] - s[r]));
    44. }
    45. }
    46. printf("%lld\n", res);
    47. return 0;
    48. }

    再总结及后续规划

    总结:自己算法还是太菜了(毕竟练习时长只有一个月),本次大概率可能是省二 ~ 省三了,省一的概率不大,不知道大三还有没有机会再打蓝桥杯,那时候应该要实习 / 考研吧。

    接下来的安排,下周六还有一场天梯赛,打完后就要继续学技术了,冲一下暑假的日常实习,到时候就开始佛系做力扣每日一题了,不再花时间集中学算法了,算法竞赛的帮助,对于找开发的工作,有帮助,但最重要的还是技术得学到手,做项目。

  • 相关阅读:
    Flutter macOS 教程之 01 macOS App开发快速入门 (教程含源码)
    C. Johnny and Another Rating Drop(思维+二进制位)
    HarmonyOS元服务实现今天吃什么
    微信视频号的项目玩法,视频号好物分享,只要你会剪辑,就可以去操作
    SpringCloud学习-周阳
    hdu 3549 a flow problem 的多种解法
    20年将投资美国约2000亿美元,三星电子财大气粗的样子真好看
    sql语法复习
    200. 岛屿数量(Java、DFS、岛屿题目)
    [博弈]Swap Game Codeforces1747C
  • 原文地址:https://blog.csdn.net/zyb___/article/details/137747389