Gym - 101174E Passwords AC自动机+额外的限制条件+状态压缩dp - ProLightsfx的技术成长

Problem E Passwords AC自动机+额外的限制条件+状态压缩dp

Source

SWERC'2016 Universidade do Porto

Gym - 101174E

My Solution

题意：给出n个由小写字母模式串，用大写字母、小写字母、十进制数字构造的长度为[A, B]的字符串，

且满足一下限制条件：1、必须有至少一个大写字母至少一个小写字母和一个数字。

2、不包含任一模式串(不区分大小写)。

3、对于o、i、e、s、t，在模式串时和0、1、3、5、7不区分。

求构造出的满足条件的字符串种数。

AC自动机+额外的限制条件+状态压缩dp

首先这题的原始版本是给出n模式串，构造不含任一模式串的长度为m的字符串种类数 http://blog.csdn.net/prolightsfxjh/article/details/54729646。

然后这题添加1、用大小写+数字进行构造+不区分大小写。

2、构造出的字符串有至少一个大写字母至少一个小写字母和一个数字。

3、对于o、i、e、s、t，在模式串时和0、1、3、5、7不区分。

对于第二个条件，可以直接添加一维dp[8] 来状态压缩。

对于第一个条件则转移的时候直接转移2次即可，//mod( dp[ac.ch[j][k]][i][w | 1] += dp[j][i-1][w] ); mod( dp[ac.ch[j][k]][i][w | 2] += dp[j][i-1][w] );

对于第三个条件则如果是o、i、e、s、t 则在不是危险节点的时候额外转移一次，//mod( dp[ac.ch[j][k]][i][w | 4] += dp[j][i-1][w] );

其它数字则不管当前节点是否为危险节点都进行转移。

答案就是 sigma{dp[0 ~ ac.sz][[A, B]]}

复杂度 O(max(A, B) * len* n * 8 * CHAR_SIZE) == 4.16e6

#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int CHAR_SIZE = 26;
const int MAX_SIZE = 1e3 + 8;
const int MOD = 1000003;

inline int mp(char ch){
    return ch - 'a';
}

struct AC_Machine{
    int ch[MAX_SIZE][CHAR_SIZE], danger[MAX_SIZE], fail[MAX_SIZE];
    int sz;

    void init(){
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        memset(danger, 0, sizeof danger);
    }

    void _insert(char *s){
        int n = strlen(s);
        int u = 0, c;
        for(int i = 0; i < n; i++){
            c = mp(s[i]);
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof ch[sz]);
                danger[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        danger[u] = 1;
    }

    void _build(){
        queue Q;
        fail[0] = 0;
        for(int c = 0, u; c < CHAR_SIZE; c++){
            u = ch[0][c];
            if(u){Q.push(u); fail[u] = 0;}
        }
        int r;
        while(!Q.empty()){
            r = Q.front();
            Q.pop();
            danger[r] |= danger[fail[r]];
            for(int c = 0, u; c < CHAR_SIZE; c++){ u = ch[r][c]; if(!u){ch[r][c] = ch[fail[r]][c]; continue; } fail[u] = ch[fail[r]][c]; Q.push(u); } } } }ac; char s[22]; inline void mod(int &x){ x -= x / MOD * MOD; } int dp[MAX_SIZE][22][8]; int main() { #ifdef LOCAL freopen("e.txt", "r", stdin); //freopen("e.out", "w", stdout); int T = 1; while(T--){ #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); int n, m, p; // n - > A, m -> B
    scanf("%d%d%d", &n, &m, &p);

    ac.init();
    while(p--){
        scanf("%s", s);
        ac._insert(s);
    }

    int i, j, k, w;
    memset(dp, 0, sizeof dp);
    ac._build();
    dp[0][0][0] = 1;

    for(i = 1; i <= m; i++){
        for(j = 0; j < ac.sz; j++){
            for(w = 0; w < 8; w++){
                if(dp[j][i-1][w] == 0) continue;
                for(k = 0; k < CHAR_SIZE; k++){
                    if(!ac.danger[ac.ch[j][k]]){
                        mod( dp[ac.ch[j][k]][i][w | 1] += dp[j][i-1][w] );
                        mod( dp[ac.ch[j][k]][i][w | 2] += dp[j][i-1][w] );
                        if(k == 'o' - 'a' || k == 'i' - 'a' || k == 'e' - 'a' || k == 's' - 'a' || k == 't' - 'a'){
                            mod( dp[ac.ch[j][k]][i][w | 4] += dp[j][i-1][w] ); // 0 1 3 5 7
                        }
                    }
                }
                mod( dp[0][i][w | 4] += dp[j][i-1][w] ); // 9
                for(k = 1; k < 10; k++){// 2 4 6 8
                    if(!(k&1)) mod( dp[0][i][w | 4] += dp[j][i-1][w] );
                }
            }
        }
    }
    int ans = 0;
    for(j = n; j <= m; j++){
        for(i = 0; i < ac.sz; i++){
            mod( ans += dp[i][j][8-1]);
        }
    }

    printf("%dn", ans);

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Gym – 101174E Passwords AC自动机+额外的限制条件+状态压缩dp

Problem E Passwords AC自动机+额外的限制条件+状态压缩dp

Source

My Solution

相关推荐

HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树

URAL – 1158 Censored! AC自动机+dp

HDU 6208 The Dominator of Strings 后缀自动机

Gym – 101164C Castle KMP的拓展、next数组+dp、好题

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类