526互联

Bitset使用总结

发布时间 2023-08-02 16:43:02作者: HikariFears

初始化

下面是初始化例子

void solve()
{
    bitset<7>dp;//初始化大小为7的bitset
    bitset<7>dp(5);//初始化为5的大小为7的bitset，即0000101
    bitset<7>dp("0011010");//用字符串直接初始化
}

修改

void solve()
{
    bitset<4>dp(5);//0101
    dp[0]=0;//0100
}

相关函数

  1. count()：用于计算bitset中1的个数。
  2. any()：如果bitset中有一个位是1，那么返回true，否则返回false。
  3. none ()：如果bitset中每个位都是0，那么返回true，否则返回false。
  4. set ()：用于将bitset中的所有位置设置成1。
  5. reset ()：用于将bitset中的所有位置设置成0。
  6. flip ()：用于将bitset中的所有位置反转。

bitset动态规划例题

CF1855D

题意：给出n张牌，最开始只有第一张牌是解锁状态，其它牌都被锁住了，每张牌上有一个点数a[i]，每次可以进行一种操作：

1.解锁顶上的未解锁的a[i]张牌

2.获得a[i]的胜利点数

问最后能得到的最大点数是多少

Solution

定义\(dp_{i}\)表示能否通过若干次解锁操作刚好解锁到i，那么可以遍历a，初始化dp[1]=1，每次令dp|=dp<<a[i]，从而转移答案，而对于当前可以刚好解锁的情况，我们需要在更新答案后将其变为0，因为在更新完答案后它就不能转移到其他的位置了，此外，考虑到可能会超过n的范围，我们可以将bitset扩大到2n，以检测最后一次解锁操作的更新位置大于n的情况

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		s[i]=s[i-1]+a[i];
	}
	bitset<200005>dp;
	
	dp[1]=1;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		dp|=dp<<a[i];
		if(dp[i])
		{
			ans=max(ans,s[i]-i+1);
			dp[i]=0;
		}
	}
//	cout<<dp<<"\n";
	for(int i=n+1;i<=2*n;i++)
	{
		if(dp[i])
		{
			ans=max(ans,s[n]-i+1);
			dp[i]=0;
		}
	}
	cout<<ans<<"\n";
}