资讯详情

初赛结束了，开始加训复赛。

来自 misaka16172 大手子的推荐。%%%

这里是题单链接：link

CF1153E Serval and Snake

*2200

交互，思维，二分

首先非常困难的一点就是要注意到当回答为奇数时，说明有恰好一个端点（头尾）在矩形里。

感性理解一下，没有端点就是在中间，肯定是从外面进来再出去，几个进来出去肯定就是偶数。要不然就是头尾都在，就少一个进来出去。

考虑枚举行，找到为奇数的两行。现在横坐标确定了，直接在行上二分就行。要不然头尾都在一行，再枚举列，然后二分。这样最多的询问次数是 \(n+n+2\log n=2020\)，刚好倒闭。

然后你发现在枚举列的时候，第二列是不用二分的，因为横坐标一定相同。这下就过了。

submission。