题解 UVA1510 【Neon Sign】

原题地址

solution:

正难则反，考虑杂色三角形的个数，计数对象可以考虑每个点.

即：总数-杂=纯

总数：C[n][3]=n!/(3!* (n-3)!)=n(n-1) (n-2)/6;

杂：(sigma r[i]* b[i])/2

杂的三角形是这样算的：
每个点有0颜色的边的个数x个和1颜色边的个数y个，
那么其产生的杂色三角形就是x* y个，但这样会有重复,想象一下一个杂色三角形，会被两个点都计数一次，这样重复度就是2，最后/2就好。

const int N = 1010;

int n;
int b[N],r[N];

int main(){
    int T;rd(T);
    while(T--){
        mem(b,0),mem(r,0);//初始化
        rd(n);
        rep(i,1,n-1){
            rep(j,i+1,n){
                int x;rd(x);
                if(x==0)b[i]++,b[j]++;
                else if(x==1)r[i]++,r[j]++;
            }
        }
        int sum=0;
        rep(i,1,n)sum+=b[i]*r[i];
        printf("%lld\n",n*(n-1)*(n-2)/6-sum/2);
    } 
    return 0;
} 

题解 UVA1510 【Neon Sign】

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11634766.html