CF2135D

_jimmywang_ · 2025-08-29 23:03:29 · 个人记录

D1 做法很人类（但是我想不出来，我不是人类。），输出 10^5 个 \sqrt{10^5}\approx316 可以确定 W 对 316 下取整是多少。如果是 0 那就输出 10^5 个 1，根据下取整直接确定这个数是多少；否则我们只需要确定 W \bmod 316 的值。注意到此时我们能够确定 W 所在的一个范围 [l,r]，r-l=315，因此你输出 l,l,1,l,2,l,3,\dots,l,314,l,315 就能确定余数。

D2 做法其实很类似，你第一步输出 B^2 个 B，确定 W<B 或者 \lfloor\frac{W}{B}\rfloor 的值（或者其所在范围），相应的 W 也能得到一个所在范围 [l,r]。你要保证 r<2l 就还能继续用上面的做法，然后第二问输出量是 2(r-l+1)-1，总输出量就是 B^2+2(r-l+1)-1。调一调这个 B，我调出来 B=110 就能保证最多 24859 个词。