2010-1141

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

'''题目大意'''[[BR]]
连通性dp经典模型稍微变形，把原来的正方形格子变成正六边形。
基本和HDU1693题目一样，每个可达格子需要且仅能用一个长度>=3的圈圈住。所有圈不能相交。
问不同的方案数。

'''解法'''[[BR]]
参考陈丹琦的国家队论文《基于连通性的状态压缩动态规划》和HDU1693的解题报告。
由于题目没有要求只能有一个圈，所以单位轮廓线的状态只需要0,1两种，表示该轮廓线是否被某个圈经过过。
因此，每个正六边形的六个边缘有且仅有两个状态为1。
与HDU1693不同的是，原来的是正方形的格子，现在是正六边形，所以轮廓线的长度与奇偶性相关，而且有点怪。
中间的状态转移，和对轮廓线的处理都需要人肉一下，具体参见程序和自己yy一下吧。。。

'''代码'''
{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long LL;

vector<LL> V[2];
LL f[2][1 << 17];
int used[1 << 17]; 
int step, t1, t2;
bool map[9][8];

void print(int mask) {
    for (int i = 0; i < 17; i++) {
        printf("%d", mask & 1);
        mask >>= 1;
    }   
}

inline void update(int now, int mask) {
    if (used[now] == step) f[t2][now] += f[t1][mask];
    else {
        f[t2][now] = f[t1][mask];
        used[now] = step;
        V[t2].push_back(now);   
    }    
}

int main() {

    int n, m;
    char st[10];

    while (scanf("%d %d", &n, &m) != EOF) {
        memset(map, true, sizeof(map));
        for (int i = 0; i < m; i++) {
            scanf("%s", st);
            map[st[0] - 'A'][st[1] - 'A'] = false;   
        }        
        memset(used, 255, sizeof(used));
        f[0][0] = 1;
        V[0].clear(), V[0].push_back(0);
        t1 = 0, step = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 8; j++) {
                step++;
                t2 = 1 - t1;
                V[t2].clear();
                for (int k = 0; k < (int)V[t1].size(); k++) {
                    int mask = V[t1][k];

                    // 0 -> 0, 1, 2
                    if (j == 0) {
                        int now = ((mask >> 1) << 1) << 2;  // (0)1...14 -> (000)3...16
                        if (!map[i][j]) {
                            if (mask & 1) continue;
                            update(mask << 2, mask);  
                        }
                        else {
                            if (mask & 1) {
                                update(now | 1, mask);
                                update(now | 2, mask);
                                update(now | 4, mask);
                            }
                            else {
                                update(now | 3, mask);
                                update(now | 5, mask);
                                update(now | 6, mask);
                            }                            
                        }
                        continue;    
                    }

                    // 14, 15, 16 -> 14
                    if (j == 7) {
                        int now = mask & ((1 << 14) - 1);  // 0...16 -> 0...13
                        int left = mask >> 14;
                        if (!map[i][j]) {
                            if (left) continue;
                            update(now, mask);  
                        }
                        else {
                            if (left == 3 || left == 5 || left == 6) {
                                update(now, mask);   
                            } else if (left == 1 || left == 2 || left == 4) {
                                update(now | (1 << 14), mask);   
                            }
                        }
                        continue;   
                    }

                    if (j % 2 == 0) {
                        // 2 * j - 1, 2 * j -> 2 * j - 1, 2 * j, 2 * j + 1, 2 * j + 2
                        int now = mask & ((1 << (2 * j - 1)) - 1);
                        now |= (mask >> (2 * j + 1)) << (2 * j + 3);
                        int left = (mask >> (2 * j - 1)) & 3;
                        if (!map[i][j]) {
                            if (left) continue;
                            update(now, mask);   
                        }                        
                        else {
                            if (left == 3) {
                                update(now, mask);   
                            }   
                            else if (left == 1 || left == 2) {
                                update(now | (1 << (2 * j - 1)), mask);
                                update(now | (2 << (2 * j - 1)), mask);
                                update(now | (4 << (2 * j - 1)), mask);
                                update(now | (8 << (2 * j - 1)), mask);   
                            }
                            else if (left == 0){
                                update(now | (3  << (2 * j - 1)), mask);
                                update(now | (5  << (2 * j - 1)), mask);
                                update(now | (9  << (2 * j - 1)), mask);   
                                update(now | (6  << (2 * j - 1)), mask);
                                update(now | (10 << (2 * j - 1)), mask);
                                update(now | (12 << (2 * j - 1)), mask);      
                            }                      
                        }
                    }
                    else {
                        // 2 * j, 2 * j + 1, 2 * j + 2, 2 * j + 3 -> 2 * j, 2 * j + 1               
                        int now = mask & ((1 << (2 * j)) - 1);
                        now |= (mask >> (2 * j + 4)) << (2 * j + 2);     
                        int left = (mask >> (2 * j)) & ((1 << 4) - 1);
                        if (!map[i][j]) {
                            if (left) continue;   
                            update(now, mask);
                        }
                        else {
                            if (left == 0) {
                                update(now | (3 << (2 * j)), mask);   
                            } else if (left == 1 || left == 2 || left == 4 || left == 8) {
                                update(now | (1 << (2 * j)), mask);
                                update(now | (2 << (2 * j)), mask);   
                            } else if (left == 3 || left == 5 || left == 9 || left == 6 || left == 10 || left == 12) {
                                update(now, mask);   
                            }
                        }
                    }
                }
                t1 = t2;  
            }
        }
        if (used[0] == step) {
            printf("%lld\n",f[t1][0]);
        }
        else {
            puts("0");
        }
    }
    return 0;    
}
}}}

