[at] abc 258G - Triangle 三元组可达-暴力

前言

t a g : tag : tag: bitset 01图 传送门:

题意 : 给定一个 01 01 01完全图, 1 1 1表示这两个点有边相连, 0 0 0表示这两个点没有边相连

询问有多少组三元组 ( i , j , k ) (i,j,k) (i,j,k),满足两两之间有边相连

思路 :

暴力的做法 n 3 n^3 n3,因为图只存在 01 01 01,我们考虑使用位运算减去一层的枚举

即bitset , 我们将状态存入biset中,然后枚举两行之间的状态,进行 & \& &运算

显然的如果 & = 1 \&=1 &=1那么,存在三个点是可达的,时间复杂度 n 2 l o g n n^2logn n2logn

code :

void solve(){
	int n;cin>>n;
	vector v(n);
	vector s(n);
	
	for(int i = 0; i >s[i];
		
		for(int j = 0 ; j