日记

今天是民国 114 年 5 月 14 日。

SuperGCD# Link to

纯恶心人的题。谁用 C++ 写谁有病。

Fox And Jumping# Link to

口胡一下发现当且仅当选出来的 $l_i$ 的 $\gcd$ 为 $1$ 的时候才会是可行的。于是我们直接设 $dp_i$ 表示把 $\gcd$ 干成 $i$ 的最小代价。转移就是 $dp_{j,\gcd(j,l_i)} \leftarrow dp_j + c_i$。用 map 存下来就行。

Boxes# Link to

我们首先把 $a,b$ 都除以一个 $\gcd(a,b)$ 把他们变得互质。$a,b$ 能通过这种操作变得某个为 $0$ 当且仅当这时的 $a + b = 2^k$。证明如下：

充分性：进行一次操作后，无论较小值是谁，$a,b$ 在二进制下的后缀 $0$ 个数都是增加的，这样最终就会变成 $2^k$。
必要性：手玩一下样例。

于是就是喜闻乐见的打代码时间了。

Binomial coefficients# Link to

根据常识，我们发现 $\binom{n}{k}$ 的 $k$ 不会大于 $30$，于是我们直接枚举 $k$，因为在 $k$ 不变的情况下 $\binom{n}{k}$ 随 $n$ 单增，我们直接二分 $n$ 然后统计答案。

记得排序和去重。

荒岛野人# Link to

野人的事情让野人自己想去

我们发现这玩意长得跟个粑粑同余方程似的，于是直接枚举 $m$，再枚举 $i,j$ 两个野人，exgcd 解出最小的 $x$，如果 $x$ 小于等于 $\min(l_i,r_i)$，就说明他们会打架，否则就可行。

后日谈 # Link to 后日谈

明日目标：$140$。