傳送門
文章目錄
題意：
給你一個串，你可以隨意安排這個串，使得這個串的每個前綴的kmpkmpkmp數組最大值最小，定義為f(a)f(a)f(a)，并且字典序最小，輸出安排之后的串。
n≤1e5n\le1e5n≤1e5
思路：
這個題就是個惡心的分情況討論題，直接分情況吧。
(1)(1)(1)全是一個字母的時候，直接輸出即可。
(2)(2)(2)有一個字母只有一個的時候，可以將最小的放在前面，其他的都依次接在他后面即可，這個時候f(a)f(a)f(a)為000，字典序最小。
(3)(3)(3)當有兩個字母的時候，這個時候f(a)f(a)f(a)最少為111，我們就貪心的從頭開始向后填字母，可以發現aabababaaabababaaabababa這樣是最優的，如果再多一個aaa的話顯然不能這么填了。所以當cnt2>=cnt1?2cnt2>=cnt1-2cnt2>=cnt1?2的時候，即可以用bbb抵消掉多余的aaa的時候，就可以這樣填來消除。否則為了使f(a)f(a)f(a)盡可能小，只能abbbbbaaaaabbbbbaaaaabbbbbaaaa這樣填。
(4)(4)(4)當有三個字母的時候，依舊采取上面的思想，類似于這樣填aababacadaaababacadaaababacada，也就是說如果除了aaa之外的字母n?cnt>=cnt?2n-cnt>=cnt-2n?cnt>=cnt?2的話，就是可以這樣填的，可知這樣字典序最小，且f(a)=1f(a)=1f(a)=1。否則的話，因為有三個，所以可以這樣填abaaaaaacbabaaaaaacbabaaaaaacb，最后用ccc將其隔開，防止填bbb使得f(a)=2f(a)=2f(a)=2。
最后分情況實現一下就好啦，由于把XXX寫成YYY還漏了第二種情況調了半天，真的是越來越不適合敲代碼了。。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
char s
[N
];
int ne
[N
];
string ans
;
int c
[30];
vector
<pair
<int,char> >v
;void solve() {for(auto x
:v
) {for(int i
=0;i
<x
.X
;i
++) ans
+=x
.Y
;}
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {for(int i
=0;i
<26;i
++) c
[i
]=0;scanf("%s",s
+1); n
=strlen(s
+1);ans
=""; v
.clear();for(int i
=1;i
<=n
;i
++) c
[s
[i
]-'a']++;int flag
=false; int id
=-1;for(int i
=0;i
<26;i
++) if(c
[i
]) {v
.pb({c
[i
],i
+'a'});if(c
[i
]==1&&id
==-1) id
=(int)v
.size()-1; }if(id
!=-1) {ans
+=v
[id
].Y
; v
[id
].X
=0;solve();}else if(v
.size()==1) {for(int i
=0;i
<v
[0].X
;i
++) ans
+=v
[0].Y
;} else if(v
.size()==2) {int cnt1
=v
[0].X
,cnt2
=v
[1].X
;char ch1
=v
[0].Y
,ch2
=v
[1].Y
;if(cnt1
==1) {ans
+=ch1
;while(cnt2
) cnt2
--,ans
+=ch2
;} else {if(cnt2
>=cnt1
-2) {ans
+=ch1
; ans
+=ch1
;cnt1
-=2;int cnt
=min(cnt1
,cnt2
);cnt1
-=cnt
; cnt2
-=cnt
;while(cnt
) cnt
--,ans
+=ch2
,ans
+=ch1
;assert(cnt1
==0);while(cnt1
) ans
+=ch1
,cnt1
--;while(cnt2
) ans
+=ch2
,cnt2
--;} else {cnt1
--; ans
+=ch1
;while(cnt2
) ans
+=ch2
,cnt2
--;while(cnt1
) ans
+=ch1
,cnt1
--;}}} else {int cnt
=v
[0].X
; char ch
=v
[0].Y
;if(cnt
<=2) {while(cnt
) cnt
--,ans
+=ch
;v
[0].X
=0;solve();} else if(cnt
==3) {v
[0].X
=0;ans
+=ch
; ans
+=ch
;ans
+=v
[1].Y
; v
[1].X
--;ans
+=ch
;solve();} else {v
[0].X
=0;if(cnt
-2<=n
-cnt
) {vector
<char>all
;for(auto x
:v
) { for(int i
=0;i
<x
.X
;i
++) all
.pb(x
.Y
);}ans
+=ch
; ans
+=ch
; cnt
-=2;for(auto x
:all
) {ans
+=x
;if(cnt
) cnt
--,ans
+=ch
;}} else {ans
+=ch
; ans
+=v
[1].Y
; v
[1].X
--;cnt
--;while(cnt
) ans
+=ch
,cnt
--;ans
+=v
[2].Y
; v
[2].X
--;solve();}}}cout
<<ans
<<endl
;}return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #733 (Div. 1 + Div. 2) E. Minimax 分情况讨论 + 思维的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
