[FZU 2199] Patchmania I 插头DP

传送门·Teleport!

题目大意

题面比较长我就不写了概要了… 懒癌发作

锌酸报告

测试数据大礼包:

Input:
11
2 2
X#
.O
1 2
XO
3 3
X##
###
##O
3 4
X###
####
..O.
3 3
X##
..#
..O
8 8
X..#####
...#####
...#####
########
########
########
#######.
#######O
6 6
X...##
..####
######
######
#####.
#####O
6 6
X.....
......
####..
####..
##.#..
#####O
4 4
....
.X..
....
...O
7 7
...####
..O####
#######
#####..
#####..
#X#####
#######
3 4
.X..
###.
#O#.
Output:
Case #1: 2 1
Case #2: 1 1
Case #3: 8 2
Case #4: 8 1
Case #5: 4 1
Case #6: 56 85852
Case #7: 30 15
Case #8: -1
Case #9: 4 6
Case #10: 39 324
Case #11: 10 1

每一组都把我卡掉过
还没完。。
附带调试写的测试数据生成器:

#include<cstdio>
#include<ctime>
#include<cstdlib>
int random(int m) {return rand()%m;}
char g[10][10];
int main () {
    freopen("data.in", "w", stdout);
    srand(time(0));
    int N, M, cas;
    cas = random(1000);
    printf("%d\n", cas);
    for(int t = 1; t<=cas; t++) {
        N = random(7)+2, M = random(7)+2;
        printf("%d %d\n", N, M);
        memset(g, 0, sizeof g);
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=M; j++)
                g[i][j] = (random(100) > 70)?'#':'.';
        int sx = random(N)+1, sy = random(M)+1;
        int tx, ty;
        do {
            tx = random(N)+1, ty = random(M)+1;
        } while(sx == tx && sy == ty);
        g[sx][sy] = 'X';
        g[tx][ty] = 'O';
        for(int i = 1; i<=N; i++)
        printf("%s\n", g[i]+1);
    }
}

正经的题解:
首先这是插头DP(如果你不知道什么是插头DP建议先看个论文 基于连通性状态压缩的动态规划问题 )
然后这题利用了括号序列的思想,如果没做过括号序列类似的题可以看看我的 CITY这篇博文
首先如果我们抛开非萝卜的区域考虑并且枚举一下起点，那么这题就转化成

规定了起点终点的覆盖全图的单条路线方案数

插头肯定是个括号序列,但用普通的括号序列好像不能搞。。
然后想一想就会发现对于每行插头的状态,右括号和左括号数量差的绝对值不会大于1
那么状态一下变小了好多。
为了描述方便,定义没有匹配括号的插头为”独立插头”,那么独立插头只可能从枚举的起点或终点出发,那么每个插头序列中最多只可能有两个独立插头。
DP开始,我们略去比较简单的其他情况,重点考虑合并。因为要维护一条覆盖全图的路径,合并时如果是普通括号的合并,只要让他们不产生环就好了(具体做法可以看上文中附加的我的博文链接)然后如果和括号独立插头合并的话,只需要吧括号并入独立插头后找到括号的匹配括号,改成独立插头(相当于用一对括号的半环延长了独立插头的路径)就可以了。
当dp时碰到枚举的起点或终点时记得自动生成一个独立插头。
需要注意的是,独立插头和独立插头在没有dp到最后一个dp到的萝卜时时不能合并的,不然这就代表着路径的结束,我们维护的路径就不能再延长了。
其他具体实现细节比如用哈希表查询括号的匹配括号方法等等类似于上面给出的CITY题解方法。
贴代码(写完想骂人系列):

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <queue>

typedef long long LL;
using std :: pair;
using std :: min;
using std :: max;
using std :: queue;
using std :: make_pair;
const int MAXN = 8;
const int MOD = 1000000007;
const int bits[10] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18};
const int mask[10] = {
    0x00000,
    0x00003, 0x0000f, 0x0003f,
    0x000ff, 0x003ff, 0x00fff,
    0x03fff, 0x0ffff, 0x3ffff
};
int N, M, cas;
inline int getBit (int num, int i)
{return (num&mask[i]&(~mask[i-1]))>>bits[i-1];}
inline int setBit (int num, int i, int val)
{return (num^(getBit(num, i)<<bits[i-1]))|(val<<bits[i-1]);}
inline void debug  (int s) {for(int i = 1; i<=M+1; i++) printf("%d", getBit(s, i));}
template <int HASH, class T> struct HashMap {
    int hash[HASH]; T data[HASH];
    void clear () {memset(hash, 0xff, sizeof hash);}
    int locate (int code) {
        int p = code%HASH;
        while(hash[p] != -1) {
            if(hash[p] == code) return p;
            p ++; if(p >= HASH) p -= HASH;
        }
        return p;
    }
    T insert (int code, T val) {
        //if(M) {printf("insert:"); debug(code); printf("\n");}
        int p = locate(code);
        if(hash[p] == -1) hash[p] = code, data[p] = 0;
        data[p] += val;
        if(data[p] >= MOD) data[p] -= MOD;
        return data[p];
    }
    T * query (int code) {
        int p = locate(code);
        if(hash[p] == -1) return NULL;
        return &data[p];
    }
} ;

