「Summary」2022-07-01 做题记录

好难啊！！！1

2022-07-01

$\mathbb{CF1174E}$

开幕黑题

link

首先确定开头。

若当前的开头数字为 $x = \prod_{i=1}^{n} p_i^{q_i}$ 。那么它的本质不同的因数个数是 $\prod_{i = 1}^n (q_i + 1)$ ， 能产生的不同的前缀 $\gcd$ 个数为 $(\sum_{i=1}^n q_i) + 1$ 。

那么开头数字的要求就应该是 $(\sum_{i=1}^n q_i)+1$ 最大的数。

最好的情况是只含有 $2,3$ 这两个质因数，因为：如果有 $5$ 则可以用 $2^2$ 代替，更大的质因数贡献更小。

而可以存在一个 $3$ ，如果是两个 $3$ ，则可以用 $2^3$ 代替。

然后发现前缀 $\gcd$ 一定只含有 $2,3$ 两个因数，则可以设计 $dp$ 状态为 $dp_{i,x,y}$ 表示当前是第 $i$ 个前缀 $\gcd$ ，含有 $x$ 个质因数 $2$ ，含有 $y$ 个质因数 $3$。

令 $cnt(x)$ 为 $n$ 以内 $x$ 的倍数，则 $cnt(x) = \lfloor \frac{n}{x} \rfloor$。

然后 $dp$ 代码长这样。

dp[i][j][0] = ((LL)dp[i - 1][j][0] * (cnt(1 << j) - i + 1)  // gcd 不变
            + (LL)dp[i - 1][j + 1][0] * (cnt(1 << j) - cnt(1 << (j + 1))) // 少一个质因数 2
            + (LL)dp[i - 1][j][1] * (cnt(1 << j) - cnt((1 << j) * 3))) % Mod; // 少一个质因数 3
dp[i][j][1] = ((LL)dp[i - 1][j][1] * (cnt((1 << j) * 3) - i + 1) // gcd 不变
            + (LL)dp[i - 1][j + 1][1] * (cnt((1 << j) * 3) - cnt((1 << (j + 1)) * 3))) % Mod; // 少一个质因数 2

$\mathbb{2015-2016\ Petrozavodsk\ Winter\ Training\ Camp,\ Saratov\ SU\ Contest\ A}$

《显而易见》的性质

link

注意到 $1 \le t_i \le 30$ 的限制，《强烈》暗示这道题的 $dp$ 维度与这个有关。

首先可以定义一个三维的 $dp_{i,x,y}$ 表示选择了前 $i$ 个任务，其中第一个机器的认为时长总和为 $x$，第二个机器的认为时长总和为 $y$ 所需要花的最小步数，再定义一个辅助数组 $f_{x,y}$ 表示 $x,y$ 的可达性。

因为每次都是从上一层转移，那么 $i$ 这一层可以消掉，结合到 $1 \le t_i \le 30$ ，则总和不超过 $12000$ ，每个机器的时长总和不超过 $4030$ ，因为若有一个比 $4030$ 更小的机器，把当前的任务分给最小的一定会让答案更优。

所以枚举的值的范围就可以缩小到 $4030$ 。

总的时间复杂度正确了。

笑了，我输出方案写挂了，原因是《左脚右脚一起走路》。。。