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
全世界应该只有我这个sb是反着跳的吧
$100$变$0$
C
不会,但是暴力分给的挺足的。虽然我一分都没拿,因为这题卡SPFA(关于SPFA,它真的死了),你得用拓扑排序求最长路。
考虑只有一组询问的部分分,直接建返图跑单源最短路即可。链就直接数离它最远的没被禁止的点。
为什么我链错了,因为我这个sb觉得直接爆数会炸,我就上下一起跳,跳到有一边跳不了了再另一边继续跳,写挂了。
考虑正解,正解的思想也是个暴力。考虑根号分治
可以把$\sqrt{L}$以内的化一块预处理出距离它最远的 $n$ 个点,这样子询问就只需要找到这些点中不在块中的最远的点即可
如果 $y_i ≥ L$,这样的询问只会有至多 $O( L)$ 个,直接拓扑排序求最长路即可。
D
智慧树上智慧果,智慧树下你和我。智慧树前做游戏,欢乐多又多
这个题跟变个膜法有什么区别,样例都看不懂
Summary
M-sea的题还是可做的,就是分挂多了