CodeForces - 1526D Kill Anton(模拟)

题目链接：https://vjudge.net/problem/CodeForces-1526D

题目大意：给出一个只有四种字母组成的字符串 $A$，要求将其重排列 $B$，使得贡献最大。贡献指的是，每次可以交换相邻的两个字母，问从 $A$ 变成 $B$ 的最小操作次数

题目分析：猜的结论，就是相同的字母一定连续，具体证明可以参考官方题解

然后思维上就没什么难度了，剩下的就是如何 $O(n)$ 或者 $O(nlogn)$ 实现 $cal$ 函数用来计算两个字符串的贡献了

因为字符集比较小，而且还是连续的，所以我直接枚举 $B$ 串，每次去 $A$ 串从前往后扫，当一个 $B$ 串中一个字符用完之后，将 $A$ 串的游标置零再重新开始就可以了，常数是 $4$

就是实现的时候感觉蛮难调的

代码：

// Problem: D. Kill Anton // Contest: Codeforces - Codeforces Round #723 (Div. 2) // URL: https://codeforces.com/contest/1526/problem/D // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } 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'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int cnt[4],a[N]; char str[]="AOTN"; int get_id(char ch) {if(ch=='A') {return 0;} else if(ch=='O') {return 1;} else if(ch=='T') {return 2;} else {return 3;} } string s; bool ban[N]; LL check(string a) {LL ans=0;int pos=0;int cnt=1;for(int i=0;i<(int)a.size();i++) {if(i>0&&a[i]!=a[i-1]) {pos=0;cnt=!ban[pos];}while(s[pos]!=a[i]) {pos++;if(!ban[pos]) {cnt++;}}ban[pos]=true;ans+=cnt-1; while(ban[pos]) {pos++;}}return ans; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {memset(cnt,0,sizeof(cnt));cin>>s;for(auto it:s) {cnt[get_id(it)]++;}for(int i=0;i<4;i++) {a[i]=i;}LL mmax=-1;string ans;do {string ss;for(int i=0;i<4;i++) {for(int j=0;j<cnt[a[i]];j++) {ss+=str[a[i]];}}memset(ban,0,s.size()+5);LL tmp=check(ss);if(tmp>mmax) {mmax=tmp;ans=ss;}}while(next_permutation(a,a+4));cout<<ans<<endl;}return 0; } 超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的CodeForces - 1526D Kill Anton(模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。