[bzoj2789][Poi2012]Letters_树状数组
2024-08-31 05:00:32
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;
}
小结:发现性质,并利用性质转化成已知问题,是一种非常好的解题方法。
最新文章
- 【小白的CFD之旅】08 CFD速成之道
- 19-ES6(2)
- 4.1 pair类模板
- win7系统cmd命令切换到指定文件夹目录
- sql注入实例分析
- Stanford机器学习---第五讲. 神经网络的学习 Neural Networks learning
- oracle查锁表SQL
- C#winform设置DateTimePicker的时间格式
- Linq基本用法
- Php ORM 对象关系映射
- Password
- postman 第6节录制case
- 《程序员修炼之道:从小工到专家》【PDF】下载
- Spring boot整合Mybatis
- 距离不是一个连续的物理量(Distance is not a continuous physical quantity)
- Tomcat延迟启动
- poj 3694 Network 【Tarjan】+【LCA】
- MySQL 5.6新特性 -- Index Condition Pushdown
- OS X - 在80端口启动Nginx
- JDK(Java SE Development Kit)的安装与环境变量的配置
热门文章
- 背包问题的方案总数 P1474 货币系统
- poi读取docx中的文字和图片(自己应用)
- 洛谷 P1032 [ NOIP 2002 ] 字串变换 —— 字符串+bfs
- SpringMVC使用POST方法传递数据,却出现Request method &#39;GET&#39; not supported?
- leetcode矩阵与动态规划相关
- leetcode数组相关
- scws
- selenium3 + python - gird分布式(转载)
- python--1、入门
- Net.Json 常用例子