HDU5972Regular Number(ShiftAnd算法 bitset)

小灰灰 2022-03-29 02:56 118阅读 0赞

## 题意 ##

[题目链接][Link 1]

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

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

最后一行一个模式串

## Sol ##

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

ShiftAnd算法，非常interesting，推荐一篇讲的非常好的[blog][]

这题就是给出了\\(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
    */

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5972
[blog]: https://blog.csdn.net/silence401/article/details/77446537

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关 bitset

bitset初始化： include<bits/stdc++.h> using namespace std; int main(){

短命女/ 2023年06月13日 03:22/ 0 赞/ 23 阅读

相关 HDU 5890-Eighty seven【背包 bitset优化】

题意：给你n(n<50)张牌，让后q(100000)次询问，每次会抽调三张牌，然后问你剩下的牌数能否拼成87. 思路：这题可以用背包来做，预处理出所有情况下的答案，但是会超

墨蓝/ 2023年05月31日 03:10/ 0 赞/ 9 阅读

相关 Hdu 1502 Regular Words (java高精度 + DP)

题意：ABC每个字母有n个，求满足要求的排列的个数：在该排列的任意前缀中满足 A的个数不少于B的个数不少于C的个数。思路：DP，dp\[i\]\[j\]\[k\]表示该串

矫情吗；*/ 2022年08月25日 01:27/ 0 赞/ 24 阅读

相关 HDU 5413 CRB and Roads【bitset】

判断u→v这条边是不是redundant就是看有没有另一条u→p1→p2→p3.....→v路径的存在。因为图是有向无环图，所以存在拓扑序，那么很明显有u,p1,p2,p

骑猪看日落/ 2022年08月04日 09:28/ 0 赞/ 193 阅读

相关 hdu--6055--Regular polygon

Regular polygon Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K

心已赠人/ 2022年06月11日 02:25/ 0 赞/ 158 阅读

相关 bitset

写在前面： LeetCode刷着题，遇到一个黑科技bitset，之前没有遇到过。 -------------------- bitset存储位（元素只有两个可能的值：

超、凢脫俗/ 2022年06月02日 01:38/ 0 赞/ 215 阅读

相关 bitset

bitset 类简化了位集的处理，有些程序要使用二进制位的有序集来保存一组项或条件的标志位，可以考虑使用bitset。需要的文件： \include <bitset

落日映苍穹つ/ 2022年05月27日 05:53/ 0 赞/ 195 阅读

相关 HDU5972Regular Number(ShiftAnd算法 bitset)

题意 [题目链接][Link 1] 第一行的\\(n\\)表示模式串长度为\\(n\\) 接下来\\(n\\)行，每行开头有一个整数\\(num\\)表示匹配串中该位

小灰灰/ 2022年03月29日 02:56/ 0 赞/ 119 阅读

相关矩阵乘法分配律+bitset优化——hdu4920

因为是模3，所以把原矩阵拆成两个01矩阵，然后按分配律拆开分别进行矩阵乘法，行列用bitset来存进行优化即可注意 int bitset<int>::count() 函数

Bertha 。/ 2021年12月01日 16:52/ 0 赞/ 250 阅读

相关 bitset

1 \include < iostream > 2 \include < bitset > 3 using namespace std;

我就是我/ 2021年11月10日 00:26/ 0 赞/ 280 阅读