P8750题解

· · 题解

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

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

进入正题。

A

problem

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

sol

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

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

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

B

problem

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

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 个点，每两个不同的点之间都有边连接，边权按一定规则生成：十进制下两个点的编号的所有不同数位的数码和。

求这张图的最小生成树。 #### sol 考虑到点的数量不多，且图为完全图，用邻接矩阵存图。 先写个加边的函数。注意点的编号要存一个备份。 ```cpp 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; } ``` 然后写个最小生成树。参考洛谷模板题。 ```cpp 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`。 ```cpp 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; } ``` --- 总结：难度不算太大，但是想要一遍过需要很仔细。特别是第三问。