LA 5846 (计数) Neon Sign

从反面考虑,统计非单色三角形的个数。

如果从一个点出发两条不同颜色的边,那么这三个点一定构成一个非单色三角形。

枚举一个顶点,统计从这个点出发的红边的个数a[i]和蓝边的个数n - 1 - a[i],这样以该点为顶点的非单色三角形的数目为a[i] * (n - 1 - a[i])

由于每个单色三角形计数了两次,所以总单色三角形的个数为sum{ a[i] * (n - 1 - a[i]) | 1 ≤ i ≤ n } / 2

最后一共有C(n, 3)个三角形,用总的减去所求就是答案。

 #include <cstdio>

 const int maxn =  + ;
int a[maxn][maxn]; int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
for(int j = i + ; j <= n; j++)
{
int x;
scanf("%d", &x);
a[i][j] = a[j][i] = x;
}
long long ans1 = ;
for(int i = ; i <= n; i++)
{
int t = ;
for(int j = ; j <= n; j++) if(i != j) t += a[i][j];
ans1 += (long long)t * (n - - t);
}
long long ans2 = n * (n-) / * (n-) / ;
printf("%lld\n", ans2 - ans1 / );
} return ;
}

代码君

上一篇:c++细节--section1


下一篇:Zabbix Proxy 分布式监控