首页 > 代码库 > LA 5846 霓虹灯广告牌（单色三角形问题）
LA 5846 霓虹灯广告牌（单色三角形问题）
https://vjudge.net/problem/UVALive-5846
题意：
圆周上有n个点，两两相连，只能涂红色或蓝色。求单色三角形的个数。
思路:
这个问题在训练指南105页有详细讲解。
三角形的总个数为C（n，3）。
先求非单色三角形的个数，然后相减得单色三角形个数。
观察上图可以发现非单色三角形会有两个顶点连接异色的两条边，所以对于任意的一个顶点，如果它连接的红边有a[i]条，黑边有（n-1-a[i]）条，那么该顶点构成的非单色三角形就有a[i]×（n-1-a[i]）个。
将每个顶点构成的非单色三角形相加，因为每个三角形重复算了两遍，最后除2。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=1000+5;13 14 int a[maxn];15 16 int main()17 {18 //freopen("D:\\input.txt","r",stdin);19 int T;20 scanf("%d",&T);21 while(T--)22 {23 memset(a,0,sizeof(a));24 int n;25 scanf("%d",&n);26 for(int i=1;i<n;i++)27 {28 for(int j=i+1;j<=n;j++)29 {30 int x;31 scanf("%d",&x);32 if(x==1) {a[i]++;a[j]++;}33 }34 }35 long long ans=n*(n-1)*(n-2)/6;36 long long sum=0;37 for(int i=1;i<=n;i++)38 sum+=a[i]*(n-1-a[i]);39 printf("%lld\n",ans-sum/2);40 }41 return 0;42 }
LA 5846 霓虹灯广告牌（单色三角形问题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。