自动搬运

查看原文

来自洛谷，原作者为

	UNVRS 名为遗憾，无相无形，噬人心骨

搬运于2025-08-24 21:50:10，当前版本为作者最后更新于2022-11-25 11:21:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给定一个长度为 $n$ 的仅由 $\texttt{LP}$ 构成的序列，描述一个包含 $n$ 个点的、边与坐标轴平行的逆时针简单多边形，其中 $\texttt{L}$ 表示往左拐，$\texttt{P}$ 表示往右拐，可能无解。

$n\le 10^5$

约定

$cnt_\texttt L$ 表示 “$\texttt L$ 的数量”，$cnt_\texttt R$ 同理。

具体表示全局或是某个区间内的应该可以通过上下文推导。

所有图片仅供示意，实际运行时（应该）都不会出现。

思路

一个简洁明快的线性做法。

首先我们来判定有无解。

不管是原文题面还是翻译题面都没有提到多边形是逆时针的，幸好有好心人在讨论区提供了一份 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$，这样可以防止最后一个区间被拆成两个。

我们可以将我们需要维护的矩形封装一下，维护以下信息：

struct sqr{
    int w,  // 宽度
    	h,  // 高度
    	lx, // 左端点延伸线段的长度
    	ly, // 右端点延伸线段的长度
    	nx, // 左端点延伸线段的在答案序列中的编号
    	ny, // 右端点延伸线段的在答案序列中的编号
    	x,  // 左端点延伸线段的位置
    	y;  // 右端点延伸线段的位置
};

如下图所示：

然后对于添加两个方向的操作：

// 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    // 位置调整，自己手画一下
              });
}

然后合并两个区间：

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$。

徒增大量细节，不知道搬题人怎么想的

怎么都在贺代码，代码撤掉了。