# 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)