关键词:
在蒟蒻Cydiater日常水题的过程中,忽然遇到了一道题。中间有一个过程是要求在很快的时间内求出$1500$大小的两个01串的与之后存在多少个1。
最坏的,扫一遍,整体复杂度$O(N)$,好像没有什么可以优化的空间了QAQ。我开始考虑用位运算的与操作优化,因为其有$1500$个元素,所以可以考虑把这个东西拆成$frac{N}{32}$个01串。
但是这之后好像就又存在一个问题。如何快速的统计一个二进制的01串里有多少个1?如果不要求$O(1)$,可以不停的统计lowbit,那么这个复杂度就和有多少个答案有关,这样的话最坏复杂度仍然是$O(N)$.
然后就去百度各种翻,看到了一个关于bitset的名词。然后xjb搞了搞后觉得很神奇,就先记下来。
BITSET
bitset是STL里的一种容器,也就是一个优化过的bool数组。里面存的就是一大串的01。
之所以说它优化过,是因为他不仅可以像int和long long一样进行与,或,异或操作。时间复杂度也大差不差。而且自带的一些函数也很方便使用,其中就包括了快速的统计出来一个bitset里有多少个1。
bitset的具体操作有很多,我列举几个比较常用的。
具体的定义如下:
#include <bitset> using namespace std; #define LENGTH 32 #define bs bitset<LENGTH> bs S;
这里面的LENGTH就是要定义的长度,也就是里面具体有几个01元素。
因为他重载了[],所有可以像访问数组一样访问任意位。
复制一段别人的代码:
#include <iostream> #include <bitset> using namespace std; int main(){ //bitset 使用整数初始化bitset bitset<3> bs(7); //输出bs各个位的值 cout<<"bs[0] is "<<bs[0]<<endl; cout<<"bs[1] is "<<bs[1]<<endl; cout<<"bs[2] is "<<bs[2]<<endl; //下面的语句会抛出outofindexexception //cout<<"bs[3] is "<<bs[3]<<endl; //使用字符串初始化bitset //注意:使用string初始化时从右向左处理,如下初始化的各个位的值将是110,而非011 string strVal("011"); bitset<3> bs1(strVal); //输出各位 cout<<"bs1[0] is "<<bs1[0]<<endl; cout<<"bs1[1] is "<<bs1[1]<<endl; cout<<"bs1[2] is "<<bs1[2]<<endl; //cout输出时也是从右边向左边输出 cout<<bs1<<endl; //bitset的方法 //any()方法如果有一位为1,则返回1 cout<<"bs1.any() = "<<bs1.any()<<endl; //none()方法,如果有一个为1none则返回0,如果全为0则返回1 bitset<3> bsNone; cout<<"bsNone.none() = " <<bsNone.none()<<endl; //count()返回几个位为1 cout<<"bs1.count() = "<<bs1.count()<<endl; //size()返回位数 cout<<"bs1.size() = "<<bs1.size()<<endl; //test()返回某一位是否为1 //flip()诸位取反 bitset<3> bsFlip = bs1.flip(); cout<<"bsFlip = "<<bsFlip<<endl; //to_ulong unsigned long val = bs1.to_ulong(); cout<<val; }
[c++多线程]1.3-多线程控制的另一种姿势-条件变量(condition_variable),信号量(semaphore)(代码片段)
文章目录条件变量(C++11)为什么要引入条件变量条件变量的用法条件变量引发的虚假唤醒信号量(C++20)std::binary_semaphore使用counting_semaphore使用条件变量(C++11)为什么要引入条件变量我们先来看看一个由互斥量加锁构... 查看详情
go删除切片元素的另一种姿势(代码片段)
首先整理一下删除切片的常用方法现在有一个切片sliceslice=append(slice[:n]:slice[n+1])slice=slice[1:]等等本文针对一个特殊场景:现有切片A,B,切片B中的部分元素是切片A的子集,求A删除B中子集后的... 查看详情
go删除切片元素的另一种姿势(代码片段)
首先整理一下删除切片的常用方法现在有一个切片sliceslice=append(slice[:n]:slice[n+1])slice=slice[1:]等等本文针对一个特殊场景:现有切片A,B,切片B中的部分元素是切片A的子集,求A删除B中子集后的... 查看详情
百分位数的另一种方法?
】百分位数的另一种方法?【英文标题】:Anotherapproachtopercentiles?【发布时间】:2013-05-0821:48:33【问题描述】:我有一个数据集,它基本上由作业批次列表、每个批次中包含的作业数量以及每个作业批次的持续时间组成。这是一... 查看详情
down的另一种用法
为啥一种算法比具有相同时间复杂度的另一种算法更快?
】为啥一种算法比具有相同时间复杂度的另一种算法更快?【英文标题】:Whyisonealgorithmfasterthananotherwiththesametimecomplexity?为什么一种算法比具有相同时间复杂度的另一种算法更快?【发布时间】:2020-06-0411:45:26【问题描述】:我... 查看详情
sharedpreferences的另一种场景的用法
SharedPreferences的另一种场景的用法昨天,下班在家想做什么来着,然后想用SharedPreferences存点数据,但是不知道咋地突然想到,SharedPreferences是应用启动时一次性加到内存里的.适合少量的存储,多的话还是用数据库吧.实际项目中都是数... 查看详情
将图片发送到 Gmail 的另一种方式
】将图片发送到Gmail的另一种方式【英文标题】:AnotherwaytosendpicturetoGmail【发布时间】:2015-07-1617:10:19【问题描述】:默认情况下,如果图片来自其他网站,Gmail会隐藏这些图片。Outlook等软件如何将签名图片发送到Gmail而不被隐... 查看详情
在 C++ 中做模板的另一种方法?
】在C++中做模板的另一种方法?【英文标题】:AnotherWaytodoTemplatesinC++?【发布时间】:2012-08-1411:44:50【问题描述】:当我发现这种创建模板类的依赖于预处理器的方法时,我只是在搞砸:#include<iostream>#include<typeinfo>//Isthi... 查看详情
Riverpod:在 ConsumerWidget 中覆盖 initState 的另一种方法
】Riverpod:在ConsumerWidget中覆盖initState的另一种方法【英文标题】:Riverpod:AlternatewayofoverridinginitStateinsideConsumerWidget【发布时间】:2021-01-1917:46:09【问题描述】:因为这里的initState方法不可覆盖,所以在consumerWidget里面初始化东西... 查看详情
insertinto的另一种添加插入新行方式
语法1插入一行insertintotable(field1,field2.....)selectvalue1,value2........; 2插入多行insertintotable(field1,field2.....)selectvalue1,value2........unionselectvalue1,value2........ 实例createtablebank(cus 查看详情
如何设置一种样式来覆盖 CSS 中的另一种冲突样式?
】如何设置一种样式来覆盖CSS中的另一种冲突样式?【英文标题】:HowcanIsetonestyletooverrideanotherconflictingstyleinCSS?【发布时间】:2010-10-0716:22:11【问题描述】:当用户单击它们时,我正在显示在数据库中标记为已读的链接。我想根... 查看详情
如何将一种泛型类型的结构复制到 TypeScript 中的另一种泛型?
】如何将一种泛型类型的结构复制到TypeScript中的另一种泛型?【英文标题】:HowtocopythestructureofonegenerictypetoanothergenericinTypeScript?【发布时间】:2021-09-0708:05:07【问题描述】:假设我们有以下输入类型:interfaceInputname:string;heightCm:... 查看详情
自闭元素的另一种说法是啥(2个词)(第一个字母以e开头)
】自闭元素的另一种说法是啥(2个词)(第一个字母以e开头)【英文标题】:Whatisanothertermforself-closingelements(2words)(firstletterstartswithe)自闭元素的另一种说法是什么(2个词)(第一个字母以e开头)【发布时间】:2020-07-2515:18:28... 查看详情
从 VB.NET 中的注册表获取实际 REG_DWORD 十进制数的另一种方法?
】从VB.NET中的注册表获取实际REG_DWORD十进制数的另一种方法?【英文标题】:AnotherroutetogetactualREG_DWORDdecimalnumberfromregistryinVB.NET?【发布时间】:2021-09-2406:02:38【问题描述】:我一直在将GetValue与GetValueKind一起使用,并且在读取大... 查看详情
shiro开发的另一种方式(代码片段)
今天在学习shiro的时候使用另一种shiro验证的方式。 总体的思路是: (1)先在自己的方法中进行身份的验证以及给出提示信息。 (2)当验证成功之后到Shiro中认证以及授权一下即可。当然,在自己验... 查看详情
从 netbeans 中的另一种形式在表中添加行
】从netbeans中的另一种形式在表中添加行【英文标题】:addingrowsinatablefromanotherforminnetbeans【发布时间】:2013-11-1508:31:15【问题描述】:我有这两种形式:NetBeans中的“时尚和鞋类”和“购物车”。第一个表单包含4个按钮。另一个... 查看详情
在 C++ 中使用 continue 关键字的另一种方法
】在C++中使用continue关键字的另一种方法【英文标题】:AnotherwaytousecontinuekeywordinC++【发布时间】:2010-09-2907:29:19【问题描述】:最近我们发现了一个使用continue注释掉代码行的“好方法”:for(inti=0;i<MAX_NUM;i++)........//-->about30... 查看详情