济南简单网站制作排名公司,淄博做网络推广的公司,郑州app开发多少钱,苏州建设交通招聘信息网站前言
我的证明#xff1a;这似乎非常对啊。 。。。
解析
直观感受#xff1a;字母交错出现非常愚蠢。 然后就猜对了
为什么#xff1f; 考虑两个相同但不相邻的字符 Ti,TjT_i,T_jTi,Tj#xff0c;对应位置为 pi,pjp_i,p_jpi,pj。 夹在中间的字符 kkk 无非三种可…前言
我的证明这似乎非常对啊。 。。。
解析
直观感受字母交错出现非常愚蠢。 然后就猜对了
为什么 考虑两个相同但不相邻的字符 Ti,TjT_i,T_jTi,Tj对应位置为 pi,pjp_i,p_jpi,pj。 夹在中间的字符 kkk 无非三种可能。 pipkpjp_ip_kp_jpipkpj此时无论是把i移到后面还是把j移到前面都会增加一个逆序对。pkpipjp_kp_ip_jpkpipj此时把j移到前面会增加一个逆序对把i移到后面会减少一个逆序对。pipjpkp_ip_jp_kpipjpk此时把i移到后面会增加一个逆序对把j移到前面会减少一个逆序对。 那么我们只需要讨论一下2、3两种情况那种更多按照对应策略操作就可以把 Ti,TjT_i,T_jTi,Tj 挪到一起且逆序对不减少。 证毕。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(ok\n)const int N1e5100;
const bool Flag1;inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
bool mem1;int n;
char s[N],ch[5],ans[N],tmp[N];
int cnt[5],sum[N][5];
int q[5],vis[5];
ll mx;
mapchar,intmp;
queueintqq[5];
int f[N];
inline void add(int p,int w){for(;pn;pp-p) f[p]w;return;
}
inline int ask(int p){int res(0);for(;p;p-p-p) resf[p];return res;
}
ll calc(){ll res(0);for(int i1;in;i){qq[mp[tmp[i]]].push(i);f[i]i-i;}for(int i1;in;i){int pqq[mp[s[i]]].front();qq[mp[s[i]]].pop();int posi-1ask(p);add(p,-1);respos-i;}return res;
}
void dfs(int k){if(k4){int num(0);for(int i1;i4;i){for(int j1;jcnt[q[i]];j) tmp[num]ch[q[i]];}//printf(%s\n,tmp1);ll ocalc();if(omx){mxo;memcpy(ans,tmp,sizeof(char)*(n1));}return;}for(int i1;i4;i){if(vis[i]) continue;vis[i]1;q[k]i;dfs(k1);vis[i]0;}return;
}void work(){scanf( %s,s1);nstrlen(s1);mx-1;memset(cnt,0,sizeof(cnt));for(int i1;in;i){cnt[mp[s[i]]];for(int j1;j4;j) sum[i][j]sum[i-1][j];sum[i][mp[s[i]]];}//scanf( %s,tmp1);//printf(tmp%lld\n,calc());dfs(1);for(int i1;in;i) putchar(ans[i]);puts(); //printf(mx%lld\n,mx);
}bool mem2;
signed main() {#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifch[1]A;ch[2]N;ch[3]O;ch[4]T;mp[A]1;mp[N]2;mp[O]3;mp[T]4;int Tread();while(T--) work();return 0;
}