题目大意

连通性dp经典模型稍微变形，把原来的正方形格子变成正六边形。

基本和HDU1693题目一样，每个可达格子需要且仅能用一个长度>=3的圈圈住。所有圈不能相交。

问不同的方案数。

解法

参考陈丹琦的国家队论文《基于连通性的状态压缩动态规划》和HDU1693的解题报告。

由于题目没有要求只能有一个圈，所以单位轮廓线的状态只需要0,1两种，表示该轮廓线是否被某个圈经过过。

因此，每个正六边形的六个边缘有且仅有两个状态为1。

与HDU1693不同的是，原来的是正方形的格子，现在是正六边形，所以轮廓线的长度与奇偶性相关，而且有点怪。

中间的状态转移，和对轮廓线的处理都需要人肉一下，具体参见程序和自己yy一下吧。。。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
vector<LL> V[2];
LL f[2][1 << 17];
int used[1 << 17]; 
int step, t1, t2;
bool map[9][8];
void print(int mask) {
    for (int i = 0; i < 17; i++) {
        printf("%d", mask & 1);
        mask >>= 1;
    }   
}
inline void update(int now, int mask) {
    if (used[now] == step) f[t2][now] += f[t1][mask];
    else {
        f[t2][now] = f[t1][mask];
        used[now] = step;
        V[t2].push_back(now);   
    }    
}
int main() {
    int n, m;
    char st[10];
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(map, true, sizeof(map));
        for (int i = 0; i < m; i++) {
            scanf("%s", st);
            map[st[0] - 'A'][st[1] - 'A'] = false;   
        }        
        memset(used, 255, sizeof(used));
        f[0][0] = 1;
        V[0].clear(), V[0].push_back(0);
        t1 = 0, step = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 8; j++) {
                step++;
                t2 = 1 - t1;
                V[t2].clear();
                for (int k = 0; k < (int)V[t1].size(); k++) {
                    int mask = V[t1][k];
                    // 0 -> 0, 1, 2
                    if (j == 0) {
                        int now = ((mask >> 1) << 1) << 2;  // (0)1...14 -> (000)3...16
                        if (!map[i][j]) {
                            if (mask & 1) continue;
                            update(mask << 2, mask);  
                        }
                        else {
                            if (mask & 1) {
                                update(now | 1, mask);
                                update(now | 2, mask);
                                update(now | 4, mask);
                            }
                            else {
                                update(now | 3, mask);
                                update(now | 5, mask);
                                update(now | 6, mask);
                            }                            
                        }
                        continue;    
                    }
                    // 14, 15, 16 -> 14
                    if (j == 7) {
                        int now = mask & ((1 << 14) - 1);  // 0...16 -> 0...13
                        int left = mask >> 14;
                        if (!map[i][j]) {
                            if (left) continue;
                            update(now, mask);  
                        }
                        else {
                            if (left == 3 || left == 5 || left == 6) {
                                update(now, mask);   
                            } else if (left == 1 || left == 2 || left == 4) {
                                update(now | (1 << 14), mask);   
                            }
                        }
                        continue;   
                    }
                    if (j % 2 == 0) {
                        // 2 * j - 1, 2 * j -> 2 * j - 1, 2 * j, 2 * j + 1, 2 * j + 2
                        int now = mask & ((1 << (2 * j - 1)) - 1);
                        now |= (mask >> (2 * j + 1)) << (2 * j + 3);
                        int left = (mask >> (2 * j - 1)) & 3;
                        if (!map[i][j]) {
                            if (left) continue;
                            update(now, mask);   
                        }                        
                        else {
                            if (left == 3) {
                                update(now, mask);   
                            }   
                            else if (left == 1 || left == 2) {
                                update(now | (1 << (2 * j - 1)), mask);
                                update(now | (2 << (2 * j - 1)), mask);
                                update(now | (4 << (2 * j - 1)), mask);
                                update(now | (8 << (2 * j - 1)), mask);   
                            }
                            else if (left == 0){
                                update(now | (3  << (2 * j - 1)), mask);
                                update(now | (5  << (2 * j - 1)), mask);
                                update(now | (9  << (2 * j - 1)), mask);   
                                update(now | (6  << (2 * j - 1)), mask);
                                update(now | (10 << (2 * j - 1)), mask);
                                update(now | (12 << (2 * j - 1)), mask);      
                            }                      
                        }
                    }
                    else {
                        // 2 * j, 2 * j + 1, 2 * j + 2, 2 * j + 3 -> 2 * j, 2 * j + 1               
                        int now = mask & ((1 << (2 * j)) - 1);
                        now |= (mask >> (2 * j + 4)) << (2 * j + 2);     
                        int left = (mask >> (2 * j)) & ((1 << 4) - 1);
                        if (!map[i][j]) {
                            if (left) continue;   
                            update(now, mask);
                        }
                        else {
                            if (left == 0) {
                                update(now | (3 << (2 * j)), mask);   
                            } else if (left == 1 || left == 2 || left == 4 || left == 8) {
                                update(now | (1 << (2 * j)), mask);
                                update(now | (2 << (2 * j)), mask);   
                            } else if (left == 3 || left == 5 || left == 9 || left == 6 || left == 10 || left == 12) {
                                update(now, mask);   
                            }
                        }
                    }
                }
                t1 = t2;  
            }
        }
        if (used[0] == step) {
            printf("%lld\n",f[t1][0]);
        }
        else {
            puts("0");
        }
    }
    return 0;    
}