【活动】苍海高级程序员试题

上邪 · 发表于 2013-11-4 21:38:01

@admin @龙 @小二悲剧，网页卡了出那么多回帖，求删

灵符 · 发表于 2013-11-10 10:41:44

本来想直接全图flood一遍就是了……结果看到司马的绝对值小于一亿……OJ一秒运行忘了是一千万还是一亿来着，O（面积）都跪更别说搜的时候还要加个平方-_-

从数据规模来看给的提示应该是从n入手，那就每条进来的时候跑一遍，看能不能回到原点= =但是，效率又是极低

所以试着每条边进来的时候，在边的每个点做个标记，搜的时候跑一遍标记，没有与别的边重叠的点直接跳过，搜索的时候也从重叠部分开始搜

搜的时候记得加路障，即被确定的矩形四个顶点都不能再搜，否则你会看到你的答案会大好多（目测普通刀和一刀分两半两种情况下多出来的矩形数不太一样……没有具体分析反正会跪就对……）

应该就是这样吧……懒得写代码了……随便说说思路……至于搜索方法嘛= =深广本质都一样，这里是求数量不是求最优解看起来像DFS……具体的没去想……广搜在这道题讨不到什么便宜没必要大费周张去建队列（反正我有建有错……）

最后看看效率……应该不会太可怕……（目测是交点个数的四次方？）应该至少前面那60分能够骗来……

灵符 · 发表于 2013-11-10 10:43:42

yuebaosanqing 发表于 2013-11-3 17:36
不是。直线的话太容易了。是线段

直线是能用数学直接得出公式或者递推是么……

yuebaosanqing · 发表于 2013-11-10 17:50:33

灵符发表于 2013-11-10 10:43
直线是能用数学直接得出公式或者递推是么……

是的。

灵符 · 发表于 2013-11-11 12:05:41

yuebaosanqing 发表于 2013-11-10 17:50
是的。

昨天晚上没事想了想……好像搜索的时候是要找最优解所以应该是WFS不是DFS上面写错了…搜的时候要记录交点个数只有四个交点的才是矩形（防止两个矩形重叠生成一个矩形两个六边形）地图目测会很大，所以地图切成多个数组或者用求余数法碰运气骗分

恩目测是这样的

灵符 · 发表于 2013-11-11 12:07:11

yuebaosanqing 发表于 2013-11-10 17:50
是的。

交点个数同时可以用来剪枝

yuebaosanqing · 发表于 2013-11-12 21:53:58

灵符发表于 2013-11-11 12:05
昨天晚上没事想了想……好像搜索的时候是要找最优解所以应该是WFS不是DFS上面写错了…搜的时候要记录交点 ...

这道题目其实可以用二分查找来完成。
以每一个横向坐标为扫描循环变量处理

灵符 · 发表于 2013-11-13 11:55:30

yuebaosanqing 发表于 2013-11-12 21:53
这道题目其实可以用二分查找来完成。
以每一个横向坐标为扫描循环变量处理

二分？找什么

yuebaosanqing · 发表于 2013-11-16 17:47:54

灵符发表于 2013-11-13 11:55
二分？找什么

对于每一条竖直的边，枚举在其范围内的横向边。（对横向边排序，二分查找两个端点）

ewei356 · 发表于 2013-11-26 00:45:23

没有然后了

yuebaosanqing · 发表于 2013-12-7 08:59:38

灵符发表于 2013-11-10 10:41
本来想直接全图flood一遍就是了……结果看到司马的绝对值小于一亿……OJ一秒运行忘了是一千万还是一亿来着， ...

其实应该是从边进行排序搜索

sungo163 · 发表于 2013-12-8 00:11:37

编程不一定要弄懂这些吧，除非要做大牛，编点小软件，我觉得这种不太需要了解

路人 · 发表于 2013-12-21 16:34:42

眼花了

真·轮回 · 发表于 2014-1-9 18:02:27

我阵亡了

小橙子姐姐 · 发表于 2014-1-14 15:28:09

很厉害啊

greedisgood · 发表于 2014-1-27 03:29:19

给横线和竖线分别编码，先一个循环拿2维数组记录所有交点的编码，然后三重循环去查每两个横线上交点的相同个数然后累加得出总方块数。。

我知道肯定超时但是只能想到这里了。。orz

账号		自动登录	找回密码
密码			立即注册

【活动】苍海高级程序员试题

二货勋章

周年纪念勋章

会员纪念勋章

伯爵荣耀

苍海的女仆