社区讨论

点进来,如果你不知道怎么求逆序对

P5149 会议座位参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lz6p0d4x
此快照首次捕获于
2024/07/29 15:53
2 年前
此快照最后确认于
2024/07/29 15:53
2 年前
查看原帖
  1. 归并排序(不在这阐述)
  2. 树状数组
  3. 如果想练习《Trie树》,其实可以用Trie树做。因为我用的是Trie求逆序对,所以分享一下
CPP
首先,先将第二行的名字重新赋值为第一行的顺序编号
如:
4
S H J A
-------
A J S H
4 3 1 2
CPP
然后,我们将这些数储存在a数组中
接着,按序加入01Trie中,
再接着,如果该位为0,且存在1
那么,若记cnt为该节点下一共有多少子树
则,sum+=cnt

没听懂

上代码

CPP
int 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 条回复,欢迎继续交流。

正在加载回复...