为啥题解里面的做法都用了 bitset
查看原帖
为啥题解里面的做法都用了 bitset
253738
听取MLE声一片楼主2023/12/21 16:13

偏移量是根号的,也就是 3030 位。但是题解区怎么都用 bitset 写的,而为了压 3030 位用 bitset 多少有点抽象。实际上直接把题解的 bitset 直接改成 long long 甚至 int 都能过。

这样的话根据 OI 的经验,把位运算视为 O(1)O(1),所以本题复杂度应该是 O(p2nn)O(p^2n\sqrt n) 吧。

感觉题解区用 bitset 都是为了强调压位这个思想,但是用 bitset 压 3030 位多少有点多余吧。

顺带一提本题最优解是面向数据编程老哥,直接改成 int 是除这个以外的最优解。

2023/12/21 16:13
加载中...