P3134 [USACO16JAN] Lights Out G 关灯

[USACO16JAN] Lights Out G

题面翻译

题目描述

Farmer John 在他的谷仓里安装了一个非常不错的新挤奶机，但是这台挤奶机耗电太多了，有时候会让谷仓直接停电！这种事发生的太频繁了，以至于 Bessie 直接把谷仓的地图背过了，以便于可以在黑暗中找到谷仓的出口。她对于停电对于她快速离开谷仓的能力的影响非常好奇。比如说，她想知道她在黑暗中需要走多远来找到谷仓的出口。

谷仓里的路可以被描述为是一个简单的用几个顶点来表示的多边形，这些顶点可以按照顺时针被表示为 $(x_{1}, y_{1}) \dots (x_{n}, y_{n})$ （保证这些顶点连成的线没有交叉的情况）。这些点构成的边在水平轴（平行于 $x$ 轴）和竖直轴（平行于 $y$ 轴）之间交替出现。第一条边可以是任意一种类型。谷仓出口在坐标 $(x_{1}, y_{1})$ 。Bessie 从谷仓内任意一个点 $(x_{i}, y_{i})$ 开始走。她只可以沿着这些边走，要不然是顺时针，要不然就是逆时针，她的目标就是以最短距离抵达出口。当然，如果灯亮着的话这个事还算相对简单，因为她要不然顺时针要不然逆时针走，无所谓哪个方向的路程更短一点。

一天，谷仓突然停电了，导致 Bessie 受到惊吓、忘记了她站在哪个顶点。幸亏她还记得谷仓的准确地图，所以她可以四处走走，用她的触觉来弄清楚她的位置。不管什么时候，只要她站在一个顶点，那么她就可以感受到她在这个点的朝向角度，弄清楚这个点是不是出口。当她沿着谷仓的一个边走完的时候，她可以算出精确的边长。Bessie 决定用这么一个策略：她会顺时针沿着谷仓周围的边走，直到她知道了足够的角度和边、可以推断出她目前在的是哪个顶点。在那个顶点，她就可以轻易地弄清楚怎样以最短距离到达出口（要不然继续沿着顺时针走，要不然倒回去沿着逆时针走）。

请帮助 Bessie 算出在起点可以是任何一个顶点情况下，在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

输入格式

第一行包括一个数字 $N (4 ⩽ N ⩽ 200)$ ，接下来 $N$ 行，每行包括两个数字，沿着顺时针表示顶点 $(x_{i}, y_{i})$ $x_{i}, y_{i} \in [- 10^{5}, 10^{5}]$ 。

输出格式

输出 Bessie 在最坏的情况下，她在黑暗中和亮着灯的时候到达出口的距离的差值（即找到差值的最大值）。

说明/提示

在这个样例中，Bessie 开始可以感觉到她沿着 $90 \degree$ 角站着，但是她辨别不出来她是在 $2, 3, 4$ 中的哪一个顶点。

在走了一条边以后，Bessie 要不然到了出口要不然就可以根据她走过的距离推断出她的位置。情况如下：

如果她从 $2$ 号点开始走，她需要在黑暗中走 $12$ 个单位，包括一个单位到达第三个点、十一个单位离开谷仓。同时，如果亮着灯，她可以只走 $10$ 个单位就离开谷仓。差值是 $2$ 。

如果从 $3$ 号点开始，她两种情况都要走 $11$ 个单位。

如果从 $4$ 号点开始，她两种情况都要走 $1$ 个单位。

所以最坏情况差值是 $2$ 。

题目描述

Farmer John has installed a fancy new milking machine in his barn, but it draws so much power that it occasionally causes the power to go out! This happens so often that Bessie has memorized a map of the barn, making it easier for her to find the exit of the barn in the dark. She is curious though about the impact of power loss on her ability to exit the barn quickly. For example, she wonders how much farther she might need to walk find the exit in the dark.

The barn is described by a simple (non self-intersecting) polygon with integer vertices $(x_{1}, y_{1}) \dots (x_{n}, y_{n})$ listed in clockwise order. Its edges alternate between horizontal (parallel to the x-axis) and vertical (parallel to the y-axis); the first edge can be of either type. The exit is located at

