题解：P8713 [蓝桥杯 2020 省 A2] 填空问题

· · 题解

题目传送门

解析

题目大意

题一就是求 1 至 2020 中有多少个数位为 2。

题二就是求满足分母分子均为 1 至 2020 间的任意整数且分子分母的最大公约数为 1。

题三就是给出了一个蛇形的阵，问第 20 行第 20 列的数是多少。

题四就是给出了如图的一个形状，求出总共能有多少种情况，使得形状有且仅有一部分的边亮光。

题五就是问 20 个圆和 20 条直线最多能把平面分成多少个部分。

考察知识

本题考查数学知识、找规律、并查集和 DFS。

思路

题一没什么好说的，就是枚举每个数，求出这个数有多少个 2 即可。代码如下。

#include<bits/stdc++.h>
using namespace std;
int sum=0;
int main() 
{
    for(int i=1;i<=2020;i++) 
    {
        int ls=i;
        while(ls) 
        {
            if(ls%10==2) 
            {
                sum++;
            }
            ls/=10;
        }
    }
    cout<<sum;
}

题二就是枚举加上最大公约数判断。这里使用通用的辗转相除法求最大公约数。代码如下。

#include<bits/stdc++.h>
using namespace std; 
int sum=0;
int gcd(int a,int b)
{
    int r=a%b;
    while(r)
    {
        a=b;b=r;
        r=a%b;
    }
    return b;
}

int main()
{
    for(int i=1;i<=2020;i++)
    {
        for(int j=1;j<=2020;j++)
        {
            if(gcd(i,j)==1)
            {
                sum++;
            }
        }
    }
    cout<<sum;
}

题三这种一看就知道是找规律。我们观察一下就会发现如下的情况。

第一行第一个数为 1=0+1。

第二行第二个数为 5=(1+2)+2=[1+2(2-1)]+2。

第三行第三个数为 13=(1+2+3+4)+3=[1+...+2(3-1)]+3。

看出规律来了吗？规律就是第 n 行第 n 列的数为 [1+...+2(n-1)]+n。运用等差数列求和公式等化简得到 (n-1)\times(2n-1)+n。

代码如下。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<(20-1)*(2*20-1)+20;
}

题四我们为了方便处理连在一起的情况，可以用并查集。我们先将连通的边用数组标记，然后用 DFS，完毕后使用并查集即可。代码如下。

#include<bits/stdc++.h>
using namespace std;
int connection[10][10],fa[10],vis[10],sum=0;
int find(int x) 
{
    if(fa[x]==x) 
    {
        return x;
    }
    return fa[x]=find(fa[x]); 
}
void dfs(int k) 
{
    if(k>7) 
    {
        for(int i=1;i<=7;i++) 
        {
            fa[i]=i;
        }
        for(int i=1;i<=7;i++) 
        {
            for(int j=1;j<=7;j++) 
            {
                if(connection[i][j]&&vis[i]&&vis[j]) 
                {
                    int xx=find(i),yy=find(j);
                    if(xx!=yy) 
                    {
                        fa[xx]=yy;
                    }
                }
            }
        }
        int ls=0;
        for(int i=1;i<=7;i++) 
        {
            if(fa[i]==i&&vis[i]) 
            {
                ls++;
            }
        }
        if(ls==1) 
        {
            sum++;
        }
        return ;
    }
    vis[k]=1;
    dfs(k+1);
    vis[k]=0;
    dfs(k+1);
}
int main() 
{
    connection[1][2]=1;
    connection[2][1]=1; 
    connection[1][6]=1;
    connection[6][1]=1;
    connection[6][7]=1;
    connection[7][6]=1;
    connection[6][5]=1;
    connection[5][6]=1;
    connection[2][7]=1;
    connection[7][2]=1;
    connection[2][3]=1;
    connection[3][2]=1;
    connection[5][7]=1;
    connection[7][5]=1;
    connection[5][4]=1;
    connection[4][5]=1;
    connection[3][7]=1;
    connection[7][3]=1;
    connection[4][3]=1;
    connection[3][4]=1;
    dfs(1);
    cout<<sum;
}

题五的话需要有点想象。构造是先用二十个圆将平面分割成 2+2+4+...38 个部分，然后画一条直线与这二十个圆相交，平面增加四十个部分。最后再画十九条直线，增加 42+...+78 个部分。代码如下。

#include<bits/stdc++.h>
using namespace std;
int sum=0;
int main()
{
    sum+=2;
    for(int i=2;i<=20;i++)
    {
        sum+=(i-1)*2;
    }
    sum+=40;
    for(int i=2;i<=20;i++)
    {
        sum+=40+i;
    }
    cout<<sum;
}

然后我们输出所有答案即可！答案是：624,2481215,761,80,1391。

代码

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "624",
        "2481215",
        "761",
        "80",
        "1391"
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}