自动搬运

查看原文

来自洛谷，原作者为

	huangruiheng0217 Let life be beautiful like summer flowers and death like autumn leaves.

搬运于2025-08-24 22:42:04，当前版本为作者最后更新于2023-02-13 21:38:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

先说句闲话：做这道题最需要的不是思维能力和代码能力，而是耐心。

等了 15min 以后出了答案，点击提交结果答案错误。。

进入正题。

---

A

problem

一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。计算 $2021$ 的双阶乘的后 $5$ 位。

sol

由定义可知，我们需要计算下列式子的值。

$$\prod_{i=1}^{1011}(2\times i-1)$$

那么直接枚举即可，注意边乘边取余。代码就不放了。

---

B

problem

找到所有的坐标 $(x,y)$ 满足：

• 在格点上。

• 在第一象限。

• 横纵坐标乘积 $\le 2021$。

sol

双重循环枚举横纵坐标在 $2021$ 以内的格点并统计答案即可。

或者也可以单重循环（注意向下取整）。

for(int i=1;i<=2021;i++)//双重循环版
	for(int j=1;i*j<=2021;j++)
		ans++;

for(int i=1;i<=2021;i++)//单重循环版
	ans+=2021/i;

---

C

problem

将 $2021$ 分解成五个正整数的和，区分顺序。求排列总数。

sol

本来要五重循环，发现最后一个数可以直接计算，减少一重循环。（其实也没有快多少）

代码也不需要了吧，答案 69167727****，炸 int 了。因此浪费了好久。

跑了十五分钟。

---

D

problem

给定 $2021$ 个点，每两个不同的点之间都有边连接，边权按一定规则生成：十进制下两个点的编号的所有不同数位的数码和。

$2021$ 和 $922$ 的千位（后者个位为 $0$）、百位和个位不同，所以边权为 $(2+0)+(0+9)+(1+2)=14$。

求这张图的最小生成树。

sol

考虑到点的数量不多，且图为完全图，用邻接矩阵存图。

先写个加边的函数。注意点的编号要存一个备份。

void add(int x,int y){
	int dx=x,dy=y;
	int res=0;
	while(x>0||y>0){
		if(x%10!=y%10)
			res+=(x%10+y%10);
		x/=10,y/=10;
	}
	g[dx][dy]=res;
	return;
}

然后写个最小生成树。参考洛谷模板题。

	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	for(int a=1;a<=n;a++){
		int minn=2e9,u=0;
		for(int i=1;i<=n;i++){
			if(vis[i])continue;
			if(minn>dis[i])u=i;
			minn=min(minn,dis[i]);
		}
		ans+=minn;
		vis[u]=1;
		for(int i=1;i<=n;i++){
			if(u==i)continue;
			if(vis[i]==1)continue;
			dis[i]=min(dis[i],g[u][i]);
		}
	}

答案以 $4$ 开头。

---

E

problem

在纸上写下一个数，此后写的每一个数都是上一个数的约数，且不能是自己。到 $1$ 结束。当以 $20210509$ 为开头的时候，求方案数量。

sol

可以从递归开始想，但是考虑到复杂度过高，可以换成递推。

为了在 $O(n\sqrt{n})$ 的复杂度以内做出答案，考虑每个小于 $\sqrt{n}$ 的因数都能找到对应的另一个因数（使得乘积为 $n$）。因此可以大幅降低查找的复杂度。注意 $a$ 数组要开 long long。

void f(int x){
	if(x==1){
		a[1]=1;
		return;
	}
	for(int i=1;i*i<=x;i++)
		if(x%i==0){
			if(i*i==x){//注意i刚好是根号x的时候要特判
				a[x]+=a[i];
				break;
			}
			a[x]+=a[i];
			a[x]+=a[x/i];
		}
	return;
}

---

总结：难度不算太大，但是想要一遍过需要很仔细。特别是第三问。