HDOJ3231醉


反正一开始就是瞎几把看题,然后题意理解了,什么飞机?只能去看题解了。

呵呵,可惜,题解看了三个小时,还是一知半解,先写了。

- -菜鸡超级详细题解,强行掰弯一波,等下再问问别人吧。

OK,OK开始!!!

题意:在一个三维的空间里,有n个长方体,棱都与坐标轴平行。

然后给你一堆关系,让你去构建一个集合能否满足这些长方体的关系。

1、在三个维度上都相交

2、其中一个长方体上的所有点(8个点)的某一维(x/y/z)的坐标完全小于另一个长方体的任意一点。【其实就是不会相交了】


思路:长方体有六个面,关系在于面是不是在另一个长方体里面,然后把面看成点,根据关系来进行建图。

然后就是建图啊,要求的不就是x,y,z的范围么?

那么就是算出点的值就好了啊,然后就是建图,先初始化,看成两个点,1--n+1,2--n+2。。。

然后就是对题目的约束条件处理相交的时候:输入u点,v点,那么u<v+nn的,v<u+nn的;

然后就是在各自的维数上搞拓扑排序就可以了,大大缩短时间,点的权值就被前面的那个点的权值+1

【案例瞎几把是没看懂- -】

最终摸索了一个下午,看题解啊,自行理解思路啊。

= =blog.csdn.net/dgq8211/article/details/8038993

这题目的难点和好的地方就是:三维,然后坐标的范围用点的值去考虑(想想也是...)但是现在还是很晕,

长方体的表示,和点的表示,最终输出的长方体的x,y,z的范围;


代码:

http://paste.ubuntu.net/16060928/



原文地址:https://www.cnblogs.com/keyboarder-zsq/p/5934561.html