首页 > 其他分享 >CF1826E

CF1826E

时间:2023-08-28 20:12:01浏览次数:42  
标签:偏序 傻卵 原题 复杂度 bitset CF1826E

原题

翻译

傻卵\(bitset\)题

高位偏序,直接套CDQ分治显然不可行

但是解决高维偏序还有一种常见的 trick:把每一维拆开,用二进制表示出偏序关系,最后全部按位与起来合并。

具体的,对于每一位我们按照\(r\)从小到大排序,固定\(i\),找出所有的\(r_j < r_i\)并在\(bitset\)中标为\(1\)。把所有的\(i\)枚举一遍后的\(bitset\) &AND&起来就是我们想要的答案了

然后只需要套一个显然的\(dp\)即可解决问题

最终复杂度\(O(\frac{n^2m}{w} + nm)\)

标签:偏序,傻卵,原题,复杂度,bitset,CF1826E
From: https://www.cnblogs.com/fox-konata/p/17663280.html

相关文章

  • CF1826E nowcoder55993G - bitset -
    CF1826E这个题比赛的时候基本做出来了,就是不会用bitset导致最后寄了。这已经是第三次很有希望做出E最后没有做出来了/ll好几个月了一直卡在四题,吐了首先如果对于一个模特,她在\(i\)城市的所有分数都分别小于\(j\)城市的,那么就\(i\rightarrowj\)连一条边,显然这是若......