POI2013 LAB-Maze 题解
UNVRS
·
·
题解
题意
给定一个长度为 n 的仅由 \texttt{LP} 构成的序列，描述一个包含 n 个点的、边与坐标轴平行的逆时针简单多边形，其中 \texttt{L} 表示往左拐，\texttt{P} 表示往右拐，可能无解。
n\le 10^5
约定
具体表示全局或是某个区间内的应该可以通过上下文推导。
所有图片仅供示意，实际运行时（应该）都不会出现。
## 思路
一个简洁明快的线性做法。
首先我们来判定有无解。
不管是原文题面还是翻译题面都没有提到多边形是逆时针的，幸好有好心人在讨论区提供了一份 SPJ 并且十分可以研读，不然我估计这辈子玩不明白 90 分是什么玩意。
那么显然，有解的情况当且仅当 $cnt_\texttt L-cnt_\texttt R=4$。
---
然后我们来考虑选取四个 $\texttt L$ 作为整个多边形的端点，要求满足两个 $\texttt L$ 之间 $cnt_\texttt L=cnt_\texttt R$，这样我们可以考虑先把这中间四部分构造出来，然后再拼起来。
> 为什么是 $cnt_\texttt L=cnt_\texttt R$ 呢，你发现这样的一个区间满足一个性质，初始方向和结束方向是相同的，所以从某种意义上，我们可以将这样一个区间构造出来的图形，视作为一个非常非常粗的线段。
>
> 这也是我们之后一定能在四个端点处将这四个图形拼起来的原因：把这四段视作为线段，最后相当于构造一个矩形。
那么满足了 $cnt_\texttt L=cnt_\texttt R$，我们发现我们可以将区间视作为一个类似于括号序的结构，不难发现可以由以下方法构造：
1. 在两端增加一对相反的方向。
2. 合并两个区间。
具体的维护可以维护一个矩形，其延伸出两条线段：
> 中间的部分仅作示意，我们实际维护的时候只维护那两个端点延伸出来的线段。
然后对于增加两个相反的方向的操作，那么就是将线段转向，延伸到矩形以外，然后旋转 $90\degree$：
然后对于合并两个矩形的操作：
我相信已经不需要我过多解释这些是什么意思了，三张图很清楚了。
---
然后考虑得到了四块矩形，如何合并。
显然 $\texttt L$ 端点对应的点应该是 *上一个矩形的右端点延伸出来的边*，以及 *下一个矩形的左端点延伸出来的边* 的交点。
我们不妨令 *下一个矩形的左端点延伸出来的边* 立刻旋转一次（固定该 $\texttt L$ 端点位置），然后直接伸长接到 *上一个矩形的右端点延伸出来的边* 上，这样只需要延伸得足够长，即可保证这两个矩形无交。
见下图：
那么接下来来到最后一步，我们这样构造的图形很可能不是闭合的。
这也很简单，我们只需要按照流程模拟一遍，最后通过起点与终点的坐标差微调一下长度即可：
例如在上图中，我们应该加长线段 $A$ 与线段 $C$。
只要我们保证我们每次是加长两根线段，就可以确保修正之后不会发生重合。
~~当然你也可以试着去直接对着矩形维护出来的信息硬算，我试过，放弃了~~
## 实现
思路不难，实现起来细节很多。
一开始可以将左边的若干个 $\texttt P$ 移到最右段，这样令第一个字母是 $\texttt L$，这样可以防止最后一个区间被拆成两个。
我们可以将我们需要维护的矩形封装一下，维护以下信息：
```c++
struct sqr{
int w, // 宽度
h, // 高度
lx, // 左端点延伸线段的长度
ly, // 右端点延伸线段的长度
nx, // 左端点延伸线段的在答案序列中的编号
ny, // 右端点延伸线段的在答案序列中的编号
x, // 左端点延伸线段的位置
y; // 右端点延伸线段的位置
};
```
如下图所示：
然后对于添加两个方向的操作：
```c++
// 0 表示左端点左转，1 表示左端点右转
sqr operator^(bool b){
// 转向之后左右两条边的长度就固定了，丢到答案上
if(!len[nx]) len[nx]=lx;
if(!len[ny]) len[ny]=ly;
return(sqr{h,
w+2, // 旋转 90 度之后长宽互换，并且高度 +2
b?h-x+1:x,
b?y:h-y+1, // 按照方向讨论一下，这里不放图了自己手画一下
nx-1,
ny+1, // 编号移动一下
b?1:w+2,
b?w+2:1 // 位置调整，自己手画一下
});
}
```
然后合并两个区间：
```c++
void operator+=(const sqr &b){
if(!len[ny]) len[ny]=ly+b.lx-1; // 将两个线段无转角地合并
*this=sqr{w+b.w, // 宽度直接相加
max(h-y,b.h-b.x)+
max(y,b.x), // 高度注意中间合并的线段位置会对结果造成影响
lx,b.ly,nx,b.ny, // 复制信息
x+max(b.x-y,0),
b.y+max(y-b.x,0) // 修正新的位置
};
}
```
---
实际上我写的时候写的是一个搬的题，那题加了一个可以选择添加一个额外拐点（这个非常阴间），然后多组数据，然后可以顺时针，还要求离散化，但是 $n\le1000$。
~~徒增大量细节，不知道搬题人怎么想的~~
**怎么都在贺代码，代码撤掉了。**
