UVALive5846

题目大意：见刘汝佳《算法竞赛入门经典——训练指南》P173。

解题思路：

　　如果要直接求所有单色三角形的个数似乎不简单，正难则反，先求出所有非单色三角形 cnt，answer = C（n,3）- cnt。

　　首先，对于每一个非单色三角形，一定有2个点对应一对异色边，那么我们只需要统计每一个点连接的红边或者蓝边数 t，则这个点连接的异色三角形个数为：t*（n - 1 - t），把各边的异色三角形个数加起来。按照这种方式，对于每一个非单色三角形我们都会从它的2个连接着一对异色边的点计算各一次，所以我们要将得到的异色三角形总数除以二就可以得到正确的 cnt。

AC代码：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 bool color[maxn][maxn];

 int main()

 {

     int T,tmp;

     int N;

     scanf("%d",&T);

     while(T--){

         ll t1=;

         scanf("%d",&N);

         for(int i=;i<N;i+=){

             for(int j=i+;j<=N;j+=){

                 scanf("%d",&tmp);

                 if(tmp) color[i][j]=color[j][i]=true;

                 else    color[i][j]=color[j][i]=false;

             }

         }

         for(int i=;i<=N;i++){

             ll on=;

             for(int j=;j<=N;j++){

                 if(i==j)    continue;

                 if(color[i][j]) on++;

             }

             t1+=(on*(N--on));

         }

         ll ans=(ll)N*(N-)*(N-)/-t1/;

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

UVALive5846

最新文章

热门文章