bitset

如果我们只需要 位与 位或 位异或，那么直接自己压位也很简单
If we need xor or and, it easy to implement ours.

但是如果我们需要 左移 右移，自己实现就很麻烦
If we need shift left and shift right, it hard to implement ours.

3个用法

1. Floyd
2. bitset优化(零一)背包
3. bitset解方程
4. ....其他题目，比如 CF878D

P4306 [JSOI2010]连通数

Floyd O(n^3) bitset 优化
暴力BFS O(nm)

不存在O(n + m)的做法

for (int k = 0; k < n; k++)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			d[i][j] |= d[i][k] && d[k][j];
		}
	}
}


for (int k = 0; k < n; k++)
{
	for (int i = 0; i < n; i++)
	{
		if (d[i][k])
		{
			for (int j = 0; j < n; j++)
			{
				d[i][j] |=  d[k][j];
				// 第i行 |= 第k行
			}
		}
	}
}

for (int k = 0; k < n; k++) {
	for (int i = 0; i < n; i++) {
		if (d[i][k]) {
			d[i] |= d[k];
		}
	}
}

spoj ADACOINS

直接背包
f |= f << x;

atcoder agc020_c

注意到子集和都是成对的，
x, s-x
唯一不成对的是s，因为没有0
所以等价于求大于等于s/2最小的子集和是什么

bzoj 3697
http://hzwer.com/3697.html
哪里出错了？

bitset优化解方程：
spoj
JZPLIT
JZPLIT2

spoj ADAFUROW

bitset 优化集合 求并 求交 求异或 求差
https://www.spoj.com/problems/ADAFUROW/

spoj ADACHERY

bitset 求三角形个数
https://www.spoj.com/problems/ADACHERY/