社区讨论
点进来,如果你不知道怎么求逆序对
P5149 会议座位参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lz6p0d4x
- 此快照首次捕获于
- 2024/07/29 15:53 2 年前
- 此快照最后确认于
- 2024/07/29 15:53 2 年前
- 归并排序(不在这阐述)
- 树状数组
- 如果想练习《Trie树》,其实可以用Trie树做。因为我用的是Trie求逆序对,所以分享一下
首先,先将第二行的名字重新赋值为第一行的顺序编号
如:
4
S H J A
-------
A J S H
4 3 1 2
CPP然后,我们将这些数储存在a数组中
接着,按序加入01Trie中,
再接着,如果该位为0,且存在1
那么,若记cnt为该节点下一共有多少子树
则,sum+=cnt
没听懂
上代码
CPPint work ( int x ){//传进a[i];
int p = 1 ;
int sum = 0 ;//累计
for ( int i = 1 ; i <= 31 ; ++i , x >>= 1 ){
b[i] = ( x & 1 ) ;//转化为二进制,便于加入01字典树
}
for ( int i= 31 ; i >= 1 ; --i ){//从高位到低位加入
if ( trie2[p][b[i]] == 0 ) trie2[p][b[i]] = ++tot2 ;
p = trie2[p][b[i]] ;
cnt[p]++ ;//累计经过该节点的子树
}
p = 1 ;//重新遍历
for ( int i = 31 ; i >= 1 ; --i ){
if ( b[i] == 0 && trie2[p][1] ){//若x该位为0且子树该位存在1
sum += cnt[trie2[p][1]] ;//则累加
}
p = trie2[p][b[i]] ;
}
return sum ;
}
接下来,只需定义ans,并累加起 每个sum
记得开 LONG LONG
回复
共 1 条回复,欢迎继续交流。
正在加载回复...