Loading... M-sea姐姐也太可爱了吧 ## A 头回做交互库的交互,还有点不熟练 吐槽:基本上50分的都是80分解法被卡成50,不得不说BalticOI数据极强 考虑二分,一开始令 $p = 1$ 并询问 $1$,每次把 $p$ 加上 $mid$ 再询问 $p$ 即可,这样是50的。 因为这篇总结是M-sea催促我发的,所以不想写的题解接直接蒯了 这时可以想到让 $p$ 左右横跳,然而初始位置并不好确定。我们假设每次二分(这里指的是 $l ← mid − 1$ 或 $r ← mid + 1$ 形式的二分)都往右,这样子可以得到一个横跳步数的序列,然后即可倒推出一个初始位置。然后以这个初始位置开始左右横跳就可以了。 为什么这样子是对的呢?因为左边的步数比右边短,甚至可能横跳的次数也比右边少,所以如果右边不出界的话某一次跳到左边一定不会出界。 ## B CF原题,详情参见[CF1292B Aroma’s Search](https://tony102.xyz/index.php/2020/10/24/cf1292b-aromas-search/) 全世界应该只有我这个sb是反着跳的吧 $100$变$0$ ## C 不会,但是暴力分给的挺足的。虽然我一分都没拿,因为这题卡SPFA(关于SPFA,它真的死了),你得用拓扑排序求最长路。 考虑只有一组询问的部分分,直接建返图跑单源最短路即可。链就直接数离它最远的没被禁止的点。 为什么我链错了,因为我这个sb觉得直接爆数会炸,我就上下一起跳,跳到有一边跳不了了再另一边继续跳,写挂了。 考虑正解,正解的思想也是个暴力。考虑根号分治 可以把$\sqrt{L}$以内的化一块预处理出距离它最远的 $n$ 个点,这样子询问就只需要找到这些点中不在块中的最远的点即可 如果 $y_i ≥ L$,这样的询问只会有至多 $O( L)$ 个,直接拓扑排序求最长路即可。 ## D ~~**智慧树上智慧果,智慧树下你和我。智慧树前做游戏,欢乐多又多**~~ 这个题跟变个膜法有什么区别,样例都看不懂 ## Summary M-sea的题还是可做的,就是分挂多了 最后修改:2021 年 09 月 04 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