题目链接

工艺

Description

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

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

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

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

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

Input

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

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

Output

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

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

1 10 9 8 7 6 5 4 3 2

Hint

【数据规模与约定】

对于 的数据,

对于 的数据,

对于 的数据,

题解

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

最小表示法板子题(

断链为环 断环为链

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

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

最小表示法代码:

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