HDU5972Regular Number(ShiftAnd算法 bitset)

小灰灰 2022-03-29 02:56 76阅读 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 条评论，76人围观）

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

相关阅读

相关理解BitSet

先来看几道面试题： > 1、统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序。 > > 2、现在有1千万个随机数，随机数的范围在1到1亿之间，要求写出一种算法，

Bertha 。/ 2022年09月24日 06:29/ 0 赞/ 147 阅读

相关 HDU 5413 CRB and Roads【bitset】

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

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

相关 hdu--6055--Regular polygon

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

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

相关 bitset

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

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

相关 bitset

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

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

相关 C++ bitset

%%% [https://blog.csdn.net/weixin\_38686780/article/details/77200536][https_

逃离我推掉我的手/ 2022年04月15日 02:25/ 0 赞/ 154 阅读

相关 HDU5972Regular Number(ShiftAnd算法 bitset)

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

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

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

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

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

相关 bitset

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

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

相关 Regular

import java.util.regex.Matcher; import java.util.regex.Pattern; public

不念不忘少年蓝@/ 2021年09月11日 07:12/ 0 赞/ 141 阅读