BitSet
bitset优化传递闭包
bitset优化传递闭包 时间复杂度 \(O(\frac{n^3}{w})\) #include<bits/stdc++.h> #define F(i,l,r) for(int i=l;i<=r;++i) #define G(i,r,l) for(int i=r;i>=l;--i) #define ......
洛谷B3611 【模板】传递闭包 floyd/bitset
目录floydbitset优化 题目链接:https://www.luogu.com.cn/problem/B3611 参考题解:https://www.luogu.com.cn/blog/53022/solution-b3611 floyd #include <bits/stdc++.h> usi ......
【笔记】 浅学 bitset
bitset 简介 bitset 是 C++ 自带的一个STL。 bitset是一个01串,01串上的每一位就是1bit,在一些场合优化bool数组。 初始化 使用 bitset 需要用到 \(\text{“#include<bitset> ”}\) ,不过这个头文件在万能头里就自带了,可以直接用。 ......
cf1856E2. PermuTree (hard version)(bitset+二进制优化背包+开不同大小bitset)
https://codeforces.com/contest/1856/problem/E2 结论是显然的,关键是有一些科技在里面 bitset+二进制优化 具体分析可以参考https://codeforces.com/blog/entry/98663 简而言之就是可以通过\(O(\frac{C\s ......
bitset用法
1、简介 bitset 在 bitset 头文件中,它类似数组,并且每一个元素只能是0或1,每个元素只用1bit空间。 //头文件 #include<bitset> 2、初始化定义 初始化方法 代码 含义 bitset a a有n位,每位都为0 bitset a(b) a是unsigned long ......
用bitset做的一些题
用bitset做的一些题 代表的意义 \(1.\)一个序列的全或加(\(01\)背包) 数组\(a\)中去任意数量的数累加起来的所有情况: bitset<N> f; for(auto x : a) { f |= f << x; } 其中,\(f[idx] == 1\)表示存在起码一种组合加法,使得他 ......
【二进制拆分】【bitset】【主定理】
CF1856E2 差点场切啊。 默认已会 E1。 考虑对 E1 进行优化,发现瓶颈在于背包。 设当前子树以 \(u\) 为根,容易发现 \(\sum siz_{v_i}=siz_u-1\),显然要从这里下手。发现总值域较小是与普通背包不同的地方,要么个数少,要么值域小。不妨设背包的总容量为 \(W\ ......
【莫队】【bitset】【数据分治】P5313 [Ynoi2011] WBLT 题解
P5313 看到值域比较,又支持离线,可以想到莫队和桶。 考虑先将桶按 \(b\) 分段,将每段分别进行按位与运算,做完第 \(i\) 段时用于运算的桶全都为 \(0\),就可以直接得到答案。这显然可以用 bitset 优化。但是 STL 的 bitset 不支持分裂操作,所以需要手写。 当 \(b ......
【bitset】【线段树】CF633G Yash And Trees 题解
CF633G 简单题。 先看到子树加和子树质数个数和,果断转换为 dfs 序进行处理。 既然有区间求和,考虑线段树。 若对于每一个节点维护一个 \(cnt\) 数组,用二进制数 \(x\) 来表示,即当 \(cnt_i = 1\) 时第 \(i\) 位为 \(1\)。设当前节点为 \(u\),左右子 ......
C++ bitset 用法和应用
C++的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用1bit空间。 下面是具体用法 构造函数 bitset常用构造函数有四种,如下 bitset<4> bitset1; //无参构造,长度为4,默认每一位为0 bitset<8> bit ......
bitset 求解高维偏序
菜,题简单,trick 蠢,求别骂。 记录今天做题的时候遇到的一个小 trick。 先看一道题:P3810 【模板】三维偏序(陌上花开)。 平凡的三维偏序板子,相信大家都会用 CDQ/树套树/K-D tree 之类的优秀做法秒了吧! 然后看这个题:求五维偏序,\(n\le 3\times 10^4\ ......
STL——bitset的使用方法
# bitset ## 介绍 类似 $bool$ 数组一样的东西,储存的是二进制,但是每一位只占 $1bit$,可以优化你算法的时间和空间复杂度。 ## 储存 开一个bitset为: ```cpp bitsetbs; ``` 最左边为最低位(即第 $0$ 位),最右边为最高位。 在初始化的时候,是从 ......
bitset 优化莫队
[题目传送门:Ynoi跳进兔子洞](https://www.luogu.com.cn/problem/P4688) # 好题! 我们观察题目,发现题目让我们求的可以写成: $$(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size$$ 其中:$size$ 是 ......
H. Needle[FFT]或bitset
Problem - H - Codeforces 题意是给三面墙(简化为一条轴),然后给墙上的洞(简化成点),问多少直线可以从第一面墙穿出第三面墙。 要使三点共线,那么(b-a)=(c-b)即(a+c)=2*b 由于n是1e5所以O(n2)会超时。有两种做法 1.本题的任意两数相加的步骤类似多项式乘 ......
Codeforces Round 889 (Div. 1) B. Earn or Unlock(dp,bitset)
题目链接:https://codeforces.com/problemset/problem/1854/B 题目大致题意: 有n张卡牌从上到下堆叠,每张卡片有锁或不锁俩种状态,一开始第一张是不锁的; 对最上面的卡牌,如果他是不锁的状态,那么可以进行俩种操作: 1:从上到下,将v张被锁的卡牌解锁; 2 ......
bitset优化01可行背包
[例题传送门:『STA - R3』Aulvwc](https://www.luogu.com.cn/problem/T345186) 先讲bitset用法: 1,基础 下标:$5~4~3~2~1~0$ 数字:$0~0~0~0~1~0$ $bitset$ $s$表示一个$n$位的二进制数,空间复杂度: ......
为什么会变成这样呢? #4(bitset)
## bitset 维护01可行背包 给定 $n$ 个数 $a_1,\dots,a_n$,已知 $\sum a_i=O(n)$,求一种把 $a$ 分为两组的方案使得两组的和尽可能接近。 期望复杂度:$O(n\sqrt n\log n/\omega)$ 解答 把 $a_i$ 中相同的数合并,容易发现只 ......
【数据结构】bitset用法
# bitset用法 bitset可以说是一个多位二进制数,每八位占用一个字节,因为支持基本的位运算,所以可用于状态压缩,n位bitset执行一次位运算的时间复杂度可视为n/32. 输出只能用cout ## 1.构造: ```c++ int a = 5; string b = "1011"; cha ......
std::bitset 的常用函数
菜。 `flip`:反转。 `set()`:全部置 `1`。 `set(i)`:第 $i$ 位置 `1`。 `set(i, 0)`:第 $i$ 位置 `0`。 `reset`:置 `0`。 `count`:求 `1` 的个数。 `test`:返回第 $i$ 位是 `0/1`。 `any`:是否有 ` ......
Bitset使用总结
## 初始化 下面是初始化例子 ```c++ void solve() { bitsetdp;//初始化大小为7的bitset bitsetdp(5);//初始化为5的大小为7的bitset,即0000101 bitsetdp("0011010");//用字符串直接初始化 } ``` ## 修改 ` ......
Bitset用法
众所周知$Bitset$可以将一些$O(n)$的操作优化为$O(N/w)$ 相当于优化了$>=$一只$log$!!! $bitset$每一位占一个$bit$,而不是一个$Byte$!!! 若一次操作复杂度为 $O(N)$ $bitset$的操作复杂度为 $O(N/w)$ $w$为计算机字长,$w$位 ......
luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】
[TOC] # 题目大意 [题目链接](https://www.luogu.com.cn/problem/P3733 "题目链接") >给出一张 $n$ 个点 $m$ 条边的连通无向图,边带边权 $w_i$ 。有以下三种操作,共 $q$ 次: $\centerdot$在点 $x,y$ 之间加入一条边 ......
ACM-knowledge <bitset>
关于bitset,详见[参考](https://www.cnblogs.com/yifusuyi/p/10072729.html); ```cpp #include #include using namespace std; using LL = long long; int main() { bi ......
C++ bitset
C++ bitset是C++ STL库中的一个类,用于**存储二进制位的数组**,并提供了一些**位操作**的函数。下面是一些C++ bitset的语法: 1. **创建**一个bitset:可以使用以下语法创建一个bitset: `````c++ std::bitset bits; // 创建一个 ......
bitset粗略用法
1. 赛中一直在想怎么找到两个点的公共点,没想到bitset还可以直接&一下在count一下直接出来了,抓紧研究下bitset ``` bitset可以近乎为只存 1, 0的数组,和普通数组相比时间复杂度优异。 普通数组count之类的数组要n的时间复杂度,bitset只要n/32. 空间也与字符型 ......
std::bitset
# `std::bitset` ## 前言 感觉 ZGY 讲得不是很清楚(例题讲得有点少,而且感觉有一点乱),所以来写了这一篇文章。但是最好结合着[他的文章](https://qoj.fzoi.top/post/5276)一起学习。 ~~可能有错别字 错公式 错表达 大佬们请请多包涵 Orz。~~ ......
abc082d <bitset 状压dp>
### 题目 [D - FT Robot](https://atcoder.jp/contests/abc082/tasks/arc087_b) ### 思路 - 动态规划的方式记录每次行动后, 机器人在坐标系中所有可能位置 - 通过bitset对状态进行压缩, 即每个位置有机器人true or 没 ......
20230411 java.util.BitSet
## 简介 - `public class BitSet implements Cloneable, java.io.Serializable` - 没有实现 Set 接口 - 此类实现了一个按需增长的位向量 - 每个位对应一个布尔值 - BitSet 的位由非负整数索引 - 可以检查、设置或清除各 ......
2023年长沙学院程序设计竞赛(CCSUPC) H.序列MEX (分块 + bitset)
[传送门](https://ac.nowcoder.com/acm/contest/58954/H) **~~优雅,太优雅了~~** 解题思路 **因为总和不超过1e5,所以最多枚举到500,不知道为啥500会wa,1010就可以ac。考虑分块,每一块维护一个大小为1010的bitset。然后对于查 ......
好用的bitset——暴力的好帮手
会持续更新的。 # bitset C++ 的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用 1 bit空间。 bitset的原理大概是将很多数压成一个,从而节省空间和时间, 一般来说bitset会让你的算法复杂度 /32 ## 构造 bi ......