$(x_{1}, y_{1})$ . Bessie starts inside the barn located at some vertex $(x_{i}, y_{i})$ for $i > 1$ . She can walk only around the perimeter of the barn, either clockwise or counterclockwise, Her goal is to travel a minimum distance to reach the exit. This is relatively easy to do with the lights on, of course, since she will travel either clockwise or counterclockwise from her current location to the exit — whichever direction is shorter.

One day, the lights go out, causing Bessie to panic and forget which vertex she is standing at. Fortunately, she still remembers the exact map of the barn, so she can possibly figure out her position by walking around and using her sense of touch. Whenever she is standing at a vertex (including at her initial vertex), she can feel the exact interior angle at that vertex, and she can tell if that vertex is the exit. When she walks along an edge of the barn, she can determine the exact length of the edge after walking along the entire edge. Bessie decides on the following strategy: she will move clockwise around the perimeter of the barn until she has felt enough angles and edges to deduce the vertex at which she is currently located. At that point, she can easily figure out how to get to the exit by traveling a minimum amount of remaining distance, either by continuing to move clockwise or by switching direction and moving counter-clockwise.

Please help Bessie determine the largest amount by which her travel distance will increase in the worst case (over all possibilities for her starting vertex) for travel in the dark versus in a lit barn.

输入格式

The first line of the input contains $N$ ( $4 \leq N \leq 200$ ). Each of the

next $N$ lines contains two integers, describing the points $(x_{i}, y_{i})$ in

clockwise order around the barn. These integers are in the range

$- 100, 000 \dots 100, 000$ .

输出格式

Output the largest amount that Bessie’s travel distance will increase in the

worst case starting position using the strategy in the problem statement.

样例 #1

样例输入 #1

样例输出 #1

提示

In this example, Bessie can feel that she is initially standing at a 90-degree

angle, but she cannot tell if she is initially standing at vertex 2, 3, or 4.

After taking a step along one edge in the clockwise direction, Bessie either

reaches the exit or can uniquely determine her location based on the length of

this edge. The distances she obtains are:

If starting at vertex 2: she travels 12 units in the dark (1 unit to reach

vertex 3, then 11 units to continue to the exit). She only needs to travel 10

units in a lit barn. This is an extra distance of 2 for this vertex.

If starting at vertex 3: she travels 11 units in both cases.

If starting at vertex 4: she travels 1 unit in both cases.

The worst-case difference over all starting points is therefore 12 – 10 = 2. That

is, Bessie can guarantee that using her strategy, no matter where she starts,

she will travel at most 2 extra units of distance farther in the dark than in the light.

题目大意

贝西开始会在一个点往 $n$ 走，当她发觉自己走了一段独特的路径时她就会沿着最短路径回到 $1$ 号点，请问她最多需要多花多长时间？

分析

我们需要一种数据结构：

1、可以查找路径在地图上出现的次数

2、支持在末尾更新路径信息

3、每种地图只有一种表达方式

所以我们想到 字符串哈希

~~ye哥只有50行的代码~~

实现

加入

我们需要模拟贝西的路线：

1、左转：在字符串中加入一个 $L$

2、左转：在字符串中加入一个 $R$

3、直走：加入这条边的长度

4、在 每次加入完成后加入一个空格 防止查找 $L 10$ 时找到 $L 1005$

void add (string &s , int x) {
    if (x == 1) s += 'T';
    else if (a[x].lr) s += 'R';
    else s += 'L';
    string s1;
    int tmp = a[x].len;
    while (tmp) s1 += char ((tmp % 10) + 48) , tmp /= 10;
    reverse (s1.begin() , s1.end());
    s += s1 , s += ' ';
}

查找

要加上这条边后面的方向

int query (string &a , string b , const char c) {
    b += c;
    size_t pos = 0;
    int sum = 0;
    while ((pos = a.find (b , pos)) != string :: npos) ++sum , ++ pos;
    return sum; 
}

统计答案

void solve (int x) {
    string s1;
    int sum = 0;
    fu (i , x , n) {
        if (query (s , s1 , a[i].lr ? 'R' : 'L') == 1) {
            // cout << i << " ";
            ans = max (ans , abs (dis[x] - (sum + dis[i])));
            return;
        }
        add (s1 , i) , sum += a[i].len;
    }
}

数据读入

自己看代码解释就好了

