「BZOJ 2882」工艺 - 最小表示法

Shq 又双叒叕在刷水题

题目链接

工艺

Description

小敏和小燕是一对好朋友。

他们正在玩一种神奇的游戏,叫Minecraft。

他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的,而且由于机器的要求,他们只能做到把这个工艺品最左边的方块放到最右边。

他们想,在仅这一个操作下,最漂亮的工艺品能多漂亮。

两个工艺品美观的比较方法是,从头开始比较,如果第 ii 个位置上方块不一样那么谁的瑕疵度小,那么谁就更漂亮,如果一样那么继续比较第 i+1i+1 个方块。如果全都一样,那么这两个工艺品就一样漂亮。

Input

第一行两个整数 nn,代表方块的数目。

第二行 nn 个整数,每个整数按从左到右的顺序输出方块瑕疵度的值。

Output

一行 nn 个整数,代表最美观工艺品从左到右瑕疵度的值。

Sample Input

1
2
10
10 9 8 7 6 5 4 3 2 1

Sample Output

1
1 10 9 8 7 6 5 4 3 2

Hint

【数据规模与约定】

对于 20%20\% 的数据,n103n\le 10^3

对于 40%40\% 的数据,n104n\le 10^4

对于 100%100\% 的数据,n3×105n\le3\times10^5

题解

题目大意: 求字典序最小的循环同构字符串

最小表示法板子题(

断链为环 断环为链

orz Shq 不会 SAM,只会用最小表示法

将串S连接成SS后建立SAM,每次找最小的儿子跑就好了 --Aufun

最小表示法代码:

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
const int MAXN = 300000 + 100;

int a[MAXN << 1];
int n;

inline int solve() {
int i = 0, j = 1, k = 0;
while (i < n && j < n && k < n) {
if (a[i + k] == a[j + k]) k++;
else {
if (a[i + k] > a[j + k]) i += k + 1;
else j += k + 1;
k = 0;
if (i == j) j++;
}
}
return std::min(i, j);
}

int main(int argc, char *argv[]) {
n = SlowRead();
up (i, 0, n - 1) a[i + n] = a[i] = SlowRead();
ll s = solve();
up (i, 0, n - 1) Print(a[i + s]), putchar(' ');
return 0;
}

Shq 又双叒叕氵了篇 Blog

坚持原创技术分享,您的支持将鼓励我继续创作!