【BZOJ2789】[Poi2012]Letters 树状数组
数组 树状
2023-09-11 14:15:27 时间
【BZOJ2789】[Poi2012]Letters
Description
给出两个长度相同且由大写英文字母组成的字符串A、B,保证A和B中每种字母出现的次数相同。
现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B。
Input
第一行一个正整数n (2<=n<=1,000,000),表示字符串的长度。
第二行和第三行各一个长度为n的字符串,并且只包含大写英文字母。
Output
一个非负整数,表示最少的交换次数。
Sample Input
3
ABC
BCA
ABC
BCA
Sample Output
2
HINT
ABC -> BAC -> BCA
题解:首先对于B中的第一个字符,我们一定是贪心的选择A中最左边一个与它相同的字符移过来,并且移过来的过程中,其它字符的相对顺序不发生改变。所以我们只需要用树状数组维护每个字符被移动的距离,然后继续做下去即可。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int maxn=1000010; int n; long long ans; char A[maxn],B[maxn]; int s[maxn],st[26][maxn],tp[26]; void updata(int x,int v) { for(int i=x;i<=n;i+=i&-i) s[i]+=v; } int query(int x) { int ret=0,i; for(i=x;i;i-=i&-i) ret+=s[i]; return ret; } int main() { scanf("%d%s%s",&n,A+1,B+1); int i,u; for(i=n;i>=1;i--) st[A[i]-'A'][++tp[A[i]-'A']]=i; for(i=1;i<=n;i++) { u=st[B[i]-'A'][tp[B[i]-'A']--]; ans+=query(u)+u-i,updata(1,1),updata(u,-1); } printf("%lld",ans); return 0; }
相关文章
- hdu4911 简单树状数组
- SGU180:Inversions(树状数组)
- 二维树状数组的区间加减及查询 tyvj 1716 上帝造题的七分钟
- 算法 - 求一个数组的最长递减子序列(C++)
- Java 数据结构(链表LinkedList增删改查、数组Vector、获取Vector最大值、交换Vector两成员位置、栈的实现、压栈出栈实现反转、队列Queue)
- 【BZOJ3413】匹配 离线+后缀树+树状数组
- 【BZOJ4384】[POI2015]Trzy wieże 树状数组
- 【BZOJ4538】[Hnoi2016]网络 整体二分+树状数组
- 【BZOJ2762】[JLOI2011]不等式组 树状数组
- 【BZOJ2422】Times 树状数组
- 【BZOJ1146】[CTSC2008]网络管理Network 树状数组+DFS序+主席树
- 【BZOJ4881】5月月赛D 线段游戏 树状数组+set
- 树状数组 1/30
- JavaScript - 一维数组 / 二维数组根据指定的对象属性获取该对象在数组中的下标(对数组进行增删还要确定该项位置)
- js实现字符串分割为数组类型(必须是数组格式)
- Arrays.toString(a)--->将数组a的值转换为字符串
- 剑指offer编程题解法汇总30-连续子数组的最大和
- 力扣解法汇总532-数组中的 k-diff 数对
- 循环队列(数组实现)
- php获取并删除数组的第一个和最后一个元素
- 60、【数组】leetcode——904. 水果成篮-滑动窗口:最大窗口(C++版本)
- 洛谷 P3374 【模板】树状数组 1
- 指针数组和数组指针
- Codeforces Round #248 (Div. 2) B称号 【数据结构:树状数组】
- C#查询数组中是否存在某元素(转载)
- java set转list,数组与list的转换
- 【bzoj4994】[Usaco2017 Feb]Why Did the Cow Cross the Road III 树状数组
- 【bzoj2384】[Ceoi2011]Match 特殊匹配条件的KMP+树状数组
- 【bzoj2141】排队 分块+树状数组
- [Python] 判断数组是否存在重复元素