牛客----Prize （bitset优化暴力）

题目链接

题面：

题解：
很明显本题贪心匹配是最优的。
但是正向贪心暴力匹配会T，但是逆向就能A了。
但是用bitset写会更快一些。
以下为bitset写法。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#define ll long long
#define pr make_pair
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=1000000007;
const int maxn=2000100;
const double eps=1e-8;
const double dnf=1e20;
const double pi=acos(-1.0);
char str[maxn];
bitset<820>b[10],now;
int main(void)
{int n,m,k,x;scanf("%d%d",&n,&m);scanf("%s",str+1);for(int i=1;i<=m;i++){scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d",&x);b[x].set(i);}}//now用来记录已经匹配了的个数。//若now的第m为1，则说明已经匹配了m个了。int ans=0;for(int i=1;i<=n;i++){now<<=1;now.set(1);//now当前有1的位上需要匹配str[i]now=now&b[str[i]-'0'];//now需要匹配的位上 可选str[i]的 位匹配成功if(now[m]==1) ans++,now.reset();}if(ans==0) printf("Failed to win the prize\n");else printf("%d\n",ans);return 0;
}