Letters bzoj-2789 Poi-2012

题目大意:给定两个字符串A和B,每次交换A中相邻两个数。问至少交换多少次,可以将A变成B。

注释:$2\le n\le 10^6$

想法:我们发现,A中任意两个相同字符的相对位置是不会发生改变的,所以我们可以直接求逆序对即可。

最后,附上丑陋的代码... ...

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1000005;
vector <int> wz[26];
int sum[N],ss,n,x,len[26],now;
char s1[N],s2[N];
long long ans;
void add(int i){for (;i<=n;i+=(i&(-i)))sum[i]++;}
int query(int i){for (ss=0;i;i-=(i&(-i)))ss+=sum[i];return ss;}
int main (){
scanf ("%d%s%s",&n,s1+1,s2+1);
for (int i=1;i<=n;++i)wz[s1[i]-'A'].push_back(i);
for (int i=1;i<=n;++i){
add(now=wz[s2[i]-'A'][len[s2[i]-'A']++]);
ans+=i-query(now);
}
printf ("%lld",ans);
return 0;
}

小结:发现性质,并利用性质转化成已知问题,是一种非常好的解题方法。

最新文章

  1. 【小白的CFD之旅】08 CFD速成之道
  2. 19-ES6(2)
  3. 4.1 pair类模板
  4. win7系统cmd命令切换到指定文件夹目录
  5. sql注入实例分析
  6. Stanford机器学习---第五讲. 神经网络的学习 Neural Networks learning
  7. oracle查锁表SQL
  8. C#winform设置DateTimePicker的时间格式
  9. Linq基本用法
  10. Php ORM 对象关系映射
  11. Password
  12. postman 第6节录制case
  13. 《程序员修炼之道:从小工到专家》【PDF】下载
  14. Spring boot整合Mybatis
  15. 距离不是一个连续的物理量(Distance is not a continuous physical quantity)
  16. Tomcat延迟启动
  17. poj 3694 Network 【Tarjan】+【LCA】
  18. MySQL 5.6新特性 -- Index Condition Pushdown
  19. OS X - 在80端口启动Nginx
  20. JDK(Java SE Development Kit)的安装与环境变量的配置

热门文章

  1. 背包问题的方案总数 P1474 货币系统
  2. poi读取docx中的文字和图片(自己应用)
  3. 洛谷 P1032 [ NOIP 2002 ] 字串变换 —— 字符串+bfs
  4. SpringMVC使用POST方法传递数据,却出现Request method &#39;GET&#39; not supported?
  5. leetcode矩阵与动态规划相关
  6. leetcode数组相关
  7. scws
  8. selenium3 + python - gird分布式(转载)
  9. python--1、入门
  10. Net.Json 常用例子