一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1565|回复: 14
收起左侧

Q代码挑战

[复制链接] |试试Instant~ |关注本帖
slaink 发表于 2016-10-13 03:48:49 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 实习@Quora - 内推 - 在线笔试 |Fail其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
这家我死的心服口服。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
六十分钟一道题,给一堆二维的信封,每个信封有长和宽,如果一个信封的长比另一个的长而且宽也比另一个的宽,那么就能把小的放大的里面。也就是说只能长比长宽比宽,不能旋转,而且一个信封里面只能塞一个信封(甲装乙里,乙装丙里,但是不是甲和乙都放丙里。放完之后甲乙丙就从三个信封变成了一个信封)。把小信封放到大信封里,最后需要几个信封?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这题后来高人说是min path coverage,用最大流解。


补充内容 (2016-10-13 09:50):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷我是写的LIS,每次取出来最长的那个LIS,然后剩下的继续做LIS直到所有信封都没了。复杂度N方。但是这样贪心应该是错的。

评分

3

查看全部评分

yhatl 发表于 2016-10-13 09:19:42 | 显示全部楼层
见LC354

字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数
回复 支持 反对

使用道具 举报

 楼主| slaink 发表于 2016-10-13 09:25:42 | 显示全部楼层
yhatl 发表于 2016-10-13 09:19. visit 1point3acres.com for more.
见LC354

字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数 ...

并不是,那个简单。这个是要你按russian doll 放完之后剩下几堆那样的russian doll。. 1point3acres.com/bbs
. 1point3acres.com/bbs
补充内容 (2016-10-13 09:26):
我就是按LIS写的贪心,每次把最长的那个取出来。
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-10-13 09:31:51 | 显示全部楼层
嗯 不是原题。
是不是应该重复russian doll 一直到装完?
回复 支持 反对

使用道具 举报

 楼主| slaink 发表于 2016-10-13 09:35:12 | 显示全部楼层
yhatl 发表于 2016-10-13 09:31
嗯 不是原题。
是不是应该重复russian doll 一直到装完?

不,我就是那么写的,应该是错的。你可以理解为一个有向图,A指向B如果B可以装下A。目标是找到最少需要多少没有重叠的线段(不重复使用边和点),能够把整个有向图cover。
回复 支持 反对

使用道具 举报

suiyuan2009 发表于 2016-10-13 09:45:21 | 显示全部楼层
dp比最大流快吧
回复 支持 反对

使用道具 举报

zt5840 发表于 2016-10-13 11:22:34 | 显示全部楼层
问题描述. 鍥磋鎴戜滑@1point 3 acres
          给定有向图 G=(V,E)。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个顶点恰好在 P 的一条路上,则称 P是 G 的一个路径覆盖。P 中路径可以从 V 的任何一个顶点开始,长度也是任意的,特别地,可以为0。G 的最小路径覆盖是 G 的所含路径条数最少的路径覆盖。

算法思想
        把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

有向无环图最小覆盖算法流程.1point3acres缃
        1.构建二分图,原图中的每个点V拆成Vx和Vy,如果有一条有向边A->B,那么就加边Ax-By。这样就得到了一个无向的二分图。
        2.求最大匹配数

确实是个经典的题,会就是会,不会就不会。
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-25 12:58:00 | 显示全部楼层
我也是这道题,挂的没脾气
回复 支持 反对

使用道具 举报

peteraristo 发表于 2016-10-27 03:48:21 | 显示全部楼层
按匈牙利算法写了,还是挂。。。
感觉他家目前不想招人,据说以前都没有OA。
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-7 14:51:02 | 显示全部楼层
我想说的,第一,我们570算法课讲过这道题,是用dp做的,按照面积大小排序,但是最后是问最多能堆几个盒子,求最大高度
第二,楼主这里说的信封,我大概理解为是抽象了一下 这个box,  没有理解的是什么叫 求把小信封放到大信封里,最后需要几个信封?
  神马叫需要几个信封? 你不是都说了N个信封,如果全都装进去 那就是N个信封啊,还是说你想问的是 最多·能这样进行装入,能装几个信封为一体?
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-7 15:30:05 | 显示全部楼层
哦 你想问的是 最后最少能装到只剩下几个一体的信封~
回复 支持 反对

使用道具 举报

peteraristo 发表于 2016-11-8 03:13:46 | 显示全部楼层
格格笑 发表于 2016-11-7 15:30
哦 你想问的是 最后最少能装到只剩下几个一体的信封~

所以你理解DP不对了吧。
不过也可能出题人就是想考DP呢。
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-8 04:08:22 | 显示全部楼层
嗯,但我仍然不知道最大流怎么做 ,待会发一个我用最大流做出的不对的解法~还有一个重要的事,楼主有oa截图啥的吗
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-8 05:34:53 | 显示全部楼层
你看楼主, 如果有三个 信封 分别是 [1,3] [2, 3] [2,2] 最后算出来应该是2对吧  你说的最大流怎么做?  哦  突然想明白了  你说的那个箭头的方向有点问题哈,应该是 A 能装 下B 就用A 指向B   A是大的 B是小的  这样才能解~,  不然  [1,3] [2, 3] [2,2]  这个例子你会算出来是1   而其实应该是2~
回复 支持 反对

使用道具 举报

jerry1394 发表于 昨天 10:18 | 显示全部楼层
按长sort,然后算宽的最长递增子列。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表