CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 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的因子，同样的因子，不同的因子没有贡献，放到一起计算。<del>然后被卡了。</del>

**comment**

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

用户工具

站点工具

页面工具
