【备赛冲刺】2021年第十二届蓝桥B组省赛第二场详细题解陆续更新ing
目录
A题:求余
问题描述
在 C/C++/Java/Python 等语言中，使用 % 表示求余，请问 2021%20 的值是多少？思路分析
签到题，直接算就行了
题目代码
你不会以为我要写代码吧？hh
题目答案
1B题:双阶乘
问题描述
一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。
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 <bits/stdc++.h>
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;
} 题目答案
59375C题:格点
问题描述
如果一个点 (x, y) 的两维坐标都是整数，即 x ∈ Z 且 y ∈ Z，则称这个点为一个格点。
如果一个点 (x, y) 的两维坐标都是正数，即x > 0 且 y > 0，则称这个点在第一象限。
请问在第一象限的格点中，有多少个点 (x, y) 的两维坐标乘积不超过 2021。即 x · y ≤ 2021。
提示：建议使用计算机编程解决问题
思路分析
暴力枚举，两层循环判断即可
题目代码
#include <bits/stdc++.h>
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;
}题目答案
15698D题:整数分解
问题描述
将 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 <bits/stdc++.h>
using namespace std;
int main()
{
long long a=1;//会爆int
int b=4*3*2*1;
for(int i=2020;i>=2017;i--)
a=(long long)a*i;//计算中会爆int
printf("%lld",a/b);
return 0;
}
题目答案
691677274345E题:城邦
问题描述
小蓝国是一个水上王国，有 2021 个城邦，依次编号 1 到 2021。
在任意两个城邦之间，都有一座桥直接连接。为了庆祝小蓝国的传统节日。
小蓝国政府准备将一部分桥装饰起来。对于编号为 a 和 b 的两个城邦，
它们之间的桥如果要装饰起来，需要的费用如下计算：
找到 a 和 b 在十进制下所有不同的数位，将数位上的数字求和。
例如，编号为 2021 和 922 两个城邦之间，千位、百位和个位都不同，
将这些数位上的数字加起来是 (2 + 0 + 1) + (0 + 9 + 2) = 14。
注意 922 没有千位，千位看成 0。为了节约开支，小蓝国政府准备只装饰 2020 座桥，
并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。
请问，小蓝国政府至少要花多少费用才能完成装饰。思路分析
关键是需要掌握最小生成树算法！！！有prim和kruskal。prim与dijkstra算法类似比较好写，但这是稀疏图，稠密图（因为点与边呈平方比例）。prim算法时间复杂度就比较高，但是！！这是填空题，使用prim算法只需要算7秒左右。还是可以接受的。要非常非常非常注意的是！！！把邻接矩阵开大一些，博主调试了一个小时发现原来是数组开小了。┭┮﹏┭┮
题目代码
#include <bits/stdc++.h>
//#pragma GCC optimize(3) 这里开不开臭氧都一样需要7秒左右
using namespace std;
const int N=2030,inf=0x3f3f3f3f;
int g[N][N];//邻接矩阵
int d[N];//第i个点到最小生成树集合的最短距离
bool st[N];//第i个点是否确认
int n;
int prim()//prim算法
{
int res=0;
memset(d,0x3f,sizeof d);//开始初始化距离无穷大
for(int i=0;i<n;i++)//n次枚举
{
int t=-1;//先找一个不在集合中的点
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))
t=j;
st[t]=true;
if(i) res+=d[t];//对第一个点特判了一下
for(int j=1;j<=n;j++)//用t点去更新其他点到集合的最短距离
d[j]=min(d[j],g[t][j]);
}
return res;
}
int cal(int i,int j)//处理边权
{
int res=0;
char a[10]={0},b[10]={0};
sprintf(a,"%04d",i);
sprintf(b,"%04d",j);
for(int k=0;k<4;k++)
if(a[k]!=b[k])
res+=(a[k]-'0')+(b[k]-'0');
return res;
}
int main()
{
n=2021;
for(int i=1;i<=n;i++)//对每条边进行处理
for(int j=1;j<=n;j++)
if(i!=j&&!g[i][j])
{
g[i][j]=cal(i,j);
g[j][i]=g[i][j];
}
cout<<prim();//输出最小生成树
return 0;
} 题目答案
4046