UOJ Logo Rating_Getter的博客

博客

hash作为标准解法合理吗?

2017-08-28 18:48:33 By Rating_Getter

关于NOI2017d1t2,有人认为hash不应该作为一道题目的标准解法,因为其有概率可能出现错误。

但例如bzoj1014,其目前还没有不用hash而能通过的做法。但一直没有人对这个题目产生怀疑。

我认为只要能有理有据的证明出错的概率在正常数据下极低,hash就可以作为标准解法。

大家有什么观点?

评论

oscar
前排滋磁“出错概率低就可以作为标准解法”
Picks
电子计算机在计算时有约1e-17的概率出现比特翻转。
negiizhao
Treap可能会被卡到$O(n)$
Alextokc
快排可能会被卡到O(n^2)
OldDriverTree
Claris有1e-18的几率女装 但是你不能说她不女装啊
OldDriverTree
话说bzoj1014第一页其他人到底写的啥啊 该不会真的是xjb预处理然后线段树吧。。。
WuHongxun
hash一般属于RP或者BPP算法,作为标解非常合理
613
很多东西是不用hash就很难做的 比如我在hn省队集训上出的一个题叫做tower
hqztrue
“例如bzoj1014,其目前还没有不用hash而能通过的做法”据我所知确实如此。但需要指出的是,hash不代表一定有出错的可能:例如这篇SODA18的paper https://arxiv.org/pdf/1511.02612.pdf看起来是可以在n log n时间内解决1014的(虽然实际是否能AC是个问题),它用到了随机化和hash,但一定不会出错。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。