poj1022:Packing Unit 4D Cubes四维魔方的题意和题解

囧，题意看起来很复杂，故几乎没什么人提交，其实只要看懂了题目的意思再简单不过了，，，这不，因为英语不好花了很久才看懂题意，稍微解释一下吧：
定义一个四维的魔方，每个四维的魔方有八个面（类比3维的魔方有六个面），每个面是一个3维的东西（类比3维的魔方的每个面是2维的平面）。
然后要把n个四维的魔方包装起来，因为是四维的，所以有四根坐标轴，每个魔方给出9个数据，第一个是此魔方的标识，然后1，2个表示在沿着第一根轴的前面和后面的用胶水
粘贴起来的魔方的编号，没有便为0。然后要你计算这n个四维魔方组装成的EER的“体积”（体积是相对与四维而言的）。理解了题意就简单了，直接由3维的外推到4维，3维里怎
么做在四维里就怎么做。如：体积等于每个坐标轴的距离乘起来。反正按3维的思考方法来就是了。
然后有两个判断：1是如果x在y上面那y必在x下面，如不成立则不存在。
2是最后只能组装城一个产品，不是多个，dfs求连通分量即可
AC代码如下：（第一次以为魔方的标识符在1到n之间，其实不是，搞得re了几次）

[cpp]
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define get(x) (((x-1)&((1 << 31) - 2)+((x-1)&1)^1)+1)
# define DEBUG

int s[111][11];
int use[111];
int check[111];
int re[111];

int go(int x, int n) {
    for (int i = 1; i <= n; ++ i){
        if(re[i] == x) return i;
    }
}

int check1(int n) {
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= 8; ++ j) {
            if (s[i][j] && s[go(s[i][j], n)][get(j)] != re[i]) return 1;
        }
    }
    return 0;
}

int dfs(int x, int n) {
    if(check[x]) return 0;
    check[x] = 1;
    for (int i = 1; i <= 8; ++ i) {
        if(s[x][i]) {
            int t = go(s[x][i], n);
            use[t] = 1;
            dfs(t,n);
        }
    }
    return 0;
}

int check2(int n, int x) {
    dfs(x,n);
    for (int i = 1; i <= n; ++ i) {
        if (!use[i]) return 1;
    }
    return 0;
}

int getAns(int n) {
    int x[5];
    memset(x, 0, sizeof(x));
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= 8; ++ j) {
            if(s[i][j]) {
                ++ x[(j + 1) >> 1];
            }
        }
    }
    int su = 1;
    for (int i = 1; i <= 4; ++ i) {
        su *= (x[i] >> 1) + 1;
    }
    printf ("%d\n", su);
    return 0;
}

int main () {
    int ts;
    for (scanf("%d", &ts); ts; -- ts) {
        int n;
        scanf("%d", &n);
        memset(s, 0, sizeof(s));
        memset(use, 0, sizeof(use));
        memset(check, 0, sizeof(check));
        memset(re, 0, sizeof(re));
        int t;
        for (int i = 1; i <= n; ++ i) {
            scanf("%d", &t);
            re[i] = t;
            s[i][0] = t;
            for (int j = 1; j <= 8; ++ j) {
                scanf("%d", &s[i][j]);
            }
        }   www.zzzyk.com
        //printf ("%d %d", check1(n), check2(n, t));
        if(check1(n) || check2(n, 1)) {
            printf ("Inconsistent\n");
        }
        else {
            getAns(n);
        }
    }

    return 0;
}

补充：软件开发 , C++ ,