20230826考试题解

· · 个人记录

原题链接

第一题：原创签到

第二题：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。

## 第二题 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$ 的三重循环的意义，最外层枚举到 $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)