网站如何做淘宝推广,怎么制作免费网站教程视频,云南省建设培训网站,创业网站建设正题
题目大意:https://www.luogu.org/problem/P3531 题目大意
两个由相同字符组成的字符串#xff0c;每次可以交换相邻的两个字符#xff0c;求最少交换次数使这两个字符串相同。 解题思路
我们拿第二个字符在第一个字符串对应的位置作为值求逆序对数量即可。
注意的是…正题
题目大意:https://www.luogu.org/problem/P3531 题目大意
两个由相同字符组成的字符串每次可以交换相邻的两个字符求最少交换次数使这两个字符串相同。 解题思路
我们拿第二个字符在第一个字符串对应的位置作为值求逆序对数量即可。
注意的是两个相同的使前面的对前面后面的对后面。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
#define ll long long
using namespace std;
const ll N1e610;
ll n,local[27],last[N],num[N],t[N],ans;
char a[N],b[N];
void change(ll x,ll z)
{while(xn){t[x]z;xlowbit(x);}
}
ll ask(ll x)
{ll ans0;while(x){anst[x];x-lowbit(x);}return ans;
}
int main()
{scanf(%lld,n);scanf(%s,a1);scanf(%s,b1);for(ll i1;in;i){last[i]local[a[i]-A];local[a[i]-A]i;}for(ll in;i1;i--){num[i]n-local[b[i]-A]1;local[b[i]-A]last[local[b[i]-A]];}for(ll i1;in;i){ansask(num[i]);change(num[i],1);}printf(%lld,ans);
}
