题解

1 条题解

  • 0
    @ 2020-08-04 20:47:23
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    # define ull unsigned long long
    const int N = 80 ;
    const int M = 3005 ;
    const ull Base = 233 ;
    const int INF = 1e8 ;
    using namespace std ;
    inline int read() {
        char c = getchar() ; int x = 0 , w = 1 ;
        while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
        while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
        return x*w ;
    }
    
    char s[N][N] ;
    int n , m , S , T ;
    int ans , cnt , num = 1 ;
    int dirh[N] , dirl[N] , hea[M] ;
    int hnum[N] , lnum[N] , d[M] ;
    int hw[2][N][N] , lw[2][N][N] , isbig[M] ;
    ull pw[N] , hsh1[N] , hsh2[N] ;
    map < ull , int > p , hap ;
    
    struct E {
        int nxt , to , dis ;
    } edge[M * 20] ; 
    inline void Insert_edge(int from , int to , int dis) {
        edge[++num].nxt = hea[from] ; edge[num].to = to ;
        edge[num].dis = dis ; hea[from] = num ;
    }
    inline void add_edge(int u , int v , int w) {
        Insert_edge(u , v , w) ;
        Insert_edge(v , u , 0) ;
    }
    inline void Clear() {
        ans = 0 ; cnt = 0 ; num = 1 ;
        memset(isbig , false , sizeof(isbig)) ;
        memset(hea , 0 , sizeof(hea)) ;
        memset(hnum , 0 , sizeof(hnum)) ;
        memset(lnum , 0 , sizeof(lnum)) ;
        p.clear() ; hap.clear() ;
    }
    
    inline bool Bfs() {
        queue < int > q ; q.push(S) ;
        memset(d , 0 , sizeof(d)) ; d[S] = 1 ;
        while(!q.empty()) {
            int u = q.front() ; q.pop() ;
            for(int i = hea[u] ; i ; i = edge[i].nxt) {
                int v = edge[i].to ;
                if(!d[v] && edge[i].dis > 0) {
                    d[v] = d[u] + 1 ;
                    q.push(v) ;
                }
            }
        }
        return d[T] ;
    }
    int Dfs(int u , int dis) {
        if(u == T || !dis) return dis ; 
        int Sum = 0 ;
        for(int i = hea[u] ; i ; i = edge[i].nxt) {
            int v = edge[i].to ;
            if(d[v] == d[u] + 1 && edge[i].dis > 0) {
                int diss = Dfs(v , min(dis , edge[i].dis)) ;
                if(diss > 0) {
                    edge[i].dis -= diss ; edge[i ^ 1].dis += diss ;
                    dis -= diss ; Sum += diss ; if(!dis) break ;
                }
            }
        }
        if(!Sum) d[u] = -1 ; 
        return Sum ;
    }
    inline void dinic() {
        while(Bfs()) 
            ans += Dfs(S , INF) ;
    }
    int main() {
        int Case = read() ;
        pw[0] = 1 ; for(int i = 1 ; i <= 75 ; i ++) pw[i] = pw[i - 1] * Base ;
        while(Case --) {
            Clear() ;
            n = read() ; m = read() ;
            for(int i = 1 ; i <= n ; i ++) dirh[i] = read() ;
            for(int i = 1 ; i <= m ; i ++) dirl[i] = read() ;
            for(int i = 1 ; i <= n ; i ++) {
                scanf("%s",s[i] + 1) ;
                for(int j = 1 ; j <= m ; j ++)
                    hsh1[j] = hsh1[j - 1] * Base + s[i][j] ;
                for(int j = m ; j >= 1 ; j --)
                    hsh2[j] = hsh2[j + 1] * Base + s[i][j] ;
                int lst = 1 ; ull tp1 , tp2 ;
                for(int j = 1 , l , r  ; j <= m ; j ++) {
                    if(s[i][j] == '_' || j == m) {
                        l = lst , r = j - 1 ; lst = j + 1 ;
                        if(s[i][j] != '_') ++ r ; if(l > r) continue ;
                        tp1 = hsh1[r] - hsh1[l - 1] * pw[r - l + 1] ;
                        tp2 = hsh2[l] - hsh2[r + 1] * pw[r - l + 1] ;
                        if(tp1 == tp2) {
                            if(hap[tp1]) continue ; 
                            ++ ans ; hap[tp1] = 1 ; continue ;
                        }
                        if(!p[tp1]) {
                            int vit1 = 1 ;
                            for(int k = 1 ; k <= r - l + 1 ; k ++) {
                                if(s[i][l + k - 1] > s[i][r - k + 1]) break ;
                                else if(s[i][l + k - 1] < s[i][r - k + 1]) {
                                    vit1 = -1 ;
                                    break ;
                                }
                            }
                            p[tp1] = ++ cnt ; isbig[cnt] = vit1 ;
                            p[tp2] = ++ cnt ; isbig[cnt] = - vit1 ;
                        }
                        hw[0][i][++hnum[i]] = p[tp1] ; hw[1][i][hnum[i]] = p[tp2] ;
                    }
                }
            }
            for(int j = 1 ; j <= m ; j ++) {
                for(int i = 1 ; i <= n ; i ++)
                    hsh1[i] = hsh1[i - 1] * Base + s[i][j] ;
                for(int i = n ; i >= 1 ; i --)
                    hsh2[i] = hsh2[i + 1] * Base + s[i][j] ;
                int lst = 1 ; ull tp1 , tp2 ;
                for(int i = 1 , l , r ; i <= n ; i ++) {
                    if(s[i][j] == '_' || i == n) {
                        l = lst , r = i - 1 ; lst = i + 1 ;
                        if(s[i][j] != '_') ++ r ; if(l > r) continue ;
                        tp1 = hsh1[r] - hsh1[l - 1] * pw[r - l + 1] ;
                        tp2 = hsh2[l] - hsh2[r + 1] * pw[r - l + 1] ;
                        if(tp1 == tp2) {
                            if(hap[tp1]) continue ;
                            ++ ans ; hap[tp1] = 1 ; continue ;
                        }
                        if(!p[tp1]) {
                            int vit1 = 1 ;
                            for(int k = 1 ; k <= r - l + 1 ; k ++) {
                                if(s[l + k - 1][j] > s[r - k + 1][j]) break ;
                                else if(s[l + k - 1][j] < s[r - k + 1][j]) {
                                    vit1 = -1 ;
                                    break ;
                                }
                            }
                            p[tp1] = ++ cnt ; isbig[cnt] = vit1 ;
                            p[tp2] = ++ cnt ; isbig[cnt] = -vit1 ;
                        }
                        lw[0][j][++lnum[j]] = p[tp1] ; lw[1][j][lnum[j]] = p[tp2] ;
                    }
                }
            }
            S = 0 , T = cnt + n + m + 1 ;
            for(int i = 1 , x , y ; i <= cnt ; i += 2) {
                x = i ; y = i + 1 ;
                if(isbig[x] == 1) swap(x , y) ;
                add_edge(x , y , 2) ;
            }
            for(int i = 1 ; i <= n ; i ++) {
                if(!hnum[i]) continue ;
                if((dirh[i] == 1 && isbig[hw[0][i][1]] < 0) || (dirh[i] == -1 && isbig[hw[1][i][1]] < 0)) {
                    add_edge(S , cnt + i , INF) ;
                    for(int j = 1 ; j <= hnum[i] ; j ++) {
                        if(dirh[i] == 1) add_edge(cnt + i , hw[0][i][j] , INF) ;
                        else add_edge(cnt + i , hw[1][i][j] , INF) ;
                    }
                }
                else if((dirh[i] == 1 && isbig[hw[0][i][1]] > 0) || (dirh[i] == -1 && isbig[hw[1][i][1]] > 0)) {
                    add_edge(cnt + i , T , INF) ;
                    for(int j = 1 ; j <= hnum[i] ; j ++) {
                        if(dirh[i] == 1) add_edge(hw[0][i][j] , cnt + i , INF) ;
                        else add_edge(hw[1][i][j] , cnt + i , INF) ;
                    }
                }
                else {
                    for(int j = 1 , x , y ; j <= hnum[i] ; j ++) {
                        x = hw[0][i][j] , y = hw[1][i][j] ;
                        if(isbig[x] > 0) swap(x , y) ;
                        add_edge(cnt + i , x , INF) ;
                        add_edge(y , cnt + i , INF) ;
                    }
                }
            }
            for(int i = 1 ; i <= m ; i ++) {
                if(!lnum[i]) continue ;
                if((dirl[i] == 1 && isbig[lw[0][i][1]] <= 0) || (dirl[i] == -1 && isbig[lw[1][i][1]] <= 0)) {
                    add_edge(S , cnt + n + i , INF) ;
                    for(int j = 1 ; j <= lnum[i] ; j ++) {
                        if(dirl[i] == 1) add_edge(cnt + n + i , lw[0][i][j] , INF) ;
                        else add_edge(cnt + n + i , lw[1][i][j] , INF) ;
                    }
                }
                else if((dirl[i] == 1 && isbig[lw[0][i][1]] >= 0) || (dirl[i] == -1 && isbig[lw[1][i][1]] >= 0)) {
                    add_edge(cnt + n + i , T , INF) ;
                    for(int j = 1 ; j <= lnum[i] ; j ++) {
                        if(dirl[i] == 1) add_edge(lw[0][i][j] , cnt + n + i , INF) ;
                        else add_edge(lw[1][i][j] , cnt + n + i , INF) ;
                    }
                }
                else {
                    for(int j = 1 , x , y ; j <= lnum[i] ; j ++) {
                        x = lw[0][i][j] , y = lw[1][i][j] ;
                        if(isbig[x] > 0) swap(x , y) ;
                        add_edge(cnt + n + i , x , INF) ;
                        add_edge(y , cnt + n + i , INF) ;
                    }
                }
            }
            
            dinic() ;
            printf("%d\n",ans) ;
        }
        return 0 ;
    }
    
  • 1

信息

ID
1994
难度
5
分类
(无)
标签
递交数
34
已通过
15
通过率
44%
被复制
1
上传者