2021年软件类第十二届蓝桥杯第二场省赛 python组 A-E题解

文章目录

• 2021年软件类第十二届蓝桥杯第二场省赛 python组 A-E题解
• • 试题 A：求余
  • • 思路
    • 代码
    • 答案
  • 试题 B：双阶乘
  • • 思路
    • 代码
    • 答案
  • 题目 C：格点
  • • 思路
    • 代码
    • 答案
  • 试题 D：整数分解
  • • 思路
    • 代码
    • 答案
  • 试题 E：城邦
  • • 思路
    • 代码
    • 答案

试题 A：求余

思路

这道题也很简单，我们求最后五位，就是%100000，然后双阶乘，实际上就是每隔1个相乘，所以我们直接循环计算即可

代码

答案

59375

题目 C：格点

思路

首先最简单的思路就是5重循环，不过O(n^5)的复杂度，让人望而却步，我也尝试进行一个改进一下范围，但是结果还是不近如意，除非在考试的时候，顶多运行5个小时一定出的来，或者利用C++运行应该会快很多的

好咯，废话不多说，这里讲一下正解，其实呢，这道题可以用隔板的思想

比如说3分为两个数，实际上就是3个小球，一个隔板，有几种放法，3 = 1 + 2,@|@@或者是3 = 2 + 1，@@|@，所以这就是一个组合的问题了，我们可以看到，3个小球有2个空隙（最前面和最后面不算），放一个隔板，就是 C 2 1 C_2^1 C21/span>

所以这样来看，我们的2021分为五个数，就是2021个球放4个隔板，有几种放法，根据上面来看，一共2020个空隙，4个隔板，一共就是 C 2020 4 C_{2020}^4 C20204/span>

代码

答案

694422703815

试题 E：城邦

生成树不唯一（取的边的组合不唯一），当我们赋予了边的权值时，所有边的权值的和也就必然有一个最小值。即最小生成树

知道定义了以后，我们这里用的是克鲁斯卡算法，kruskal的基本算法思想，创建边的数组（i,j,weihgt），按照边的权值排序（贪心），然后，初始化各个顶点作为一个独立的集合（并查集思想），遍历边（贪心）,如果i和j不在同一集合，意味着i,j不连通（并查集），对应的边应当取过来，权值和累加一次，否则如果i和j在同一集合（已经连通），意味着这条边不应取过来…直至取完n-1条边,只剩下一个集合，这个集合包含所有点（连通性）那么最终的权值和一定是最小的（最小权值和）。

代码

答案

4046

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34188 人正在系统学习中

来源：风信子的猫Redamancy