单色原理

时间限制：3000 ms

内存限制：65535 KB

难度：4

描述给定空间里的n个点，其中没有三点共线。每两个点之间都可以用红色和黑色线段连接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。对于给定的红色线段的列表，希望你找出单色三角形个数。输入第一行有一个整数n（3<=n<=100）表示一共有n组测试数据，接下来每一组数据第一行有一个整数m（3<=m<=1000）,表示一共有m个顶点，接下来一行有m个数，表示第i（0<=i<m）个顶点的红色边个数。输出输出每组数据中一共有几个三角形是单色三角形，换行结束。

样例输入 1 3 1 1 2

样例输出 0

来源 NOI 上传者 iphxer

/*正难则反，只要求出非单色三角形，就可以了，在每个非单色三角形中，恰好有两个顶点连接两条异色边（不含不在此三角形中的边）而且有一个公共点的两条异色边总是唯一对应一个非单色三角形，因此如果第i个点连接了x条红边y条黑边，则有x*y个非单色三角形。每个非单色三角形考虑了两次。。答案除以2即可！！*/

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<queue>

#include<set>

#include<vector>

#include<bitset>

using namespace std;

typedef long long ll;

const int M=1000010;

 

int main()

{

 　　int i,y,n,x,T;  

　　scanf("%d",&T);

 　　while(T--)  

　　{  

 　　　　int S,s;  

　　 　   S=s=0;

  　　　  scanf("%d",&n);

  　　　  S=n*(n-1)*(n-2)/6;  

 　　　　for(i=1;i<=n;i++)

 　　　  {

  　　　　 　scanf("%d",&x);  

 　　　　     y=n-1-x;   

 　　　　     s+=x*y;  

 　　　  }  

 　　     S-=s/2;   

　　      printf("%d
",S);

　　 }  

　　return 0;

}

View Code