2022年徐州市首届编程大赛题解（By Zchared）#

T1 - 数字正方形#

Link. 1s/512MB 的限制感觉作为签到题给的太过于大了 n ≤ 300 这题模拟就行了，相比较 CSP-S 2020 的 T1 的大模拟，这题简直有点基础的直接秒了。 主要就是每次循环，开个变量存上一行最后一个数字。记得这个变量要及时 mod 10 时间复杂度 O(n^2)

T2 - 数字反转#

Link. 限制 1s/128MB,是非常充裕的了。 N（-1000000000 ≤ n ≤ 1000000000）。 这题本人直接用字符串做（看 n 的范围,用字符串完全不用担心空间会爆） 开一个 bool 变量来记录是否为负数。如果字符串最前面一位（即 s[0]）为‘ - ’的话，就是负数。 舍去 0 的话，开循环进行判断就行了。 时间复杂度 O(s.length())

T3 - 试题解答#

Link. 1s/128MB 随便浪费吧 n ≤ 10000 慢慢细心模拟就行了.(由于我没有原题，所以不知道有没有算除法的。反正加上判定没坏处) 时间复杂度 O(n)

T4 - 跳格子#

Link. 1s/256MB 有人可能刚拿来可能拿来就想爆搜 DFS，然后他们就可能时间爆了，50pts—; 方法一：记忆化搜索 当下面的 DP 做就行了。换种写法就是记忆化搜索。 方法二：入门 DP 题 读题再写状态转移方程就行了。注意三个递推式的顺序。 dp[0]=0; dp[1]=0; dp[2]=2; dp[3]=1; ………… dp[i]=dp[i-1]+1; dp[i+2]=dp[(i+2)/3]+1; dp[i+1]=dp[i+2]+1; ans 保守点，开了 unsigned long long 时间复杂度 O(n)

T5 - 阶乘问题#

Link. (本人感觉其实这题是《编程之美》2.2 的变式，我把原来的题附在题解的PDF中。) (在《算法竞赛进阶指南》P138 也有道题和这道题差不多（叫：阶乘分解）) 1s/256MB 感觉暴力还是要优化的 我们从简单的问题开始考虑 假如 p = 10，那么什么时候 n!会出现 0？ 很容易想到，利用p进制的思维，当 n！的质因数分解中，有多少个 2 和 5 的乘积，末尾就有多少个 0。之后，ans=min(num(2),num(5)) 考虑到一个 p 可能有多个质因子，我们直接开数组。 py[]用来存 p 的质因子是啥。pynum[]用来存质因子 py[]在 p 的质因数分解中有多少个。numy[]用来存对应 n！的质因数分解中，质因子 py[]有多少个。之后：ans=min(numy[i]/pynum[i]); 主要是把原本 O(n^2)的求 n！质因数分解的过程给优化成大约 O(nsqrt(n))了 时间复杂度大约 O(nsqrt(n))(感觉这个优化后方法的时间复杂度不太好分析，这个时间复杂度可能不太对。) 其实还可以优化 直接上结论。 n!的质因数分解中，质因子 p 的个数为 (公式抄的《算法竞赛进阶指南》) gs0 于是原来算法的 O(n*sqrt(n))被优化成了 O(nlogn)