初赛结束了,开始加训复赛。
来自 misaka16172 大手子的推荐。%%%
这里是题单链接:link
CF1153E Serval and Snake
*2200
交互,思维,二分
首先非常困难的一点就是要注意到当回答为奇数时,说明有恰好一个端点(头尾)在矩形里。
感性理解一下,没有端点就是在中间,肯定是从外面进来再出去,几个进来出去肯定就是偶数。要不然就是头尾都在,就少一个进来出去。
考虑枚举行,找到为奇数的两行。现在横坐标确定了,直接在行上二分就行。要不然头尾都在一行,再枚举列,然后二分。这样最多的询问次数是 \(n+n+2\log n=2020\),刚好倒闭。
然后你发现在枚举列的时候,第二列是不用二分的,因为横坐标一定相同。这下就过了。
submission。