清新小容器 — bitset
Nickel_Angel
2019-10-22 08:17:04
bitset 是 STL 中一个不错的容器，在一些可以使用状压的题目中，她可以为记录二进制状态提供更大的空间。
bitset 位运算的时间复杂度为 $O(\frac {n} {w})$ ，其中 $w$ 为 $32$ 或 $64$ 。这样我们可以用较小的常数去用 $O(n^2)$ 的暴力通过一些题目。
***
[P1537 弹珠](https://www.luogu.org/problem/P1537)
这是一个布尔背包问题，若设所有弹珠的价值和为 $sum$ ，我们只需关心 $\frac {sum} {2}$ 能否用其他弹珠的和表示出来。考虑使用背包解决这个问题。设 $dp[i][j]$ 表明考虑到第 $i$ 个物品时 (根据题意其价值为 $m_i$ )，是否可以表示出 $j$ 的价值，不难得出状态转移方程为：$dp[i][j] = dp[i][j] $ `bitor` $ dp[i - 1][j - i \times k]\text{ }k \in [0, m_i]$ 。
但我们发现在本题中我们只关心某个价值能不能被表示出来，而不关心它的代价或方案数……故考虑使用 bitset 优化。我们可以直接将状态记录在一个 01 串里，其中若该 01 串的第 $i$ 位若为 1 则表示 $i$ 可以被表示出来。这样每次转移时直接在 bitset 上操作即可。
Code：
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
namespace Primary
{
int w[10], sum;
bitset<10010> help;
void main()
{
int Case = 0;
while (++Case)
{
help.reset(), sum = 0;
for (int i = 1; i < 7; ++i)
{
scanf("%d", w + i);
sum += w[i] * i;
}
if (!sum) return;
printf("Collection #%d:\n", Case);
if (sum & 1)
{
puts("Can't be divided.");
puts("");
continue;
}
help.set(0);
for (int i = 1; i < 7; ++i)
{
for (int j = 1; j <= w[i]; ++j)
{
help |= (help << i);
}
}
if (help.test(sum >> 1)) puts("Can be divided.");
else puts("Can't be divided.");
puts("");
}
}
}
int main()
{
Primary::main();
return 0;
}
```
***
[P2757 等差子序列]( https://www.luogu.org/problem/P2757 )
题目大意为给定一个全排列，询问在其中是否存在一个长度至少为 $3$ 的等差子序列。但其实我们只需找到长度为 $3$ 的等差子序列即可。
本题正解为线段树 + hash，但我们可以使用自带小常数的 bitset 通过本题。
不难发现，由于本题给定的 $a_i$ 为 $1 \cdots n$ 的全排列，我们可以使用一个长度为 $n$ 的布尔数组，其中第 $i$ 位的值表明 $i$ 这个数是否出现过。初始这个布尔数组的值为空，我们依次用序列中的值更新这个布尔数组。
我们每一次更新（假定我们当前扫到序列中的值为 $a_i$），就查询以 $a_i$ 为中心，**以 $1$ 或 $n$ 为边界的对称区域**是否回文，如果回文则说明可以与 $a_i$ 构成等差序列的值已经在前面出现过了。若不回文，由于整个序列是一个 $1 \sim n$ 的全排列，则另一项可以与 $a_i$ 构成等差数列的值一定会在后面出现。
考虑到我们可以使用 bitset 代替布尔数组，而为了便于我们判断回文串，我们可以考虑同时维护两个 bitset：
一个 bitset （$pre$）正序存储 $1 \sim n$ 之间的数是否被出现过（即 bitset 第 $i$ 位若为 $1$ ，则表明 $i$ 这个数曾出现过）。
一个 bitset （$suf$）倒序存储 $1 \sim n$ 之间的数是否被出现过（即 bitset 第 $i$ 位若为 $1$ ，则表明 $n - i + 1$ 这个数曾出现过）。
在依次将序列中的数（设其为 $a_i$）更新 bitset 时，要判断是否会以 $a_i$ 为中心构成回文，需根据 $a_i$ 与 $\lfloor \frac {n} {2} \rfloor$ 的大小关系，判断以 $a_i$ 为中心对称区域的边界。若 $a_i \leq \lfloor \frac {n} {2} \rfloor$ ，则边界为 $n$ ，反之，边界为 $1$ 。由于还要防止多余位数的干扰，故开一个 bitset（$base$），令其 $1 \sim n$ 位的值均为 $1$ ，不难发现其可以让其左移 $x$ 位后与一个 bitset 按位与，这样就使得那个 bitset 只保留下了 $n - x$ 位。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
namespace Primary
{
const int maxn = 10010;
int n, T, x;
bitset<maxn> pre, suf, base, cmp1, cmp2;
bool check(int x)
{
//下面的式子推了半天QAQ但奈何不知如何表达
if (x > n / 2)//这里对称区域的边界为 1
{
cmp1 = (pre >> (x - 1));
cmp2 = (suf >> (n - x)) & (base >> (x - 1));
}
else//这里对称区域的边界为 n
{
cmp1 = (pre & (base >> (n - x)));
cmp2 = ((suf >> (n - 2 * x + 1)) & (base >> (n - x)));
}
cmp1.set(0), cmp2.set(0);//由于 bitset 是从第一位开始使用的，故要消除第 0 位的影响
return cmp1 != cmp2;
}
void main()
{
scanf("%d", &T);
bool flag;
while (T--)
{
pre.reset(), suf.reset(), base.reset();//多组数据，注意清空
scanf("%d", &n);
for (int i = 1; i <= n; ++i) base.set(i);
flag = false;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &x);
if (flag) continue;
pre.set(x), suf.set(n - x + 1);
if (check(x)) flag = true;
}
puts(flag ? "Y" : "N");
}
}
}
int main()
{
Primary::main();
return 0;
}
```
***
[P3674 小清新人渣的本愿](https://www.luogu.org/problem/P3674)
由于本题没有修改操作，故可以使用离线做法，考虑莫队。
假设当前序列中存在一对 $a, b$ ，使得 $a - b = x$ ，移项得：$a = b + x$ ，故可以考虑像上一道题一样维护一个正序记录序列中数的出现情况的 bitset（$pre$）。故每一次减法的询问可以转化成 $pre \text{ } \& \text{ } (pre << x)$ 。
考虑加法，若当前序列中存在一对 $a, b$ ，使得 $a + b = x$，我们可以像上一题一样维护一个反向记录序列中数的出现情况的 bitset（$suf$）。故每一次加法询问可以转化为 $pre \text{ } \& \text{ } (suf >> (n - x))$，注意这里的 bitset 是从第 0 位开始使用的，因为序列中可能会出现 0 。
对于乘法，我们只需 $O(\sqrt{x})$ 枚举 $x$ 的质因子即可。
```cpp
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
namespace IO
{
template<typename T>
inline void input(T &x)
{
x = 0;
register char ch = getchar();
register bool f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}
}
using namespace IO;
namespace Primary
{
const int maxn = 1e5 + 10;
int n, m, a[maxn], cnt[maxn], tot;
bool ans[maxn];
bitset<maxn> pre, suf;
struct event
{
int opt, s, e, v, id;
bool operator < (const event &rhs) const
{
return (s / tot) ^ (rhs.s / tot) ? s < rhs.s :
((s / tot) & 1) ? e < rhs.e : e > rhs.e;
}
}q[maxn];
inline void add(int x)
{
x = a[x];
if (!(cnt[x]++)) pre[x] = suf[n - x] = true;//在指针扫动时直接维护 bitset 即可
}
inline void del(int x)
{
x = a[x];
if (!(--cnt[x])) pre[x] = suf[n - x] = false;
}
void main()
{
input(n), input(m);
tot = sqrt(n);
for (int i = 1; i <= n; ++i)
input(a[i]);
for (int i = 1, opt, s, e, x; i <= m; ++i)
{
input(q[i].opt), input(q[i].s), input(q[i].e), input(q[i].v);
q[i].id = i;
}
sort(q + 1, q + m + 1);
int L = q[1].s, R = L - 1, ql, qr, x;
for (int i = 1; i <= m; ++i)
{
ql = q[i].s, qr = q[i].e;
while (ql > L) del(L++);
while (ql < L) add(--L);
while (qr > R) add(++R);
while (qr < R) del(R--);
x = q[i].v;
if (q[i].opt == 1)
ans[q[i].id] = (pre & (pre << x)).any();
else if (q[i].opt == 2)
ans[q[i].id] = (pre & (suf >> (n - x))).any();
else
{
for (int j = 1; j * j <= x; ++j)
{
if (x % j != 0) continue;//注意去除不是 x 的约数
if (pre[j] && pre[x / j])
{
ans[q[i].id] = true;
break;
}
}
}
}
for (int i = 1; i <= m; ++i)
puts(ans[i] ? "hana" : "bi");
}
}
int main()
{
Primary::main();
return 0;
}
```
***
[P6328 我是仙人掌](https://www.luogu.com.cn/problem/P6328)
注意到 $n$ 很小，我们就有足够的时间跑多源最短路。又注意到边权均为 $1$ ，故可以直接拿 bfs 跑多源最短路。在预处理多源最短路后，考虑设一个 bitset $f[u][i]$ 表明到 $u$ 最短路（即距离）长度为 $i$ 的点有哪些，若 $f[u][i]$ 第 $v$ 位为 $1$ ，则说明存在一条从 $u$ 至 $v$ 长度为 $i$ 的最短路。
由于题目中询问的是 $dis(u, x_i) \leq y_i$ ，故我们做个前缀按位或即可。bitset 可以帮我们做到去重的作用。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;
namespace Primary
{
const int inf = 1005;
int n, m, q, dis[1010][1010];
bitset<1010> f[1010][1010];
vector<int> e[1010];
void bfs(int S, int *dis)
{
for (int i = 1; i <= n; ++i) dis[i] = inf;//将 dis 初始化为 inf
queue<int> q;
q.push(S);
dis[S] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (unsigned i = 0, v; i < e[u].size(); ++i)
{
v = e[u][i];
if (dis[v] == inf)
{
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
for (int i = 1; i <= n; ++i) f[S][dis[i]].set(i);
for (int i = 1; i <= n; ++i) f[S][i] |= f[S][i - 1];
}
void main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1, u, v; i <= m; ++i)
{
scanf("%d%d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
for (int i = 1; i <= n; ++i) bfs(i, dis[i]);
while (q--)
{
bitset<1010> ans;
int u, v, x;
scanf("%d", &x);
while (x--)
{
scanf("%d%d", &u, &v);
if (v > n) v = n;//注意一个 n 个点的图中最短路长度不会超过 n
ans |= f[u][v];
}
printf("%d\n", ans.count());
}
}
}
int main()
{
Primary::main();
return 0;
}
```
***
[CF914F Substrings in a String](https://www.luogu.org/problem/CF914F)
感谢 @[ywy_c_asm](https://www.luogu.org/user/125124) 学长推荐本题 w！
本题看上去像是 kmp 动态修改，但实际上是 bitset 暴力 QwQ
题目中给定的字符串只会出现 26 种字符（即所有小写字母），故考虑开 26 个 bitset 分别记录 26 种字符在 $s$ 中出现的位置。
那么修改操作（即 1 操作）可直接在对应 bitset 中修改即可。
考虑询问操作（即 2 操作），发现两个串匹配的过程（下文设询问给出的字符串为 $t$，初始给定的字符串为 $s$）可以看成先对于 $t$ 的第一个字符依次在 $s$ 中寻找其在 $s$ 中出现的位置，并判断以这些位置为起点，且与 $t$ 长度相同的 $s$ 的子串是否和 $t$ 恰好匹配。我们可以维护一个 01 串表示 $s$ 的每个位置是否存在以该位置为起点的子串和 $t$ 恰好匹配，再通过前缀和的思想，设询问区间为 $[l, r]$，其答案即为 $[1, r - |t| + 1]$ 区间的匹配数减去 $[1, l]$ 区间的匹配数。
注意本篇代码的字符串下标是从 0 开始的，而题目中的字符串下标是从 1 开始的。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
namespace Primary
{
const int maxn = 1e5 + 10;
char s[maxn], t[maxn];
int q;
bitset<maxn> help[26], ans;
void main()
{
scanf("%s%d", s, &q);
int len = strlen(s);
for (int i = 0; i < len; ++i)
help[s[i] - 'a'].set(i);
int opt, ql, qr;
while (q--)
{
scanf("%d", &opt);
if (opt == 1)
{
scanf("%d%s", &ql, t), --ql;
help[s[ql] - 'a'].set(ql, 0);
help[t[0] - 'a'].set(ql);
s[ql] = t[0];
}
else
{
scanf("%d%d%s", &ql, &qr, t);
len = strlen(t);
if (len > qr - ql + 1)//若 t 的长度大于询问长度,显然无解
{
puts("0");
continue;
}
ans.set();
for (int i = 0; i < len; ++i)
ans &= (help[t[i] - 'a'] >> i);
int ans_l = (ans >> (ql - 1)).count();
int ans_r = (ans >> (qr - len + 1)).count();
printf("%d\n", ans_l - ans_r);
}
}
}
}
int main()
{
Primary::main();
return 0;
}
```
***
[P5640 【CSGRound2】逐梦者的初心](https://www.luogu.org/problem/P5640)
多亏了前一道题的铺垫，让我想到了本题 $O(\frac {m^2} {w})$ 的正解。
~~然而比赛时没调出来QAQ~~
感觉题目中的式子比较难受 >_<，故考虑将其转化成偏移量的形式：
> 初始给定一个字符串 $s$ 和一个空串 $t$ 。每次操作会在 $t$ 的首或尾插入一个字符。每次插入后询问存在多少个 $j \in [0, |t| - 1]$ 使得对于每一个 $i \in [1, |t| - j]$，都满足 $s_i \neq t_{i + j}$ 。
发现对于每个 $j$ 均判断一遍每一个位置 $i$ 均满足 $s_i \neq t_{i + j}$ 需要关注多个对象，不好维护，故考虑判断其逆命题是否成立，即我们只需对于每一个 $j$ 判断是否存在一个位置 $i$ 使得 $s_i = t_{i + j}$ 即可。
统计一次答案我们只需扫描一遍序列即可，我们发现这个过程可以像前一道题一样使用 bitset 进行优化，然而这样可能导致我们在修改 $t$ 时需要修改多个 bitset（本题字符集大小相对来说较大）导致复杂度不优。
这正启发我们关注每一次修改时会对答案造成什么样的影响：
对于在 $t$ 的末尾插入的一个字符来说，偏移量 $j \in [0, |t| - 1]$ 对答案的贡献均有可能改变，但我们发现，我们只需关注新插入的字符在 $s_{1 \cdots |t|}$ 中出现的位置即可。这个可以直接对于每种字符维护一个 bitset 记录。
对于在 $t$ 的开头插入的一个字符来说，不难发现原来偏移量为 $j$ 时的答案变成了现在偏移量为 $j + 1$ 时的答案。故可以维护一个 bitset（设其为 $now$），其第 $j$ 位表明偏移量为 $j$ 是否对答案有贡献。故在开头插入时只需令 $now$ 左移一位即可。当然，还需考虑到加入的字符对答案的影响。
注意只有 $s$ 的前 $m$ 位会对答案产生影响。故将 bitset 的长度设为 $m$ 即可。
```cpp
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
template<typename T>
inline bool chkmax(T& x, const T& y) {return x < y ? (x = y, true) : false;}
namespace IO
{
template<typename T>
inline void input(T& x)
{
x = 0;
register char ch = getchar();
register bool f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}
}
using IO::input;
namespace Primary
{
int n, m;
bitset<35000> id[1010], now, base;
void main()
{
input(n), input(m);
register int i, x, opt;
for (i = 1; i <= n; ++i)
{
input(x);
if (i <= m) id[x].set(i);
}
base.set();
for (i = 1; i <= m; ++i)
{
input(opt), input(x);
base.set(i, 0);//限制对答案产生贡献的长度
if (opt == 0) now = (now << 1) | id[x];
else now |= id[x] << (i - 1);
printf("%llu\n", (~(now | base)).count());
}
}
}
int main()
{
Primary::main();
return 0;
}
```