BZOJ1100【POI2007】对称轴osi < Manacher >

Posted on Symbols count in article: 844 Reading time ≈ 3 mins.

Problem

【POI2007】对称轴osi

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

FGD\mathrm{FGD}小朋友——一个闻名遐迩的年轻数学家——有一个小MM，yours\mathrm{yours}。FGD\mathrm{FGD}小朋友非常喜欢他的MM，所以他很乐意帮助他的MM做数学作业。但是，就像所有科学的容器一样，FGD的大脑拒绝不停地重复思考同样的问题。不幸的是，yours\mathrm{yours}是一个十分用功的学生，所以她不停地让FGD\mathrm{FGD}帮助她检查她的作业。
一个阳光明媚的周末，yours\mathrm{yours}的数学老师布置了非常多的寻找多边形的对称轴的题，足够她做相当长的一段时间了。在此之前FGD\mathrm{FGD}已经决定去海边度过这个难得的假期，不过他还是觉得应该帮助他的MM对付可爱的数学作业。很快地，他找到了解决方案，最好写一个程序来帮助yours\mathrm{yours}检查她的数学作业。
因为FGD\mathrm{FGD}并非一个计算机科学家，所以他找到了他的好朋友你，请你帮助他完成这个任务。
请写一个程序：读入多边形的描述计算出每个多边形的对称轴数将计算的结果输出。

Input

输入的第一行包含一个正整数T  (1≤T≤10)T\;(1\le T\le10)，为多边形的边数。
接下来，为TT个多边形的描述。
每个描述的第一行为一个正整数n  (3≤n≤105)n\;(3\le n\le10^5)，表示了多边形的点数。
后面nn行每行两个整数xx和y  (−108≤x,y≤108)y\;(-10^8\le x, y\le10^8)，依次表示多边形的顶点坐标。
多边形不一定是凸的，但是不自交。任何两条边都只有最多一个公共点，即它们的公共端点。此外，没有两条连续的边平行。

Output

你的程序应该输出正好TT行，第k行包含了一个整数nkn_k——表示第kk个多边形有多少个对称轴。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
12
1 -1
2 -1
2 1
1 1
1 2
-1 2
-1 1
-2 1
-2 -1
-1 -1
-1 -2
1 -2
6
-1 1
-2 0
-1 -1
1 -1
2 0
1 1

Sample Output

1
2
4
2

标签：Manacher

Solution

Manacher\mathrm{Manacher}好题。

如果我们确定一个多边形的每条边和每个角，我们就确定了这个多边形。那么半个多边形呢？也是一样的。
我们将nn边形写成长为2n2n的数组，即每条边的长度和两边夹角的叉积交错排列。将这个数组看成一个环，对称意味着这个环关于某个位置对称。按常理断环成链后跑Manacher\mathrm{Manacher}，过程中判每个位置的回文半径是否大于nn即可。

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
#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, nxt[MAX_N+5], s[MAX_N+5]; bool mrk[26];
int main() {
    read(n);
    for (int i = 0; i < n; i++) read(nxt[i]), nxt[i] = i-nxt[i];
    for (int p = 1; p < n; p++) {
        if (~nxt[p]) s[p] = s[nxt[p]];
        else {
            memset(mrk, false, sizeof mrk);
            for (int q = nxt[p-1]; ~q; q = nxt[q])
                mrk[s[q+1]] = true;
            for (int c = 1; c < 26; c++)
                if (!mrk[c]) {s[p] = c; break;}
        }
    }
    for (int i = 0; i < n; i++) printf("%c", 'a'+s[i]);
    return 0;
}