E-Prize
做法:bitset常见套路了。
用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]);
}