P2870 [USACO07DEC]Best Cow Line G

題意：

給你一個字符串，每次從首或尾取一個字符組成字符串，問所有能夠組成的字符串中字典序最小的一個。

題解：

現(xiàn)在要組成字典序最小的，那我們每次就盡可能取小的
我們從兩端開始，如果有一端小，那肯定選小的一段。如果兩端一樣大，此時我們要考慮這兩端后面的影響，我們要盡可能選后面較小的，比如圖中藍色一樣，但是紫色比橙色小，那我們兩端優(yōu)先取右側(cè)藍色，因為這樣可以保證后面取得小

那么如何比較兩端這個大小，我們可以將字符串翻轉(zhuǎn)一倍，這樣就相當于比兩個后綴的rank，跑個后綴數(shù)組就行

代碼：

// Problem: P2870 [USACO07DEC]Best Cow Line G // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P2870 // Memory Limit: 250 MB // Time Limit: 1500 ms // Data:2021-08-22 11:41:01 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef LOCALstartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef LOCALendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int N= 1000010;char s[N]; int n, sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N]; char ans[N]; bool cmp(int x, int y, int w) {return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]; }int main() {int i, m= 300, p, w;int t;read(t);//char ch= getchar();for (int i= 1; i <= t; i++) {scanf("%c", &s[i]);char ch= getchar();} // for (int i= 1; i <= t; i++) { // printf("s[i]=%c\n", s[i]); // }int len= t; for (int i= 1; i <= len; i++) {s[i + len]= s[len - i + 1];} // for (int i= 1; i <= 2*t; i++) { // printf("s[i]=%c\n", s[i]); // }n= 2*t;for (i= 1; i <= n; ++i)++cnt[rk[i]= s[i]];for (i= 1; i <= m; ++i)cnt[i]+= cnt[i - 1];for (i= n; i >= 1; --i)sa[cnt[rk[i]]--]= i;for (w= 1; w < n; w<<= 1, m= p) { // m=p 就是優(yōu)化計數(shù)排序值域for (p= 0, i= n; i > n - w; --i)id[++p]= i;for (i= 1; i <= n; ++i)if (sa[i] > w)id[++p]= sa[i] - w;memset(cnt, 0, sizeof(cnt));for (i= 1; i <= n; ++i)++cnt[px[i]= rk[id[i]]];for (i= 1; i <= m; ++i)cnt[i]+= cnt[i - 1];for (i= n; i >= 1; --i)sa[cnt[px[i]]--]= id[i];memcpy(oldrk, rk, sizeof(rk));for (p= 0, i= 1; i <= n; ++i)rk[sa[i]]= cmp(sa[i], sa[i - 1], w) ? p : ++p;} // for (int i= 1; i <= n; i++) // printf("sa[i]=%d", sa[i]);int l= 1, r= t;int tot= 0;while (l <= r) {if (rk[l] < rk[len + (len - r) + 1])cout << s[l++];elsecout << s[r--];tot++;if (tot % 80 == 0)printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P2870 [USACO07DEC]Best Cow Line G的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。