2020牛客暑期多校第九场

2020牛客暑期多校第十场

无

AtCoder Grand Contest 047

见本周推荐

无

无

见本周推荐

无

无

见本周推荐

AtCoder:

Integer Product

题意:

给一堆浮点数,问有哪些数对,它们的积是整数.

tag:

数学

题解:

显然,每个数可以看做是2的次幂乘以5的次幂再乘以其他的因数.因为要求两数之积是整数,所以只需要考虑2和5的贡献.

如果一个数的2和5的次幂分别是$x$,$y$,另一个数是$x'$,$y'$,如果有$x+x' \geq 0$,$y+y' \geq 0$,那么两个数的乘积就是整数.

只需要把每个数先补成整数,质因数分解后算贡献即可.

commment:

HDU 3709

题意

求 $[L, R]$ （均 $\le 10^9$）中有多少个数，其是力矩平衡的。

一个 $\text{n}$ 位数 $b_{n} b_{n-1} \cdots b_2 b_1$ 是力矩平衡的当且仅当 $\exists \ p \in [1, n]，s.t. \sum\limits_{i\ =\ len}^{1}\{b_i\times (i-p) \} = 0$。

题解

数位dp，考虑枚举中心的位置 $\in [1, len]$ 进行统计。

这个力矩计算的定义类似数位和，又因为计算的时候和中心位置有关，所以枚举数位和和枚举中心占 2 维，3 维 dp 即可。 dp[i][j][k] 表示当前中心枚举到 i，当前力矩和为 j，枚举到位数 k 的计数。在 k 走到 0 的时候判断 j 是不是 0 统计即可。

一个显而易见的剪枝是如果当前的力矩和为负了，说明已经开始递减，因此最后不可能回到 0，可以剪掉。

注意 0 的去重即可（不管中心在哪里都会被统计 1 次）。

https://ac.nowcoder.com/acm/contest/5674/E

题意

计算如题描述的累积式子。

题解

枚举x和y的因子，同样的因子，不同的因子没有贡献，放到一起计算。然后被卡了。

comment

还得记忆化x和y的某因子次数，因为贡献是一个关于因子值的一次式，就可以先把前面的系数处理出来。以防那种2*3*5*7*11*13*17的数据。