和 dx,EY 一起打的一场,各做各的。
容易发现二分后贪心。
如果一定要改,就改,不咋需要改的,能改到 $a_i=a_{i-1}$ 就改。
可以证明,这是对的。
一开始写了个暴力,发现跑的飞快!
这是因为抽屉原理易证不会有 $\geq 10$ 的非法串串。
赛时没做出来。
dx 给我讲了。
能连边当且仅当有至少一位都是 $1$,所以我们考虑对于每一位中转点优化连边一下,然后在图上跑 dijkstra 即可。
觉得这很对,但是多组询问怎么做暂时搞不懂。