中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當前位置: 首頁 > news >正文

網(wǎng)站建設(shè)說辭神馬推廣

網(wǎng)站建設(shè)說辭,神馬推廣,鎮(zhèn)江丹陽怎么樣,網(wǎng)站建設(shè)確認書【模板】最小表示法 題目描述 小敏和小燕是一對好朋友。 他們正在玩一種神奇的游戲,叫 Minecraft。 他們現(xiàn)在要做一個由方塊構(gòu)成的長條工藝品。但是方塊現(xiàn)在是亂的,而且由于機器的要求,他們只能做到把這個工藝品最左邊的方塊放到最右邊?!?article class="baidu_pl">

【模板】最小表示法

題目描述

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

他們正在玩一種神奇的游戲,叫 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 1000n1000
  • 對于 40%40\%40% 的數(shù)據(jù),n≤104n\le 10^4n104
  • 對于 100%100\%100% 的數(shù)據(jù),n≤3×105n\le 3\times 10^5n3×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;
}
http://www.risenshineclean.com/news/54683.html

相關(guān)文章:

  • 網(wǎng)站備案局網(wǎng)絡(luò)營銷好不好
  • 免費企業(yè)網(wǎng)站源碼生成7個經(jīng)典軟文營銷案例
  • 設(shè)計優(yōu)秀的企業(yè)網(wǎng)站seo快速優(yōu)化
  • 0基礎(chǔ)學習網(wǎng)站開發(fā)網(wǎng)站模板購買
  • 肖鴻昌建筑網(wǎng)站寧波網(wǎng)絡(luò)營銷推廣公司
  • 網(wǎng)站開發(fā)端賺錢軟件
  • 網(wǎng)站建設(shè)空間步驟詳解搜索引擎優(yōu)化要考慮哪些方面?
  • 做網(wǎng)站和做推廣的區(qū)別四種營銷模式
  • 教育類網(wǎng)站框架網(wǎng)頁模板源代碼
  • 用別人網(wǎng)站做app的危害杭州網(wǎng)站
  • 上海網(wǎng)站制作平臺足球世界排名一覽表
  • wordpress軟件下載主題北海百度seo
  • 網(wǎng)站制作.com語言做網(wǎng)站公司哪家正規(guī)
  • 河南省專業(yè)做網(wǎng)站公司長沙專業(yè)競價優(yōu)化公司
  • 做餐飲的網(wǎng)站營銷推廣seo
  • 不會代碼怎么做網(wǎng)站免費網(wǎng)頁在線客服系統(tǒng)
  • 深圳做網(wǎng)站公廣東免費網(wǎng)絡(luò)推廣軟件
  • cc后綴網(wǎng)站長沙網(wǎng)站優(yōu)化效果
  • 沈陽制作網(wǎng)站的人做網(wǎng)頁用什么軟件好
  • 淘寶客網(wǎng)站建設(shè)教程西安seo公司
  • 自學python的網(wǎng)站電商代運營公司十強
  • 平面設(shè)計有什么網(wǎng)站女教師網(wǎng)課入06654侵錄屏
  • 電商網(wǎng)站運營方案百度優(yōu)化點擊軟件
  • 交友視頻網(wǎng)站建設(shè)網(wǎng)絡(luò)推廣靠譜嗎
  • 廣州英銘網(wǎng)站建設(shè)百度網(wǎng)盤官網(wǎng)下載
  • 企業(yè)網(wǎng)站建設(shè)公司司如何做好網(wǎng)絡(luò)銷售技巧
  • 企業(yè)網(wǎng)站建設(shè)優(yōu)化泉州百度競價推廣
  • jsp怎么做網(wǎng)站的刪除數(shù)字營銷服務(wù)商seo
  • 5年網(wǎng)站續(xù)費多少錢做銷售找客戶渠道
  • 濟源建設(shè)工程管理處網(wǎng)站網(wǎng)絡(luò)推廣員要怎么做