====== 2020/08/08 -- 2020/08/14 周报 ====== ===== 团队训练 ===== [[2020-2021:teams:tle233:Niuke09|2020牛客暑期多校第九场]] [[2020-2021:teams:tle233:Niuke10|2020牛客暑期多校第十场]] ===== Marvolo ===== ==== 专题 ==== 无 ==== 比赛 ==== [[https://atcoder.jp/contests/agc047|AtCoder Grand Contest 047]] ==== 题目 ==== 见本周推荐 ===== Kevin ===== ==== 专题 ==== 无 ==== 比赛 ==== 无 ==== 题目 ==== 见本周推荐 ===== TownYan ===== ==== 专题 ==== 无 ==== 比赛 ==== 无 ==== 题目 ==== 见本周推荐 ===== 本周推荐 ===== ==== Marvolo ==== AtCoder: [[https://atcoder.jp/contests/agc047/tasks/agc047_a| Integer Product]] 题意: 给一堆浮点数,问有哪些数对,它们的积是整数. tag: 数学 题解: 显然,每个数可以看做是2的次幂乘以5的次幂再乘以其他的因数.因为要求两数之积是整数,所以只需要考虑2和5的贡献. 如果一个数的2和5的次幂分别是$x$,$y$,另一个数是$x'$,$y'$,如果有$x+x' \geq 0$,$y+y' \geq 0$,那么两个数的乘积就是整数. 只需要把每个数先补成整数,质因数分解后算贡献即可. commment: ==== Kevin ==== [[http://acm.hdu.edu.cn/showproblem.php?pid=3709 | 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 次）。 ==== TownYan ==== [[https://ac.nowcoder.com/acm/contest/5674/E]] **题意** 计算如题描述的累积式子。 **题解** 枚举x和y的因子，同样的因子，不同的因子没有贡献，放到一起计算。然后被卡了。 **comment** 还得记忆化x和y的某因子次数，因为贡献是一个关于因子值的一次式，就可以先把前面的系数处理出来。以防那种2*3*5*7*11*13*17的数据。