中铁建设集团有限公司门户网站,凉山州建设银行官方网站,wordpress文章页调用分类列表,创新 反腐倡廉网站建设传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个串#xff0c;你可以随意安排这个串#xff0c;使得这个串的每个前缀的kmpkmpkmp数组最大值最小#xff0c;定义为f(a)f(a)f(a)#xff0c;并且字典序最小#xff0c;输出安排之后的串。 n≤1e…传送门
文章目录题意思路题意
给你一个串你可以随意安排这个串使得这个串的每个前缀的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的话显然不能这么填了。所以当cnt2cnt1−2cnt2cnt1-2cnt2cnt1−2的时候即可以用bbb抵消掉多余的aaa的时候就可以这样填来消除。否则为了使f(a)f(a)f(a)尽可能小只能abbbbbaaaaabbbbbaaaaabbbbbaaaa这样填。 (4)(4)(4)当有三个字母的时候依旧采取上面的思想类似于这样填aababacadaaababacadaaababacada也就是说如果除了aaa之外的字母n−cntcnt−2n-cntcnt-2n−cntcnt−2的话就是可以这样填的可知这样字典序最小且f(a)1f(a)1f(a)1。否则的话因为有三个所以可以这样填abaaaaaacbabaaaaaacbabaaaaaacb最后用ccc将其隔开防止填bbb使得f(a)2f(a)2f(a)2。 最后分情况实现一下就好啦由于把XXX写成YYY还漏了第二种情况调了半天真的是越来越不适合敲代码了。。
// Problem: E. Minimax
// Contest: Codeforces - Codeforces Round #733 (Div. 1 Div. 2, based on VK Cup 2021 - Elimination (Engine))
// URL: https://codeforces.com/contest/1530/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
char s[N];
int ne[N];
string ans;
int c[30];
vectorpairint,char v;void solve() {for(auto x:v) {for(int i0;ix.X;i) ansx.Y;}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--) {for(int i0;i26;i) c[i]0;scanf(%s,s1); nstrlen(s1);ans; v.clear();for(int i1;in;i) c[s[i]-a];int flagfalse; int id-1;for(int i0;i26;i) if(c[i]) {v.pb({c[i],ia});if(c[i]1id-1) id(int)v.size()-1; }if(id!-1) {ansv[id].Y; v[id].X0;solve();}else if(v.size()1) {for(int i0;iv[0].X;i) ansv[0].Y;} else if(v.size()2) {int cnt1v[0].X,cnt2v[1].X;char ch1v[0].Y,ch2v[1].Y;if(cnt11) {ansch1;while(cnt2) cnt2--,ansch2;} else {if(cnt2cnt1-2) {ansch1; ansch1;cnt1-2;int cntmin(cnt1,cnt2);cnt1-cnt; cnt2-cnt;while(cnt) cnt--,ansch2,ansch1;assert(cnt10);while(cnt1) ansch1,cnt1--;while(cnt2) ansch2,cnt2--;} else {cnt1--; ansch1;while(cnt2) ansch2,cnt2--;while(cnt1) ansch1,cnt1--;}}} else {int cntv[0].X; char chv[0].Y;if(cnt2) {while(cnt) cnt--,ansch;v[0].X0;solve();} else if(cnt3) {v[0].X0;ansch; ansch;ansv[1].Y; v[1].X--;ansch;solve();} else {v[0].X0;if(cnt-2n-cnt) {vectorcharall;for(auto x:v) { for(int i0;ix.X;i) all.pb(x.Y);}ansch; ansch; cnt-2;for(auto x:all) {ansx;if(cnt) cnt--,ansch;}} else {ansch; ansv[1].Y; v[1].X--;cnt--;while(cnt) ansch,cnt--;ansv[2].Y; v[2].X--;solve();}}}coutansendl;}return 0;
}
/**/
