P8741 [蓝桥杯 2021 省 B] 填空问题 题解

题目传送门

欢迎大家指出错误并联系这个蒟蒻

更新日志

• 2023-05-09 23:19 文章完成
• 2023-05-09 23:20 通过审核

试题 A ：空间

【解析】 本题考察计算机存储的基础知识，只要掌握空间存储的换算方法，就能够算出答案。 【程序】

#include <bits/stdc++.h>

using namespace std;

int main()
{
    printf("%d\n",256*8/32*1024*1024);
    return 0;
}

【答案】
$67108864$

试题 B ：卡片

【解析】 这道题应该先定义一个长度为 $10$ 的数组，用来存放数字 $0 \sim 9$ 的卡片数，下标则代表数字，元素代表卡片已经使用的张数，初始值为 $0$ ，每种卡片如果使用超过 $2021$ 张，则输出结果。 程序从 $1$ 开始递增遍历，当遍历到某个数时，将拼成该数所需的所有卡片类型数增加，随后判断数组中每种卡片是否被用完，如果用完则退出循环。 【程序】

#include <bits/stdc++.h>

using namespace std;

int a[10];

int main()
{
    for(int s=1;;s++)
    {
        int temp=s;
        while(temp)
        {
            a[temp%10]++;
            temp/=10;
        }
        for(int i=1;i<10;i++)
        {
            if(a[i]>2021)
            {
                printf("%d\n",s-1);
                //减1是因为这一张无法凑出
                return 0;
            }
        }
    }
    return 0;
}

【答案】
$3181$

试题 C ：直线

【解析】 本题很容易让人想到枚举和去重，本人代码就是用枚举和去重来实现的。 为了储存 $3$ 个数，本人采取了 $\operatorname{STL}$ 中 $\operatorname{pair}$ 类来表示，为了去重，本人采取了 $\operatorname{STL}$ 中的 $\operatorname{set}$ 集合 （如果没学过，请自行查阅资料）。 【程序】

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
typedef pair<PII,int> PIII;

set<PIII> s;

vector<PII> vec;

int gcd(int a,int b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b,a%b);
}

int main()
{
    for(int i=0;i<20;i++)
    {
        for(int j=0;j<21;j++)
        {
            vec.push_back({i,j});
        }
    }
    for(int i=0;i<vec.size();i++)
    {
        for(int j=i+1;j<vec.size();j++)
        {
            int x1=vec[i].first,y1=vec[i].second;
            int x2=vec[j].first,y2=vec[j].second;
            int A=x2-x1,B=y1-y2,C=x1*y2-x2*y1;
            int gcdd=gcd(gcd(A,B),C);
            s.insert({{B/gcdd,A/gcdd},C/gcdd});
        }
    }
    cout<<s.size()<<endl;
    return 0;
}

【答案】
$40257$

试题 D ：货物摆放

【解析】 本题根据题意，要满足 $\operatorname{n}=\operatorname{x}\times \operatorname{y}\times \operatorname{z}$ 的所有情况，首先想到枚举法，分为两步： 1、找出 $n$ 的所有因子。 2、对所有因子进行暴力枚举。

【程序】

#include <bits/stdc++.h>

using namespace std;

long long a[100];
long long n=2021041820210418;

int len;

int main()
{
    for(long long i=1;i*i<=n;i++)
    {
        if(n%i==0)
        //i是约数
        {
            a[len++]=i;
            //将约数放入数组
            if(n/i!=i)
            //n/i也是约数
            {
                a[len++]=n/i;
            }
        }
    }
    int ans=0;
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<len;j++)
        {
            for(int k=0;k<len;k++)
            {
                if(a[i]*a[j]*a[k]==n)
                {
                    ans++;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

【答案】
$2430$

试题 E ：路径

【解析】 本题题意比较直接，通过题意就可以知道题目考查图的最短路径算法，本人则使用了 $\operatorname{Dijkstra}$ 算法直接计算 （如果没学过，请自行查阅资料并学习）。 【程序】

#include <bits/stdc++.h>

using namespace std;

const int MAXN=2022;

int edges[MAXN][MAXN];
int d[MAXN];

bool visited[MAXN];

int gcd(int u,int v)
{
	int temp=u%v;
	while(temp>0)
	{
		u=v;
		v=temp;
		temp=u%v;
	}
	return v;
}
int lcm(int u,int v)
{
	return (u*v/gcd(u,v));
}

int main()
{
    memset(edges,0x3f3f3f,sizeof(edges));
    for(int i=1;i<=2021;i++)
    {
        edges[i][i]=0;
        for(int j=i+1;j<=2021;j++)
        {
            if(j-i<=21)
            {
                edges[i][j]=edges[j][i]=lcm(j,i);
            }
            else
            {
                break;
            }
        }
    }
    memset(d,0x3f3f3f,sizeof(d));
    memset(visited,false,sizeof(visited));
    d[1]=0;
    for(int i=1;i<2021;i++)
    {
        int x=0;
        for(int j=1;j<2021;j++)
        {
            if(!visited[j] && d[j]<d[x])
            {
                x=j;
            }
        }
        visited[x]=1;
        for(int j=max(1,x-21);j<=min(2021,x+21);j++)
        {
            d[j]=min(d[j],d[x]+edges[x][j]);
        }
    }
    printf("%d\n",d[2021]);
	return 0;
}

【答案】
$10266837$