[ POI 2012 ] Letters
2024-08-30 22:18:52
\(\\\)
\(Description\)
给出两个长度为 \(N\) 的字符串\(S_1,S_2\),且保证两个字符串中每一个字符出现次数相同。
现在一次操作可以交换相邻的两个字符,问将 \(S_2\) 变成 \(S_1\) 最少需要交换多少次。
- \(N\le 10^6\)
\(\\\)
\(Solution\)
假如一共出现了五个 \(A\) ,那一定是按照顺序移动,即\(S_2\)中第一个出现的 \(A\) 最后一定会移动到\(S_1\)中第一个出现的 \(A\) 处。
然后就是逐一匹配的问题了。
以第一个串每一个字符的位置做为权值绑在第二个串对应字符的位置上,相当于将第一个串的 \(id\) 按照第二个串的位置打乱再冒泡排序。
然后根据冒泡排序的原理,这个序列的逆序对数就是交换次数。
\(\\\)
\(Code\)
#include<cmath>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000010
#define R register
#define gc getchar
using namespace std;
typedef long long ll;
inline ll rd(){
ll x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
ll n,ans,s[N],ptr[30];
vector<int> p[30];
struct BIT{
ll c[N];
inline int lowbit(ll x){return x&-x;}
inline void add(ll p,ll x){for(;p<=N;p+=lowbit(p)) c[p]+=x;}
inline ll query(ll p){
ll res=0;
for(;p;p-=lowbit(p)) res+=c[p];
return res;
}
}bit;
int main(){
n=rd();
char c=gc();
for(R int i=1;i<=n;++i){
while(!isalpha(c)) c=gc();
p[c-'A'+1].push_back(i); c=gc();
}
for(R int i=1;i<=n;++i){
while(!isalpha(c)) c=gc();
s[i]=p[c-'A'+1][ptr[c-'A'+1]];
++ptr[c-'A'+1]; c=gc();
}
for(R int i=n;i;--i){
ans+=bit.query(s[i]);
bit.add(s[i],1);
}
printf("%lld\n",ans);
return 0;
}
最新文章
- 匹夫细说C#:庖丁解牛迭代器,那些藏在幕后的秘密
- BootStrap_02之全局样式及组件
- js的this上下文的坑
- 脚本改yum源
- 命令行导入mysql数据
- Python 之路 Day5 - 常用模块学习
- DIY(码表)制作实验
- 14. javacript高级程序设计-表单
- 碰到一个在app内部浏览器锚点异常的问题
- Codeforces Round #130 (Div. 2) C - Police Station 最短路+dp
- 封装鼠标滚轮事件_mousewheel
- 记录一下跟Python有关的几个拓展名
- fancybox的使用
- checkbox、select、radio的设置与获取
- [置顶]
 一个demo学会c#
- Java设计模式-责任链模式
- sqlplus 登录数据库
- 转载(略有修改):Windows 8的承载网络设置方法(w8 创建无线网络/ap)
- react-native中的style
- 关于Django启动创建测试库的问题
热门文章
- cogs 48. [NOIP2007] 字符串的展开
- oracle的processes和session最大限制
- 测试使用markdonw写博客
- spring,spring mvc之所以起作用是因为开启了注解解释器,即spring的annotation on
- 标准ACL、扩展ACL和命名ACL的配置详解
- Samba完整篇 ubuntu 10.04
- 使用Charles进行网络抓包
- LeetCode_Mysql_Second Highest Salary
- iOS 多线程,ARC
- Highcharts数据表示(3)