2014
11-30

# To Be an Dream Architect

The “dream architect” is the key role in a team of “dream extractors” who enter other’s dreams to steal secrets. A dream architect is responsible for crafting the virtual world that the team and the target will dream into. To avoid the target noticing the world is artificial, a dream architect must have powerful 3D imagination.

Cobb uses a simple 3D imagination game to test whether a candidate has the potential to be an dream architect. He lets the candidate imagine a cube consisting of n×n×n blocks in a 3D coordinate system as Figure 1. The block at bottom left front corner is marked (1, 1, 1) and the diagonally opposite block is marked (n, n, n). Then he tells the candidate that the blocks on a certain line are eliminated. The line is always parallel to an axis. After m such block eliminations, the candidate is asked to tell how many blocks are eliminated. Note that one block can only be eliminated once even if it is on multiple lines.

Here is a sample graph according to the first test case in the sample input:

The first line is the number of test cases.
In each test case, the first line contains two integers n and m( 1 <= n <= 1000, 0 <= m <= 1000).，meaning that the cube is n x n x n and there are m eliminations.

Each of the following m lines represents an elimination in the following format:
axis_1=a, axis_2=b
where axis_i (i=1, 2) is ‘X’ or ‘Y’, or ‘Z’ and axis_1 is not equal to axis_2. a and b are 32-bit signed integers.

The first line is the number of test cases.
In each test case, the first line contains two integers n and m( 1 <= n <= 1000, 0 <= m <= 1000).，meaning that the cube is n x n x n and there are m eliminations.

Each of the following m lines represents an elimination in the following format:
axis_1=a, axis_2=b
where axis_i (i=1, 2) is ‘X’ or ‘Y’, or ‘Z’ and axis_1 is not equal to axis_2. a and b are 32-bit signed integers.

2
3 2
Y=1,Z=3
X=3,Y=1
10 2
X=3,Y=3
Y=3,Z=3

5
19

#include <cstdio>
#include <string.h>
using namespace std;
const int maxn = 1111;
int n, m;
bool h[maxn];
char t1, t2; int v1, v2;
int d[maxn][4], type[maxn];
int com;
int ans;
int main() {
//freopen("c.in", "r", stdin);
int T; scanf("%d", &T);
while (T--) {
ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) h[j] = 1;
scanf("%*c");
scanf("%c=%d", &t1, &v1);
//putchar(t1);
scanf("%*c%c=%d", &t2, &v2);
//putchar(t2);
//puts("");
d[i][t1-'X'+1] = v1;
d[i][t2-'X'+1] = v2;
type[i] = 6-(t1-'X'+1)-(t2-'X'+1);
d[i][type[i]] = 0;
for (int j = 1; j < i; j++){
if (type[i]==type[j]){
if (d[i][1]==d[j][1]&&d[i][2]==d[j][2]&&d[i][3]==d[j][3]) {
memset(h,0,sizeof(h)); break;
}
} else {
com = 6-type[i]-type[j];
if (d[i][com]==d[j][com]) {
h[d[j][type[i]]]=0;
}
}
}
for (int j = 1; j <= n; j++) ans += h[j];
}
printf("%d\n", ans);
}
return 0;
}

1. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