NFLSPC #2 月 题解

2019-11-28 22:47:57 By wzy

考虑从左到右找每个1的位置 通过二分答案找

直接对着位置二分答案要非常多的询问 我们发现它的缺陷在于每次二分时两种情况发生的概率差别很大

我们换一种方式二分答案:每次找到一个位置 使下一个1在这个位置或其左边的概率与在其右边的位置尽量相等

这样我们得到了一个平均4728的做法 可以得到90分

一共有C(10000,1000)种情况 最优情况下平均只要4683次就可以找到 所以还有不小优化空间

考虑调参 并且考虑到二分的时候有两种很不一样的情况(区间非常大和区间非常小)因为第一次发现第一个1在询问位置左之前平均区间长度5000左右 第一次发现第一个1在询问位置左之后区间长度不超过15 我们把两种情况分开调参

经过轻微的调参即可做到4717-4718 可以通过此题

说一下需要调参的原因:

每次使答案在左侧的可能性尽量靠近0.5并不是最优的,最优可能是0.48或者0.52,这是因为只考虑答案在左边或右边的概率并不全面,还需要考虑答案在左右时的期望操作次数。其中一个处理方法就是调参。

这道题应当还有更优的做法 欢迎有想法的选手介绍自己的做法

$by\ \text{skyline}$

评论

avatar
skyline
不是这个意思啊 我让你直接写纸上的版本 抛弃老版本……
avatar
dancecherry
二分就做到了4752的样子……调参这东西属于细节优化范畴了,对数量级不影响,我这个做工程的不深究了,反正4752和4718也只差不到百分之一,工作中用不着了。。

发表评论

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