赛氪

发布

竞赛活动

【ACM学神来了】第三期“数据结构”专题直播，嘉宾：马鑫宇，北京理工大学，区域赛一金，一银，两铜

关注 7

学神来了.005.jpg

图1.jpg

问答时间：2015年 7月11日 16:00-17:00

提问方：赛氪用户

答疑方：马鑫宇

问答规则：

提问同学请在问题前输入【ACM学神来了】马甲进行提问，例如“【ACM学神来了】，请问P神XXXXX”；

提问范围仅限 ACM相关问题，大神会现场进行解答；

直播过程中可以发表看法、想法，但严禁刷屏；

直播时间为1小时，请各位同学抓紧提问，如想进一步讨论交流可加入如下QQ群；

ACM赛氪直播交流QQ群：468023758

赛氪微信公众平台：

52个回答（按时间倒序 · 按时间正序）发表回答

马鑫宇

北京理工大学· 2015-07-11

好了，那么今天的解答到此结束，感谢各位捧场。

PS：Orz11菊苣！11菊苣教我进Final！11菊苣教我在Final上虐清华北大！

评论 1 赞同 12

李美琳 Orz马神
2015-07-11 回复

回复取消

吴德兰

福建师范大学· 2015-07-11

如何把多叉树转成二叉树

评论 1 赞同 12

马鑫宇左孩子右兄弟。“我把你们当兄弟，你们却把我当父亲”当然你要是边分治的话，加入虚节点也可以。
2015-07-11 回复

回复取消

赵倩倩

暨南大学· 2015-07-11

最短路径的求法和应用？

评论 1 赞同 10

马鑫宇这个建议看一看清华出版的《网络优化》，详细讲了最短路从线性规划转化成动态规划再转化成标号修正算法的过程。
2015-07-11 回复

回复取消

李若谷

哈尔滨工程大学· 2015-07-11

Treap树和其他一些平衡树的区别在哪

评论 1 赞同 11

马鑫宇 ACM中用到的Treap主要是非旋转Treap，可以看吕凯风（就是传说中的VFK）的论文《对无旋转操作的平衡树的一些探究》。
2015-07-11 回复

回复取消

王宇义

东北大学· 2015-07-11

马神，并查集的路径压缩是什么意思？

评论 1 赞同 11

马鑫宇就是在回溯的时候修改父亲节点的指针。
2015-07-11 回复

回复取消

张辰龙

河海大学· 2015-07-11

ACM学神来了可持久化Treap和普通Treap的区别

评论 1 赞同 9

马鑫宇普通Treap是旋转的，可持久化Treap不旋转，而且也没有向父亲的指针。
2015-07-11 回复

回复取消

周勇

湖南理工学院· 2015-07-11

树链剖分是怎么剖分树从而使得效率提高的？

评论 1 赞同 10

马鑫宇这个看之前的论文就好了。
2015-07-11 回复

回复取消

张云锋

东北林业大学· 2015-07-11

KD-Tree是一种什么树结构？是怎么查找到最近点的？

评论 1 赞同 13

马鑫宇 KD-Tree我觉得吧，就是一个每次按不同维度比较大小的替罪羊树。最近点查找其实是启发式的回溯搜索，效率不高，据说根号的算法。
2015-07-11 回复

回复取消

田婷

南京邮电大学· 2015-07-11

树链剖分是怎么剖分树从而使得效率提高的？

评论 1 赞同 11

马鑫宇 HLD的话你看杨哲的《QTREE解法的一些研究》吧，是靠重孩子的性质实现的。
2015-07-11 回复

回复取消

邓晓倩

中国矿业大学· 2015-07-11

【ACM学神来了】跳跃表是什么东西，在ACM里面有用么？

评论 1 赞同 8

马鑫宇跳表那东西貌似是个黑科技，我没用过，ACM目前来看出的题很少。
2015-07-11 回复

回复取消

洲少

江苏大学· 2015-07-11

Treap,SBT,Splay他们各自的用处在哪里

评论 1 赞同 9

马鑫宇 Treap和Splay用处比较大，因为可以提取区间，可以打标记；Treap还能持久化。SBT就是快，但它是个裸的平衡树，一般不用来搞别的。（至少我没听说过有人SBT提取区间的，也许是我姿势水平不够？）
2015-07-11 回复

回复取消

叶子

中国海洋大学· 2015-07-11

主席树，笛卡尔树是什么一种树？

评论 1 赞同 14

马鑫宇主席树就是树状数组套线段树。笛卡尔树没用过，没记错的话应该就是个树堆？ACM应该也不考这个。
2015-07-11 回复

回复取消

林浩成

东北大学· 2015-07-11

马神，我想问一下， 10000个int范围内的数字用hash存储应该开多大空间的数组？除数取余的质数又该选取多大的质数？还有就是，针对此题，hash好还是直接用stl的map好？

评论 1 赞同 13

马鑫宇这个不好说，看你需求。我觉得map就挺好的，不行就unordered_map。自己hash的话当然是开越大越好。要是评测机给开10G内存不判MLE我就敢开2^32……
2015-07-11 回复

回复取消

熊梅

江西师范大学· 2015-07-11

前缀树和后缀树的区别是什么

评论 2 赞同 11

熊梅后缀树和后缀数组的区别又是什么
2015-07-11 回复

回复取消
马鑫宇前缀树应该是Trie树？我没用过不太清楚。后缀树就是把所有后缀做成一个Trie树。裸的后缀树效率太低所以一般是压缩的后缀树，或者是后缀自动机一类的。后缀数组只是把所有后缀排个序而已，根本没有树形结构，也不能直接用来匹配。（所以后缀数组一般都要用加#加目标字符串的形式串在一起再搞）
2015-07-11 回复

回复取消