bitset的用法

bitset的用法以及优化方案

基本用法：https://oi-wiki.org/lang/csl/bitset/
bitset是以字节为单位存储的，所以单次操作的时间复杂度是O（n / m),m为机器的位数，n是bitset对象的长度。这样就可以优化O(n)时间复杂度，避免超时
例题：P10914 [蓝桥杯 2024 国 B] 跳石头 https://www.luogu.com.cn/problem/P10914

#include <bits/stdc++.h>
#define PRINT_PI(presision, value) std::cout << std::fixed << std::setprecision(presision) << (value) << std::endl
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
const int N = 4e4 + 10;
std::map<i64, std::pair<i64, i64>> mp;
std::bitset<N> dp[N];
i64 a[N];
void solve() {
	int n;
    std::cin >> n;
    mp.clear();
    // 预处理出每个位置可以由哪些地方跳来
    for (int i = 1; i <= n; i ++) {
        std::cin >> a[i];
        if (i + a[i] <= n) mp[i + a[i]].first = i;
        if (2 * i <= n) mp[2 * i].second = i;
    }
    i64 res = 0;
    // dp[i]表示从i开始跳的最大值，所以要倒着枚举；如果从1~n枚举，那么dp[i]的意义就是以i结束的最大值了，与题意不符
    for (int i = n; i >= 1; i --) {
        dp[i][a[i]] = 1;
        if (i + a[i] <= n) dp[i] |= dp[i + a[i]];
        if (i * 2 <= n) dp[i] |= dp[i * 2];
        res = std::max(res, (i64)(dp[i].count()));
    }
    std::cout << res << "\n";
}
int main()
{	
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1;
	// std::cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}

这里我们用bitset将原本O(n²)时间复杂度的程序优化成O(n² / m)，避免超时，并且Bitset支持的位运算使用很方便，避免大量循环迭代

来源链接：https://www.cnblogs.com/zj-cnbolgs/p/18813388