牛客竞赛3 J（思维）

Counting Triangles

给n个点，组成的边有黑色和白色，问组成的三角形边为同色的个数

思路：
因为边只有两种颜色，所以三角形只有两种：一种是三条边颜色都相同的，另一种是三条边，两条颜色相同，另一条颜色不同

即不符合条件的三角形必然存在这样的点：这个点连接的边既有黑边又有白边，黑边数*白边数/2就是这个点形成的不符合条件的三角形个数

所求即为C_n³减去不符合的三角形数

#include
using namespace std;
typedef long long ll; 
namespace GenHelper
{unsigned z1,z2,z3,z4,b,u;unsigned get(){b=((z1<<6)^z1)>>13;z1=((z1&4294967294U)<<18)^b;b=((z2<<2)^z2)>>27;z2=((z2&4294967288U)<<2)^b;b=((z3<<13)^z3)>>21;z3=((z3&4294967280U)<<7)^b;b=((z4<<3)^z4)>>12;z4=((z4&4294967168U)<<13)^b;return (z1^z2^z3^z4);}bool read() {while (!u) u = get();bool res = u & 1;u >>= 1; return res;}void srand(int x){z1=x;z2=(~x)^0x233333333U;z3=x^0x1234598766U;z4=(~x)+51;u = 0;}
}
using namespace GenHelper;
int w[8005]={0};//记录每个点的黑色边的个数 
ll cot=0;//记录不符合条件的三角形个数 
bool edge[8005][8005];
int main() {ll n; //设long long  int seed;cin >> n >> seed;srand(seed);for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++){edge[j][i] = edge[i][j] = read();//记录每个点的黑色边的个数 if(edge[i][j]) {w[i]++;w[j]++;}}//对于遍历到的每个点，统计不符合条件的三角形个数//黑边数*白边数/2//除于2是因为同一个三角形，在以i为遍历点和不以i为遍历点时各统计了一次	for(int i=0;i<n;i++){cot+=w[i]*(n-1-w[i])/2; }//n个点中取3个形成的三角形个数减去不符合条件的三角形个数 cout<<n*(n-1)*(n-2)/6-cot<<endl;//注意n^3会爆int return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！