本文主要是介绍E-Prize bitset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
E-Prize
题目链接
做法：bitset常见套路了。
类似做法：博客 题目链接： 富豪凯匹配串
以及bitset优化01背包：博客 题目链接：回到过去
用bitset 的 now now的每一位i代表是否有连续的i个出现在s串中，dp一下就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,M=1000;
char s[N];
bitset<M>b[12],now,pre;
int n,m,dp[N];
int main()
{scanf("%d%d",&n,&m);scanf("%s",s+1);for(int i=1;i<=m;++i){int num;scanf("%d",&num);while(num--){int x;scanf("%d",&x);b[x].set(i);}}for(int i=1;i<=n;++i){pre<<=1;pre.set(1);//每一个i肯定有连续的1位存在now=pre&b[s[i]-'0'];//now的每一位i代表是否有连续的i位 出现在s串中if(now[m]) dp[i]=dp[i-m]+1;else dp[i]=dp[i-1];pre=now;//保存前一个状态}if(!dp[n]) puts("Failed to win the prize");else printf("%d\n",dp[n]);}
这篇关于E-Prize bitset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
