首页 > 其他 > 详细

【Bitset】重识

时间:2018-03-07 00:26:52      阅读:242      评论:0      收藏:0      [点我收藏+]

----------------------------------------------------------------------------

一题题目:

技术分享图片

一题题解:

 技术分享图片

  • 这个题目哪来入门再好不过了,支老板之前没有接触过这个东西,然后一点即通:就是把一个int(32位)拆成32个只放0或1的位置,然后这32个的单点操作或者32个一起操作的复杂度是O(1),所以长度位N的bitset的一次单点操作是O(1),整体操作是O(N/w),其中w=32。(long long 是64)。
  • 然后Bitset还有强大是&和|功能,以及count(1)等功能。
  • 但是Bitset最厉害的地方在于优化图论的dfs部分: 我们知道,dfs的时候对于当前点X,会继续访问和X有关联的所有点,continue忽略vis过的点。而有了bitset,我们可以直接得到有关联的,而且没有vis过的点,这样可以保证不去访问不必要的边,这在稠密图里改进极大。

 

-----------------------------------------------------------------------------

二题题目:

技术分享图片

二题题解:

技术分享图片

  • 跳过缩点建图。
  • 第一部分是求Bitset,得到每个点可以访问到的点。 
  • 第二部分求对应的权值和,巧妙的利用了分块来优化,复杂度/13。而且这个13的选择也是经过计算的,2^13<n,保证分块计算的复杂度影响小于前面的复杂度,新技能,学到了。

 

【Bitset】重识

原文:https://www.cnblogs.com/hua-dong/p/8519739.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!