自动搬运

查看原文

来自洛谷，原作者为

	a202401006 繁星固然美丽，但摘星的人却寥寥无几。

搬运于2025-08-24 22:41:42，当前版本为作者最后更新于2025-06-28 17:44:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

解析

题目大意

题一就是求 $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;
}