POI2013 LAB-Maze

题意

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

约定

表示 “ 的数量”， 同理。

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

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

思路

首先我们来判定有无解。

不管是原文题面还是翻译题面都没有提到多边形是逆时针的，幸好有好心人在讨论区提供了一份 SPJ 并且十分可以研读，不然我估计这辈子玩不明白 90 分是什么玩意。

那么显然，有解的情况当且仅当 。

然后我们来考虑选取四个 作为整个多边形的端点，要求满足两个 之间 ，这样我们可以考虑先把这中间四部分构造出来，然后再拼起来。

为什么是 呢，你发现这样的一个区间满足一个性质，初始方向和结束方向是相同的，所以从某种意义上，我们可以将这样一个区间构造出来的图形，视作为一个非常非常粗的线段。

这也是我们之后一定能在四个端点处将这四个图形拼起来的原因：把这四段视作为线段，最后相当于构造一个矩形。

那么满足了 ，我们发现我们可以将区间视作为一个类似于括号序的结构，不难发现可以由以下方法构造：

  1. 在两端增加一对相反的方向。
  2. 合并两个区间。

具体的维护可以维护一个矩形，其延伸出两条线段：

中间的部分仅作示意，我们实际维护的时候只维护那两个端点延伸出来的线段。

然后对于增加两个相反的方向的操作，那么就是将线段转向，延伸到矩形以外，然后旋转 ：

然后对于合并两个矩形的操作：

我相信已经不需要我过多解释这些是什么意思了，三张图很清楚了。

然后考虑得到了四块矩形以及八个端点，如何合并。

显然 端点对应的点应该是 上一个矩形的右端点延伸出来的边，以及 下一个矩形的左端点延伸出来的边 的交点。

我们不妨令 下一个矩形的左端点延伸出来的边 立刻旋转一次（固定该 端点位置），然后直接伸长接到 上一个矩形的右端点延伸出来的边 上，这样只需要延伸得足够长，即可保证这两个矩形无交。

见下图：

那么接下来来到最后一步，我们这样构造的图形很可能不是闭合的。

这也很简单，我们只需要按照流程模拟一遍，最后通过起点与终点的坐标差微调一下长度即可：

例如在上图中，我们应该加长线段 与线段 。

只要我们保证我们每次是加长两根线段，就可以确保修正之后不会发生重合。

当然你也可以试着去直接对着矩形维护出来的信息硬算，我试过，放弃了

实现

思路不难，实现起来细节很多。

一开始可以将左边的若干个 移到最右段，这样令第一个字母是 ，这样可以防止最后一个区间被拆成两个。

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

1
2
3
4
5
6
7
8
9
10
struct sqr{
    int w,  // 宽度
        h,  // 高度
        lx, // 左端点延伸线段的长度
        ly, // 右端点延伸线段的长度
        nx, // 左端点延伸线段的在答案序列中的编号
        ny, // 右端点延伸线段的在答案序列中的编号
        x,  // 左端点延伸线段的位置
        y;  // 右端点延伸线段的位置
};

如下图所示：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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    // 位置调整，自己手画一下
              });
}

然后合并两个区间：

1
2
3
4
5
6
7
8
9
10
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)       // 修正新的位置
             };
}

实际上我写的时候写的是一个搬的题，那题加了一个可以选择添加一个额外拐点（这个非常阴间），然后多组数据，然后可以顺时针，还要求离散化，但是 。

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

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100010,FSIZE=1<<20,fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,len[N],sts;
struct{
    int x;    // 该层对应的矩形编号
    bool y;   // 该层外面两边的方向
}st[N];       // 栈
struct point{int x,y;}ans[N];
vector<int> a;
bool s[N];
struct sqr{
    int w,h,lx,ly,nx,ny,x,y;
    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)       // 修正新的位置
                 };
    }

    // 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    // 位置调整，自己手画一下
              });
    }
}d[N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
sqr solve(int l,int r){
    if(l>r)
        return(sqr{0,1,0,0,0,0,0,0});
    for(d[0]=sqr();l<=r;++l){
        if(sts&&s[l]!=st[sts].y){   // 这里需要魔改一下括号序的弹栈规则
            if(!d[sts--].w){        // 如果下一层矩形为空
                d[sts+1]={1,2,1,1,l-1,l+1,s[l]?1:2,s[l]?2:1};
                len[l]=1;
            }else
                d[sts+1]=d[sts+1]^s[l];    // 旋转
            if(!d[sts].w)
                d[sts]=d[sts+1];    // 如果当前层矩形为空直接复制
            else
                d[sts]+=d[sts+1];   // 否则合并
            d[sts+1]=sqr();
        }else{
            st[++sts]={l,s[l]};
            d[sts]=sqr();
        }
    }
    return(d[0]);
}
void calc(int m){    // 按照当前的长度情况模拟出答案各点的坐标
    ans[m]={0,0};
    for(int i=m,f=0;i<=n;++i){
        ans[i+1]={ans[i].x+fx[f][0]*len[i],ans[i].y+fx[f][1]*len[i]};
        if((s[i]?++f:--f)>3) f=0;
        else if(f<0) f=3;
    }
}
void work(){
    int L=0,R=0,m=1,p=0;
    for(int i=1;*InF>32;(s[i++]=*InF++=='P')?++R:++L,++n);
    if(L-R!=4){
        printf("NIE\n");
        return;
    }

    // 将左边的 R 移到右边
    for(a.clear();s[m];s[++n]=s[m++]);

    // 找到四个端点
    for(int i=m,d=0;a.size()<4;++i)
        if(!d&&s[i]==s[m]) a.push_back(i);
        else s[i]==s[m]?++d:--d;

    // 计算四个矩形
    len[a[0]]=(solve(a[0]+1,a[1]-1)^0).lx+N;
    len[a[1]]=(solve(a[1]+1,a[2]-1)^0).lx+N;
    len[a[2]]=(solve(a[2]+1,a[3]-1)^0).lx+N;
    len[a[3]]=(solve(a[3]+1,n     )^0).lx+N;

    // 进行一次模拟
    calc(m);

    // 修正 x
    if(ans[n+1].x>0)
        len[a[0]]+=ans[n+1].x;
    else
        len[a[2]]-=ans[n+1].x;

    // 修正 y
    if(ans[n+1].y>0)
        len[a[1]]+=ans[n+1].y;
    else
        len[a[3]]-=ans[n+1].y;

    // 计算答案
    for(calc(m);m>1;ans[--m]=ans[n--]);
    for(int i=m+p;i<=n;++i) printf("%d %d\n",ans[i].x,ans[i].y);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    work();
    return(0);
}

≡