const int HASH    = 8971;
const int HASHSEQ = 997187;
HashMap<HASH,    int > mem[2], *dp, *src;
HashMap<HASHSEQ, char> lef, rig;
int lastX, lastY;

void dfs (int i, int cnt, int s, int dcnt) {
    if(i >= MAXN+1) {
        if(cnt) return ;
        for(int i = 1; i<=MAXN+1; i++)
        if(getBit(s, i) == 1) {
            int t = 1;
            for(int j = i+1; j<=MAXN+1; j++) {
                if(getBit(s, j) == 1) t++;
                else if(getBit(s, j) == 2) t--;
                if(t == 0) {
                    rig.insert((s<<4)+i, j);
                    break;
                }
            }
        } else if(getBit(s, i) == 2) {
            int t = 1;
            for(int j = i-1; j; j--) {
                if(getBit(s, j) == 2) t++;
                else if(getBit(s, j) == 1) t--;
                if(t == 0) {
                    lef.insert((s<<4)+i, j);
                    break;
                }
            }
        }
        return ;
    }
    dfs(i+1, cnt, s<<2, dcnt);
    dfs(i+1, cnt+1, (s<<2)+2, dcnt);
    if(cnt) dfs(i+1, cnt-1, (s<<2)+1, dcnt);
    if(dcnt < 2) dfs(i+1, cnt, (s<<2)+3, dcnt+1);
}

char input[MAXN+3][MAXN+3];
bool status[MAXN+3][MAXN+3];

