有哪些算法或数据结构是ACM大牛们在比赛中创造出来的？

ACM大牛们对基础数据结构和算法的研究可谓苦心孤诣；我想知道的是，现在我们已知的数据结构和算法中，有没有哪个是由ACMer们在比赛或平时训练中创造的，或加以显著改进的？

我这里说的数据结构和算法，是偏向于基础性的方面，例如在wiki百科上能查到的词条，或对已知的一般书上能查到的常用数据结构和算法的改进；不包括大牛们参加工作或学术研究之后，对某个领域，例如特定的数值算法或某个特定芯片上的算法优化。

MarsZhangLing · 2018-9-28 00:21:32

类比要小学生发明创造，有可能，但可能性不大，比赛只是比赛，这是个最多只能研一参加的比赛。倘若大四后参赛，即使拿到世界冠军，个人也不是很佩服。这比赛本身就是针对特定年龄段的，非最高奖项，真要说明成就，参考历年图灵奖得主。

匿名用户 · 2018-9-28 00:21:31

提示: 作者被禁止或删除内容自动屏蔽

废柴少女skyline · 2018-9-28 00:21:30

每当我现场创造神奇算法结束后总有大佬告诉我是经典算法
可能跑题了

Stump · 2018-9-28 00:21:29

水一发
一些数论筛法叶氏筛法，杜教筛，洲阁筛，Min_25筛什么的

潇洒 · 2018-9-28 00:21:27

在noip新手阶段noip考场推出扩展gcd
某场网络赛没接触过情况下队友推出斯坦钠树

无限cdq分治
splaytreap

秦航 · 2018-9-28 00:21:26

SBT_百度百科

这个算吗。不知道为什么维基百科的页面没有了。

其实我觉得ACMer对算法的贡献在于不断优化一种这种算法的实现方案。
代码更短，更清晰，更不容易出错。
比如罗穗骞那个丧心病狂的后缀数组的实现，刷新了“更短”等等。

算法合集之《后缀数组――处理字符串的有力工具》

听雨 · 2018-9-28 00:21:25

以前俺们老师说过有个家伙发明了双向搜索
当时中国队还不会动态规划，IOI遇到一个题目，只有那个家伙做的全对。

李冰 · 2018-9-28 00:21:23

想当年本蒟蒻在高一时参加NOIP2011(第一次参加比赛。。)
当时day2A题是个关于多项式的问题(经知友提醒这个题目叫计算系数)，花了大量时间发现原来系数是有规律的，简单的推了下得出了:f[i+1][j]=f[j]+f[j+1]....惊喜的敲出来，最后把这大水题过了。

尼玛到高二的一堂数学课才知道这玩意叫杨辉三角。。。。。

有哪些算法或数据结构是ACM大牛们在比赛中创造出来的？

8 个回复