题解：P7195 [IOI2019] 折线

· · 题解

WC2025 讲，遂写题解。

做法 1

考虑使用绕圈圈方法，第一步从 (0,0) 走到 x 最大的点，然后刚才的那条折线继续延伸直到 y 最大的点的 y 坐标，然后向左拐，左拐以后继续提前准备右拐。

理想情况下每个折线可以达到一个点。

做法 2

刚才那个东西显然无法处理 x_i=y_i=i 这样的情况。

思考一下为什么。我们从一个点绕进去了以后，到达了当前所有未遍历点的右上角。此时你无法通过延长上一条直线来节省步数。

同样的情况还有，当我们来到 (1,1) 这个点时，这个点恰好是所有未遍历点的左下角。此时仍然要多花步数。

考虑单独设计一个做法求这个构造。从左下角遍历到右上角就可以了。

做法 3

考虑把刚才两个东西缝起来。能绕就绕，不能绕就先把这个点删掉然后加入两个队列中的一个。

这两个队列分别是一条从左下到右上的线和从左上到右下的线。

绕完以后把这两个队列走一遍即可。精细实现可以做到步数 \le n+3。