【备赛冲刺】第十二届蓝桥省赛第二场B组详细题解陆续更新ing

目录

A题:求余

B题:双阶乘

C题:格点

D题:整数分解

E题:城邦

A题:求余

问题描述

在 C/C++/Java/Python 等语言中，使用 % 表示求余，请问 2021%20 的值是多少？

思路分析

签到题，直接算就行了

题目代码

你不会以为我要写代码吧？hh

题目答案

1

B题:双阶乘

问题描述

一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。n 的双阶乘用 n!! 表示。例如：3!! = 3 × 1 = 3。8!! = 8 × 6 × 4 × 2 = 384。11!! = 11 × 9 × 7 × 5 × 3 × 1 = 10395。请问，2021!! 的最后 5 位（这里指十进制位）是多少？注意：2021!! = 2021 × 2019 × · · · × 5 × 3 × 1。提示：建议使用计算机编程解决问题。

思路分析

枚举相乘就行，注意取模

题目代码

#include using namespace std;int main(){long long sum=1;for(int i=1;i<=2021;i+=2)sum=(sum*i)%100000;//保留后5位cout<<sum;return 0;} 

题目答案

59375

C题:格点

问题描述

如果一个点 (x, y) 的两维坐标都是整数，即 x ∈ Z 且 y ∈ Z，则称这个点为一个格点。如果一个点 (x, y) 的两维坐标都是正数，即x > 0 且 y > 0，则称这个点在第一象限。请问在第一象限的格点中，有多少个点 (x, y) 的两维坐标乘积不超过 2021。即 x · y ≤ 2021。提示：建议使用计算机编程解决问题

思路分析

暴力枚举，两层循环判断即可

题目代码

#include using namespace std;int main(){int res=0;for(int i=1;i<=2021;i++)for(int j=1;j<=2021;j++)if(i*j<=2021)res++;cout<<res;return 0;}

题目答案

15698

D题:整数分解

问题描述

将 3 分解成两个正整数的和，有两种分解方法，分别是 3 = 1 + 2 和3 = 2 + 1。注意顺序不同算不同的方法。将 5 分解成三个正整数的和，有 6 种分解方法。它们是 1+1+3 = 1+2+2 =1 + 3 + 1 = 2 + 1 + 2 = 2 + 2 + 1 = 3 + 1 + 1。请问，将 2021 分解成五个正整数的和，有多少种分解方法？

思路分析

方法有很多，打三层暴力可以，枚举前三个数，后两个数的方案用数学证明即可得出。也可以用dp，dp可能不那么容易理解。这里博主将介绍一种无比巧妙的方法，不仅能解决分解5个数的问题，分解任意数都能解决。这个方法可能大家初中都学过，那就是-------隔板法！！！！

思路：将2021分解为2021个1，那么这2021个1中间就有2020个间隔可以放搁板，而我们要的是分解为5个数，那么放4个隔板即可，总方案为：C

题目代码

#include using namespace std;int main(){long long a=1;//会爆intint b=4*3*2*1;for(int i=2020;i>=2017;i--)a=(long long)a*i;//计算中会爆intprintf("%lld",a/b);return 0;} 

题目答案

691677274345

E题:城邦

问题描述

小蓝国是一个水上王国，有 2021 个城邦，依次编号 1 到 2021。在任意两个城邦之间，都有一座桥直接连接。为了庆祝小蓝国的传统节日。小蓝国政府准备将一部分桥装饰起来。对于编号为 a 和 b 的两个城邦，它们之间的桥如果要装饰起来，需要的费用如下计算：找到 a 和 b 在十进制下所有不同的数位，将数位上的数字求和。例如，编号为 2021 和 922 两个城邦之间，千位、百位和个位都不同，将这些数位上的数字加起来是 (2 + 0 + 1) + (0 + 9 + 2) = 14。注意 922 没有千位，千位看成 0。为了节约开支，小蓝国政府准备只装饰 2020 座桥，并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。请问，小蓝国政府至少要花多少费用才能完成装饰。

思路分析

关键是需要掌握最小生成树算法