zcmimi's blog

arrow_back逆序对共4篇文章

avatar
zc
2020-03-24 09:05:00
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

avatar
zc
2020-03-02 02:05:00
查看原题

点击跳转

线段树合并的时候取\min(\text{交换前},\text{交换后})

avatar
zc
2020-01-19 10:55:00
查看原题

点击跳转

f[sta]表示sta表示的所有颜色都排列到从1开始的相连的一段,最少要多少次

pre[i][j]表示所有颜色i前面总共有多少个颜色j,也就是说要将所有颜色i移动到颜色j左边要移动多少次

即:\sum[y<x,c[x]=i,c[y]=j]

sta[i]表示sta表示的第i种颜色的状态

f[sta]=\min{f[sta']+\sum_{sta[j]=1,sta[k]=0}pre[j][k]}

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

看到交换相邻字母,就想到逆序对

考虑一下,一定是将A的每个字母移动到离它最近的B中相同字母的位置

我们可以用讲位置存起来然后处理一下

之后数组变成了A中每个位置最后在B中的位置

这个数组中逆序对的数目就是答案

1/1
Search
search