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 ......

目录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 是 C++ 自带的一个STL。 bitset是一个01串，01串上的每一位就是1bit，在一些场合优化bool数组。 初始化 使用 bitset 需要用到 \(\text{“#include<bitset> ”}\) ，不过这个头文件在万能头里就自带了，可以直接用。 ......

https://codeforces.com/contest/1856/problem/E2 结论是显然的，关键是有一些科技在里面 bitset+二进制优化 具体分析可以参考https://codeforces.com/blog/entry/98663 简而言之就是可以通过\(O(\frac{C\s ......

1、简介 bitset 在 bitset 头文件中，它类似数组，并且每一个元素只能是０或１，每个元素只用１bit空间。 //头文件 #include<bitset> 2、初始化定义 初始化方法 代码 含义 bitset a a有n位，每位都为0 bitset a(b) a是unsigned long ......

用bitset做的一些题 代表的意义 \(1.\)一个序列的全或加(\(01\)背包) 数组\(a\)中去任意数量的数累加起来的所有情况： bitset<N> f; for(auto x : a) { f |= f << x; } 其中，\(f[idx] == 1\)表示存在起码一种组合加法，使得他 ......

CF1856E2 差点场切啊。 默认已会 E1。 考虑对 E1 进行优化，发现瓶颈在于背包。 设当前子树以 \(u\) 为根，容易发现 \(\sum siz_{v_i}=siz_u-1\)，显然要从这里下手。发现总值域较小是与普通背包不同的地方，要么个数少，要么值域小。不妨设背包的总容量为 \(W\ ......

P5313 看到值域比较，又支持离线，可以想到莫队和桶。 考虑先将桶按 \(b\) 分段，将每段分别进行按位与运算，做完第 \(i\) 段时用于运算的桶全都为 \(0\)，就可以直接得到答案。这显然可以用 bitset 优化。但是 STL 的 bitset 不支持分裂操作，所以需要手写。 当 \(b ......

CF633G 简单题。 先看到子树加和子树质数个数和，果断转换为 dfs 序进行处理。 既然有区间求和，考虑线段树。 若对于每一个节点维护一个 \(cnt\) 数组，用二进制数 \(x\) 来表示，即当 \(cnt_i = 1\) 时第 \(i\) 位为 \(1\)。设当前节点为 \(u\)，左右子 ......

C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。 下面是具体用法 构造函数 bitset常用构造函数有四种，如下 bitset<4> bitset1; //无参构造，长度为４，默认每一位为０ bitset<8> bit ......

菜，题简单，trick 蠢，求别骂。 记录今天做题的时候遇到的一个小 trick。 先看一道题：P3810 【模板】三维偏序（陌上花开）。 平凡的三维偏序板子，相信大家都会用 CDQ/树套树/K-D tree 之类的优秀做法秒了吧！ 然后看这个题：求五维偏序，\(n\le 3\times 10^4\ ......

# bitset ## 介绍 类似 $bool$ 数组一样的东西，储存的是二进制，但是每一位只占 $1bit$，可以优化你算法的时间和空间复杂度。 ## 储存 开一个bitset为： ```cpp bitsetbs; ``` 最左边为最低位（即第 $0$ 位），最右边为最高位。 在初始化的时候，是从 ......

[题目传送门：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$ 是 ......

Problem - H - Codeforces 题意是给三面墙(简化为一条轴)，然后给墙上的洞（简化成点），问多少直线可以从第一面墙穿出第三面墙。 要使三点共线，那么(b-a)=(c-b)即(a+c)=2*b 由于n是1e5所以O(n2)会超时。有两种做法 1.本题的任意两数相加的步骤类似多项式乘 ......

题目链接：https://codeforces.com/problemset/problem/1854/B 题目大致题意： 有n张卡牌从上到下堆叠，每张卡片有锁或不锁俩种状态，一开始第一张是不锁的； 对最上面的卡牌，如果他是不锁的状态，那么可以进行俩种操作： 1：从上到下，将v张被锁的卡牌解锁； 2 ......

[例题传送门：『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$位的二进制数，空间复杂度： ......

## 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可以说是一个多位二进制数，每八位占用一个字节，因为支持基本的位运算，所以可用于状态压缩，n位bitset执行一次位运算的时间复杂度可视为n/32. 输出只能用cout ## 1.构造： ```c++ int a = 5; string b = "1011"; cha ......

菜。 `flip`：反转。 `set()`：全部置 `1`。 `set(i)`：第 $i$ 位置 `1`。 `set(i, 0)`：第 $i$ 位置 `0`。 `reset`：置 `0`。 `count`：求 `1` 的个数。 `test`：返回第 $i$ 位是 `0/1`。 `any`：是否有 ` ......

## 初始化 下面是初始化例子 ```c++ void solve() { bitsetdp;//初始化大小为7的bitset bitsetdp(5);//初始化为5的大小为7的bitset，即0000101 bitsetdp("0011010");//用字符串直接初始化 } ``` ## 修改 ` ......

众所周知$Bitset$可以将一些$O(n)$的操作优化为$O(N/w)$ 相当于优化了$>=$一只$log$!!! $bitset$每一位占一个$bit$，而不是一个$Byte$!!! 若一次操作复杂度为 $O(N)$ $bitset$的操作复杂度为 $O(N/w)$ $w$为计算机字长，$w$位 ......

[TOC] # 题目大意 [题目链接](https://www.luogu.com.cn/problem/P3733 "题目链接") >给出一张 $n$ 个点 $m$ 条边的连通无向图，边带边权 $w_i$ 。有以下三种操作，共 $q$ 次： $\centerdot$在点 $x,y$ 之间加入一条边 ......

关于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++ STL库中的一个类，用于**存储二进制位的数组**，并提供了一些**位操作**的函数。下面是一些C++ bitset的语法： 1. **创建**一个bitset：可以使用以下语法创建一个bitset： `````c++ std::bitset bits; // 创建一个 ......

1. 赛中一直在想怎么找到两个点的公共点，没想到bitset还可以直接&一下在count一下直接出来了，抓紧研究下bitset ``` bitset可以近乎为只存 1， 0的数组，和普通数组相比时间复杂度优异。 普通数组count之类的数组要n的时间复杂度，bitset只要n/32. 空间也与字符型 ......

# `std::bitset` ## 前言 感觉 ZGY 讲得不是很清楚（例题讲得有点少，而且感觉有一点乱），所以来写了这一篇文章。但是最好结合着[他的文章](https://qoj.fzoi.top/post/5276)一起学习。 ~~可能有错别字 错公式 错表达 大佬们请请多包涵 Orz。~~ ......

### 题目 [D - FT Robot](https://atcoder.jp/contests/abc082/tasks/arc087_b) ### 思路 - 动态规划的方式记录每次行动后, 机器人在坐标系中所有可能位置 - 通过bitset对状态进行压缩, 即每个位置有机器人true or 没 ......

## 简介 - `public class BitSet implements Cloneable, java.io.Serializable` - 没有实现 Set 接口 - 此类实现了一个按需增长的位向量 - 每个位对应一个布尔值 - BitSet 的位由非负整数索引 - 可以检查、设置或清除各 ......

[传送门](https://ac.nowcoder.com/acm/contest/58954/H) **~~优雅，太优雅了~~** 解题思路 **因为总和不超过1e5，所以最多枚举到500，不知道为啥500会wa，1010就可以ac。考虑分块，每一块维护一个大小为1010的bitset。然后对于查 ......

会持续更新的。 # bitset C++ 的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用 １ bit空间。 bitset的原理大概是将很多数压成一个，从而节省空间和时间, 一般来说bitset会让你的算法复杂度 /32 ## 构造 bi ......