自己做网站优化,韩国外贸平台,莱芜人才网最新招聘,无锡网站制作哪家公司好CF1526 D. Kill Anton
题意#xff1a;
给你一个由’A’,‘N’.‘T’,O’四个字符组成的字符串b#xff0c;现在要求你改变b的顺序得到a#xff0c;使得a通过移动回到b的步数最多。 每次移动只能移动相邻两项
题解#xff1a;
官方题解说#xff1a;最佳情况为相同字符…CF1526 D. Kill Anton
题意
给你一个由’A’,‘N’.‘T’,O’四个字符组成的字符串b现在要求你改变b的顺序得到a使得a通过移动回到b的步数最多。 每次移动只能移动相邻两项
题解
官方题解说最佳情况为相同字符靠在一起 证明我也不清楚。。 证明可以看看这篇文章 按照官方题解的说法将相同的字符排列在一起一共就四种字符那么也就是排列方式一共就24种4我们直接暴力求出每种情况然后求出其要移动的步数取最大值 这个移动的步数咋求 假设原先字符串是ANTON下标依次是12345现在我们将其打乱成ATONN原先的下标就成了13425那13425变回12345的步骤不就是其逆序对吗所以对于每一种情况我们求其逆序对然后保留最大值
这题挺好~
代码
#include bits/stdc.h
#define ll long long
using namespace std;
int a[50];//记录字符个数
vectorintid[50],c;//记录字符
string s;ll nxt;
void msort(int l,int r){//归并排序 if(lr)return;//区间元素小于1 int midlr1;msort(l,mid);//分 msort(mid1,r);//分 int il,jmid1,k0;int t[r-l1];while(imidjr){if(c[i]c[j])t[k]c[i]; else{//此时存在逆序对在归并过程中记录逆序对的个数 t[k]c[j];nxtmid-i1;//记录逆序对数 }}while(imid)t[k]c[i];while(jr)t[k]c[j];for(il,k0;ir;i,k)c[i]t[k];//将t排好序的数复制到c中
}
int main()
{ios_base::sync_with_stdio(false);int t;cint;while(t--){int r[5]{0,A,N,O,T};//通过函数枚举各种可能性 memset(a,0,sizeof(a));//清空 id[A-A].clear();id[N-A].clear();id[O-A].clear();id[T-A].clear();cins;for(int i0;is.size();i){a[s[i]-A];//记录每个字母的个数 id[s[i]-A].push_back(i1); }ll ans0;string as;do{c.clear();nxt0;//清零记录下一种情况的操作数for(int i1;i4;i){//四个字符分别连续存入形成一个新的字符串 c.insert(c.end(),id[r[i]-A].begin(),id[r[i]-A].end());}/*coutc ;for(int i0;ic.size();i)couts[c[i]-1];coutendl; */msort(0,c.size()-1);if(nxtans){ansnxt;as;for(int i1;i4;i) asstring(a[r[i]-A],(char)r[i]);//存入此时的最优字符串即前面c的原串 }}while(next_permutation(r1,r5));//对四个字符全排列的各种可能性 if(ans!0)coutasendl;else coutsendl;//ans为0说明原字符串已经为最优解 } return 0;
}
我还有看到一种写法本质一样它将转化后的字符串下标定为1234…,根据这个将原字符串下标定义为nxt[j]然后跑逆序对一样的
for(int i0;ilen;i){//将该情况的字符串转为数字 for(int j0;j3;j){if(mp[s[i]]nxt[j]){//每次打乱nxt c[i]j;break;}}}#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//qdu打铁匠
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn2e59;
int nxt[]{0,1,2,3};
ll a[maxn];
ll c[maxn],b[maxn];
mapchar,intmp;
ll cnt0;
void unite(int l,int mid,int r){if(lr)return ;unite(l,(lmid)1,mid);unite(mid1,(mid1r)1,r);int il,jmid1;for(ll kl;kr;k){if(jr||imidc[i]c[j]) b[k]c[i];else b[k]c[j],cntmid-i1;}for(ll kl;kr;k) c[k]b[k];
}
string s;
ll cal(int len){for(int i0;ilen;i){//将该情况的字符串转为数字 for(int j0;j3;j){if(mp[s[i]]nxt[j]){//每次打乱nxt c[i]j;break;}}}cnt0;unite(0,(len-1)1,len-1);//求逆序对 return cnt;
}
void solve(){cins;string a,n,o,t;for(int i0;is.length();i){if(s[i]A)aA;if(s[i]N)nN; if(s[i]O)oO;if(s[i]T)tT;}string anss;ll sum0;do{ll nowcal(s.size());if(nowsum){//得到更大的逆序对即需要步数更多 sumnow;ans.clear();for(int i0;i3;i){if(nxt[i]0)ansa;if(nxt[i]1)ansn;if(nxt[i]2)anst;if(nxt[i]3)anso;} }}while(next_permutation(nxt,nxt13));coutansendl;
}
int main()
{int tread();mp[A]0;mp[N]1;mp[T]2;mp[O]3;while(t--){solve();}
}
