HDU5972Regular Number(ShiftAnd算法 bitset)

题意

第一行的\(n\)表示模式串长度为\(n\)

接下来\(n\)行，每行开头有一个整数\(num\)表示匹配串中该位置的字符可以在\(num\)个桅子花出现，接下来输入这\(num\)个位置

最后一行一个模式串

sol

"it contains a set of test data"的意思原来是说只有一组测试数据

shiftand算法，非常interesting，推荐一篇讲的非常好的

这题就是给出了\(b\)数组，然后暴力搞一下就行了。。

垃圾题目卡我读入卡我输出

#include<bits/stdc++.h>
#define chmax(a, b) (a = (a > b ? a : b))
#define chmin(a, b) (a = (a < b ? a : b))
#define ll long long
//#define int long long 
using namespace std;
const int maxn = 5e6 + 10;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n;
char s[maxn], tmp = '\0';
bitset<1001> b[11], ans;
void solve() {
    for(int i = 0; i <= n; i++) b[i].reset(); ans.reset();
    for(int i = 0; i < n; i++) {
        int num = read();
        for(int j = 0; j < num; j++) b[read()].set(i);
    }
    gets(s);
    int l = strlen(s);
    for(int i = 0; i < l; i++) {
        ans <<= 1; ans.set(0);
        ans &= b[s[i] - '0'];
        if(ans[n - 1] == 1) swap(s[i + 1], tmp), puts(s + i - n + 1), swap(s[i + 1], tmp);
    }
}
main() {
  scanf("%d", &n); solve();
}
/*
4
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524
*/