網(wǎng)站建設(shè)說辭神馬推廣
【模板】最小表示法
題目描述
小敏和小燕是一對好朋友。
他們正在玩一種神奇的游戲,叫 Minecraft。
他們現(xiàn)在要做一個由方塊構(gòu)成的長條工藝品。但是方塊現(xiàn)在是亂的,而且由于機器的要求,他們只能做到把這個工藝品最左邊的方塊放到最右邊。
他們想,在僅這一個操作下,最漂亮的工藝品能多漂亮。
兩個工藝品美觀的比較方法是,從頭開始比較,如果第 iii 個位置上方塊不一樣那么誰的瑕疵度小,那么誰就更漂亮,如果一樣那么繼續(xù)比較第 i+1i+1i+1 個方塊。如果全都一樣,那么這兩個工藝品就一樣漂亮。
輸入格式
第一行一個整數(shù) nnn,代表方塊的數(shù)目。
第二行 nnn 個整數(shù),每個整數(shù)按從左到右的順序輸出方塊瑕疵度的值。
輸出格式
一行 nnn 個整數(shù),代表最美觀工藝品從左到右瑕疵度的值。
樣例 #1
樣例輸入 #1
10
10 9 8 7 6 5 4 3 2 1
樣例輸出 #1
1 10 9 8 7 6 5 4 3 2
提示
- 對于 20%20\%20% 的數(shù)據(jù),n≤1000n\le 1000n≤1000;
- 對于 40%40\%40% 的數(shù)據(jù),n≤104n\le 10^4n≤104;
- 對于 100%100\%100% 的數(shù)據(jù),n≤3×105n\le 3\times 10^5n≤3×105。
題意:
雖然題目給定的是個數(shù)組,但我們可以把問題抽象成:給定一個長度為 n 的字符串 s,找出字典序最小的循環(huán)移位(長度也為 n)。以下的分析我們均用 “串” 來代替數(shù)組。
思路:
SAM 高度壓縮了原串各種長度的所有子串。我們發(fā)現(xiàn):字符串 s + s 包含 s 的所有循環(huán)移位作為子串。所以如果要找字典序的最小循環(huán)移位,不妨將原串復(fù)制一份,形成一個長度為 2n 的串,選擇所有長度為 n 的子串集合中字典序最小的那個。
我們對長度為 2n 的新串構(gòu)建后綴自動機,從DAG的根節(jié)點開始,每次貪心的走字典序最小的節(jié)點,走 n 步,邊走邊輸出即可。
時間復(fù)雜度:O(n)O(n)O(n)
代碼:
#include<bits/stdc++.h>using namespace std;const int N = 6e5 + 10, M = N << 1;
int n, a[N], len[M], fa[M], np = 1, tot = 1;
map<int, int> ch[M];
vector<int> g[M];void extend(int c)
{int p = np; np = ++tot;len[np] = len[p] + 1;while (p && !ch[p][c]) {ch[p][c] = np;p = fa[p];}if (!p) {fa[np] = 1;}else {int q = ch[p][c];if (len[q] == len[p] + 1) {fa[np] = q;}else {int nq = ++tot;len[nq] = len[p] + 1;fa[nq] = fa[q], fa[q] = fa[np] = nq;while (p && ch[p][c] == q) {ch[p][c] = nq;p = fa[p];}ch[nq] = ch[q];}}
}signed main()
{scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);a[i + n] = a[i];}n <<= 1;for (int i = 0; i < n; ++i) {extend(a[i]);}int p = 1;for (int i = 0; i < n / 2; ++i) {auto pp = ch[p].begin(); //由于map自動按第一關(guān)鍵字排序,因此每次貪心地選擇首元素走就行int ele = (*pp).first;int nd = (*pp).second;printf("%d ", ele);p = nd;}puts("");return 0;
}