~~虽然不多~~

void pre () {
    /*a[i].lr: 0->左转，1->右转*/
    /*a[i].dir: 1->东，2->南,3->西,4->北*/
    fu (i , 2 , n + 1) {
        if (re[i].x == re[i - 1].x) {
            tot += (a[i - 1].len = abs (re[i].y - re[i - 1].y));
            if (re[i].y > re[i - 1].y) {
                a[i - 1].dir = 4;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 1) a[i - 1].lr = 0;
                else a[i - 1].lr = 1;
            }
            else {
                a[i - 1].dir = 2;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 1) a[i - 1].lr = 1;
                else a[i - 1].lr = 0;
            }
        }
        else {
            tot += (a[i - 1].len = abs (re[i].x - re[i - 1].x));
            if (re[i].x > re[i - 1].x) {
                a[i - 1].dir = 1;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 2) a[i - 1].lr = 0;
                else a[i - 1].lr = 1;
            }
            else {
                a[i - 1].dir = 3;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 2) a[i - 1].lr = 1;
                else a[i - 1].lr = 0;
            }
        }
    }
}

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 205;
int tot , ans = -10000000;
struct re {
    int x , y;
} re[N];
struct node {
    int len , dir;
    bool lr;
} a[N];
int n , dis[N];
string s;
int read () {
    int val = 0 , fu = 1;
    char ch = getchar ();
    while (ch > '9' || ch < '0') {
        if (ch == '-') fu = -1;
        ch = getchar ();
    }
    while (ch <= '9' && ch >= '0') {
        val = val * 10 + (ch - '0');
        ch = getchar ();
    }
    return val * fu;
}
void pre () {
    /*a[i].lr: 0->左转，1->右转*/
    /*a[i].dir: 1->东，2->南,3->西,4->北*/
    fu (i , 2 , n + 1) {
        if (re[i].x == re[i - 1].x) {
            tot += (a[i - 1].len = abs (re[i].y - re[i - 1].y));
            if (re[i].y > re[i - 1].y) {
                a[i - 1].dir = 4;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 1) a[i - 1].lr = 0;
                else a[i - 1].lr = 1;
            }
            else {
                a[i - 1].dir = 2;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 1) a[i - 1].lr = 1;
                else a[i - 1].lr = 0;
            }
        }
        else {
            tot += (a[i - 1].len = abs (re[i].x - re[i - 1].x));
            if (re[i].x > re[i - 1].x) {
                a[i - 1].dir = 1;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 2) a[i - 1].lr = 0;
                else a[i - 1].lr = 1;
            }
            else {
                a[i - 1].dir = 3;
                if (!a[i - 2].dir) continue;
                if (a[i - 2].dir == 2) a[i - 1].lr = 1;
                else a[i - 1].lr = 0;
            }
        }
    }
}
void add (string &s , int x) {
    if (x == 1) s += 'T';
    else if (a[x].lr) s += 'R';
    else s += 'L';
    string s1;
    int tmp = a[x].len;
    while (tmp) s1 += char ((tmp % 10) + 48) , tmp /= 10;
    reverse (s1.begin() , s1.end());
    s += s1 , s += ' ';
}
void init () {
    fu (i , 1 , n) add (s , i);
    for (int sum = 0 , i = 1 ; i <= n ; i ++) dis[i] = min (tot - sum , sum) , sum += a[i].len;
}
int query (string &a , string b , const char c) {
    b += c;
    size_t pos = 0;
    int sum = 0;
    while ((pos = a.find (b , pos)) != string :: npos) ++sum , ++ pos;
    return sum; 
}
void solve (int x) {
    string s1;
    int sum = 0;
    fu (i , x , n) {
        if (query (s , s1 , a[i].lr ? 'R' : 'L') == 1) {
            // cout << i << " ";
            ans = max (ans , abs (dis[x] - (sum + dis[i])));
            return;
        }
        add (s1 , i) , sum += a[i].len;
    }
}
int main () {
    n = read ();
    fu (i , 1 , n) re[i].x = read () , re[i].y = read ();
    re[n + 1].x = re[1].x , re[n + 1].y = re[1].y;
    pre ();
    init ();
    fu (i , 2 , n) solve (i); 
    printf ("%d" , ans);
    return 0;
}