2014
03-09

# Box Relations

There are n boxes C1, C2, …, Cn in 3D space. The edges of the boxes are parallel to the x, y or z-axis. We provide some relations of the boxes, and your task is to construct a set of boxes satisfying all these relations.

There are four kinds of relations (1 <= i,j <= n, i is different from j):

• I i j: The intersection volume of Ci and Cj is positive.
• X i j: The intersection volume is zero, and any point inside Ci has smaller x-coordinate than any point inside Cj.
• Y i j: The intersection volume is zero, and any point inside Ci has smaller y-coordinate than any point inside Cj.
• Z i j: The intersection volume is zero, and any point inside Ci has smaller z-coordinate than any point inside Cj.

.

There will be at most 30 test cases. Each case begins with a line containing two integers n (1 <= n <= 1,000) and R (0 <= R <= 100,000), the number of boxes and the number of relations. Each of the following R lines describes a relation, written in the format above. The last test case is followed by n=R=0, which should not be processed.

There will be at most 30 test cases. Each case begins with a line containing two integers n (1 <= n <= 1,000) and R (0 <= R <= 100,000), the number of boxes and the number of relations. Each of the following R lines describes a relation, written in the format above. The last test case is followed by n=R=0, which should not be processed.

3 2
I 1 2
X 2 3
3 3
Z 1 2
Z 2 3
Z 3 1
1 0
0 0

Case 1: POSSIBLE
0 0 0 2 2 2
1 1 1 3 3 3
8 8 8 9 9 9

Case 2: IMPOSSIBLE

Case 3: POSSIBLE
0 0 0 1 1 1

1、某两个长方体相交。

2、某个长方体的所有点的某一维的坐标完全小于另一个长方体的任意一点。

#include <queue>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 2005

struct T
{
int v,next;
}E[3][N*100];

struct TT
{
}V[3][N];

int top[3],ans,n,m;

{
E[k][top[k]].v = v;
++V[k][v].rd;
}

bool Top_Sort(int k)
{
queue<int> Q;
for(int i=1;i<=n;i++)
if(V[k][i].rd == 0)
Q.push(i);
int cnt = 0;
while(!Q.empty())
{
++cnt;
int p = Q.front();
{
int q = E[k][i].v;
--V[k][q].rd;
if(V[k][q].rd == 0)
{
Q.push(q);
V[k][q].dep = V[k][p].dep + 1;
}
}
Q.pop();
}
return cnt == n;
}
int main()
{
int u,v,nn,ncase=0;
char cmd;
while(~scanf("%d%d%*c",&nn,&m),nn)
{
memset(V,0,sizeof(V));
top[0] = top[1] = top[2] = 1;
n = 2*nn;
for(int k=0;k<3;k++)
for(int i=1;i<=nn;i++)
while(m--)
{
scanf("%c%d%d%*c",&cmd,&u,&v);
if(cmd == 'I')
{
for(int k=0;k<3;k++)
{
}
}
else
}
printf("Case %d: ",++ncase);
if(!Top_Sort(0) || !Top_Sort(1) || !Top_Sort(2))
puts("IMPOSSIBLE\n");
else
{
puts("POSSIBLE");
for(int i=1;i<=nn;i++)
printf("%d %d %d %d %d %d\n",V[0][i].dep,V[1][i].dep,V[2][i].dep,V[0][i+nn].dep,V[1][i+nn].dep,V[2][i+nn].dep);
puts("");
}
}
return 0;
}

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

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

3. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

4. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

5. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.