本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-26 17:26:56

原题链接

第一题：原创签到

第二题：https://ac.nowcoder.com/acm/contest/57360/C

第三题：https://ac.nowcoder.com/acm/contest/57360/B

第四题：https://acm.hdu.edu.cn/showproblem.php?pid=7308

第五题：https://acm.hdu.edu.cn/showproblem.php?pid=7322

第一题 T310720 宝石分配

给出 $N,M$，求最大的 $x$ 满足 $x|N$ 且 $x \le M$。

$O(\sqrt n)$ 枚举 $N$ 的因数即可。

第二题 T372575 数学高手也会爱上毒瘤数学题2

求 $1!! \times 2!! \times 3!! \times \cdots \times n!!$ 的后缀 $0$ 的个数。

因为质因数分解后 $2$ 的次数一定大于等于 $5$ 的次数，因此可以转化为求质因数分解后 $5$ 的次数。

分奇偶双阶乘进行讨论，对于奇数的双阶乘，可以发现 $5!!、6!!\cdots$ 都包含一个 $5$，$10!!、11!!\cdots$ 都包含一个 $10$，这样推下去，会发现$5,10,15,20,25,30 \cdots$ 出现的次数分别是(设最大的奇数为 $n$) $n-4,n-9,n-14,n-19 \cdots$，等差数列求和即可。

做到这里会发现一个问题，就是像 $25$ 这种对质因数$5$的次数的贡献为 $2$，因此，我们可以递归地计数。设上面的等差数列求和过程为函数 $calc(n，5)$，则将$calc(n/5，25)，calc(n/5/5，125) \cdots$ 也统计进答案即可。(这样可以保证因数 $5^k$ 被统计了 $k$ 次)

最后用 $\_\_int128$ 统计答案，时间复杂度 $O(logn)$。

第三题 T372576 占卜

首先可以发现性质，对于两个大小相等的可重集合，想要计算可信度，可以将两个集合分别排序，然后将对应位置的差的绝对值加起来就是这两个集合的可信度。

排序之后，有两种方法统计答案：

方法一：

$ans = \sum_{1 \le i \le n} \sum_{1 \le j \le n} [\sum_{0 \le k < min(i,j)} (^{i-1}k) (^{j-1}_k)][\sum{0 \le k \le min(n-i,n-j)} (^{n-i}_k) (^{n-j}_k)] |a_i-b_j|$

利用组合恒等式 $\sum_{0 \le k \le min(n,m)} (^{n}k) (^{m}_k) = (^{n+m}{n})$ 化简，得

$ans = \sum_{1 \le i \le n} \sum_{1 \le j \le n} (^{i+j-2}{i-1})(^{2n-i-j}{n-i}) |a_i-b_j|$

预处理组合数统计答案即可。

如果不会组合恒等式也可以用 $cnt[i][j]$ 表示从第一个集合的前$i$个元素和第二个集合的前$j$个元素中选取的方案总数，然后DP转移即可。

方法二：动态规划

设$f[i][j]$表示考虑第一套卡牌的前 $i$ 张和第二套卡牌的前 $j$ 张，所产生的所有答案的和。

转移 $f[i][j]=f[i-1][j]+f[i][j-1]+cnt[i-1][j-1] \times |a_i-b_j|$

其中 $cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]$

两个方法的时间复杂度均为 $O(n^2)$

第四题 T372577 什么是羁绊

每张卡牌有三个指标 $a_i,b_i,c_i$，每张卡牌可以进行一次升级或不升级，升级之后变成$a_i',b_i',c_i'$

计算 $max(\max_{1\le i\le n}a_i-\min_{1\le i\le n}a_i,\max_{1\le i\le n}b_i-\min_{1\le i\le n}b_i,\max_{1\le i\le n}c_i-\min_{1\le i\le n}c_i)$ 的最小值

做法：首先令所有卡牌都不升级，然后统计一次答案。在统计答案的时候，找到产生当前答案的瓶颈所在的卡牌。如果该卡牌没有被升级过，可以确定的是，如果接下来不升级这张卡牌，答案一定不会更优，因为瓶颈没有消除。

所以可以贪心地每次找到当前处于瓶颈的卡牌(如果不能升级就直接退出，因为之后的答案不会更优了)，然后进行升级，用当前的答案尝试更新最终的答案。

这样最多升级 $n$ 张卡牌之后，就获得了本题的答案。

在升级过程中需要使用多个 $set$ 对升级过和没升级过的卡牌进行维护和取最大最小值等操作，复杂度 $O(nlogn)$

第五题 T372578 逛校园

给出 $n$ 个点的有向带权图，统计最小环的个数和长度。

$floyd$ 跑最短路+最短路计数，用 $dis[i][j]$ 表示从 $i$ 到 $j$ 的最短路，用 $cnt[i][j]$ 表示从 $i$ 到 $j$ 的最短路条数。

考虑 $floyd$ 的三重循环的意义，最外层枚举到 $k$ 的时候，当前的 $dis$ 和 $cnt$ 都表示除了端点只经过编号小于等于 $k$ 的点的情况下的最短路和最短路条数。为了防止重复找环，$floyd$ 最外层枚举到 $k$ 的时候，只将经过 $k$ 的环统计进答案，即枚举编号小于 $k$ 的所有点 $i$，尝试用 $dis[i][k]+w[k][i]$更新答案。

更新答案的意思是：如果当前记录的最小环的大小大于 $dis[i][k]+w[k][i]$，就直接更新最小环的大小，并令最小环的个数等于 $cnt[i][k]$；如果当前记录的最小环的大小等于 $dis[i][k]+w[k][i]$，就只令当前记录的最小环的个数加上 $cnt[i][k]$；其它情况不更新。

本题为 $floyd$ 的深度理解与应用，时间复杂度 $O(n^3)$