int caltPath (pair<int, int> S, pair<int, int> T, int pvalue) {

    memset(status, 0, sizeof status);
    status[S.first][S.second] = true;
    status[T.first][T.second] = true;
    dp = &mem[0], src = &mem[1];
    dp->clear(), src->clear();
    src->insert(0, pvalue);

    for(int row = 1; row <= N; row ++) {
        for(int col = 1; col <= M; col ++) {
            dp->clear();
            for(int hp = 0; hp<HASH; hp++) {
                int s; if((s=src->hash[hp]) == -1) continue ;
                int lc = getBit(s, col), rc = getBit(s, col+1), val = src->data[hp];
                //printf("row:%d, col:%d, lcrc:%d%d, s:", row, col, lc, rc);
                //debug(s); printf(", val:%d\n", val);
                if(status[row][col]) { //出现新的独立插头
                    if(lc == 0 && rc == 0) {
                        if(row != N) dp->insert(setBit(s, col,   3), val);
                        if(col != M) dp->insert(setBit(s, col+1, 3), val);
                    } else if(rc == 0 || lc == 0) { //和独立插头合并
                        int tmp = rc + lc; char * r;
                        if(tmp == 3 && row == lastX && col == lastY)
                            dp->insert(setBit(setBit(s, col, 0), col+1, 0), val); //两个独立合并 只有最后一个点
                        else if(lc == 1 && (r=rig.query((s<<4)+col)) != NULL) // 和括号合并
                            dp->insert(setBit(setBit(s, col, 0), *r, 3), val);
                        else if(lc == 2 && (r=lef.query((s<<4)+col)) != NULL)
                            dp->insert(setBit(setBit(s, col, 0), *r, 3), val);
                        else if(rc == 1 && (r=rig.query((s<<4)+col+1)) != NULL)
                            dp->insert(setBit(setBit(s, col+1, 0), *r, 3), val);
                        else if(rc == 2 && (r=lef.query((s<<4)+col+1)) != NULL)
                            dp->insert(setBit(setBit(s, col+1, 0), *r, 3), val);
                    }
                    else continue ;
                } else if(input[row][col] == '.') {//障碍空转移
                    if(lc == 0 && rc == 0) dp->insert(s, val);
                } else if(lc == 0 && rc == 0 && row != N && col != M) //生成一对新括号
                    dp->insert(setBit(setBit(s, col, 1), col+1, 2), val);
                else if((lc != 0 && rc == 0) || (lc == 0 && rc != 0)) { //延伸一个插头
                    int tmp = lc + rc;
                    if(row != N) dp->insert(setBit(setBit(s, col, tmp), col+1, 0), val);
                    if(col != M) dp->insert(setBit(setBit(s, col, 0), col+1, tmp), val);
                } else /*if(lc != 0 && rc != 0)*/ { //讨论合并
                    char * r;
                    if(lc == 1 && rc == 1 && (r=rig.query((s<<4)+col+1)) != NULL)
                        dp->insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 1), val);
                    if(lc == 2 && rc == 2 && (r=lef.query((s<<4)+ col )) != NULL)
                        dp->insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 2), val);
                    if(lc == 1 && rc == 3 && (r=rig.query((s<<4)+ col )) != NULL)
                        dp->insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 3), val);
                    if(lc == 3 && rc == 1 && (r=rig.query((s<<4)+col+1)) != NULL)
                        dp->insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 3), val);
                    if(lc == 2 && rc == 3 && (r=lef.query((s<<4)+ col )) != NULL)
                        dp->insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 3), val);
                    if(lc == 3 && rc == 2 && (r=lef.query((s<<4)+col+1)) != NULL)
                        dp->insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 3), val);
                    if(lc == 3 && rc == 3 && row == lastX && col == lastY) //答案转移可以合并独立插头
                        dp->insert(setBit(setBit(s, col, 0), col+1, 0), val);
                    if(lc == 2 && rc == 1) dp->insert(setBit(setBit(s, col, 0), col+1, 0), val);
                }
            }
            std :: swap(src, dp);
        }
        dp->clear(); //否然换行
        for(int s = 0; s < HASH; s++) {
            if(src->hash[s] == -1 || getBit(src->hash[s], M+1) != 0) continue ; //非法转移
            dp->insert((src->hash[s]<<bits[1])&mask[M+1], src->data[s]);
        }
        std :: swap(src, dp);
    }
    int * ans = src->query(0);
    if(ans == NULL) return -1; //无合法转移
    return * ans;
}
const int mov[4][2]  ={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dist[MAXN+3][MAXN+3];
int plans[MAXN+3][MAXN+3];
queue<pair<int, int> > que;
void bfs (pair<int, int> s) {
    memset(dist, 0x3f, sizeof dist);
    memset(plans, 0, sizeof plans);
    dist[s.first][s.second] = 0;
    plans[s.first][s.second] = 1;
    que.push(s);
    while(!que.empty()) {
        pair<int, int> p = que.front();
        que.pop();
        int x = p.first, y = p.second;
        if(input[x][y] != '.') continue ;
        for(int i = 0; i<4; i++) {
            int nx = x+mov[i][0], ny = y+mov[i][1];
            if(nx<=0 || ny<=0 || nx>N || ny>M || dist[nx][ny] < dist[x][y]+1) continue ;
            plans[nx][ny] += plans[x][y];
            if(plans[nx][ny] >= MOD) plans[nx][ny] -= MOD;
            if(dist[nx][ny] != dist[x][y]+1)
                dist[nx][ny] = dist[x][y]+1, que.push(make_pair(nx, ny));
        }
    }
}

int main () {

    scanf("%d", &cas);
    lef.clear(), rig.clear();
    dfs(0, 0, 0, 0);
    int tc = 0;

    while(tc < cas && (~scanf("%d%d", &N, &M))) {
        memset(input, 0, sizeof input);
        pair<int, int> S, T;
        for(int i = 1; i<=N; i++)
            scanf("%s", input[i]+1);
        lastX = lastY = 0; int ccnt = 0;
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=M; j++) {
                if(input[i][j] == '#') ccnt ++;
                if(input[i][j] == 'X') S.first = i, S.second = j;
                if(input[i][j] == 'O') T.first = i, T.second = j;
                if(input[i][j] != '.' && input[i][j] != 'X') lastX = i, lastY = j;
            }
        input[S.first][S.second] = '.'; // 初始点为未种
        bfs(S);
        if(ccnt == 0) {
            if(plans[T.first][T.second])
                printf("Case #%d: %d %d\n", ++tc, dist[T.first][T.second], plans[T.first][T.second]);
            else printf("Case #%d: -1\n", ++tc);
            continue ;
        }
        int mindist = 0x3f3f3f3f;
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=M; j++)
                if(input[i][j] == '#') mindist = min(mindist, dist[i][j]);

        int ans = -1;
        while(true) {
            bool flag = false;
            int cnt = 0;
            for(int i = 1; i<=N; i++)
                for(int j = 1; j<=M; j++) {
                    if(input[i][j] != '#' || dist[i][j] != mindist) continue ;
                    //printf("dp:(%d, %d) -> (%d, %d)\n", i, j, T.first, T.second);
                    int app = caltPath(make_pair(i, j), T, plans[i][j]);
                    if(app != -1) flag = true, (cnt += app) %= MOD;
                }
            if(flag) {ans = cnt; break;}
            mindist ++;
            if(mindist > N*M) break;
        }
        printf("Case #%d: ", ++tc);
        if(ans == -1) puts("-1");
        else printf("%d %d\n", ccnt+mindist, ans);
    }
}

吐槽

我现在特别想把出题人拉过来啊一顿。