首页 > 代码库 > 计数(数学题，思维技巧)
计数(数学题，思维技巧)
计数
Time Limit:0MS Memory Limit:0KB 64bit IO Format:%lld & %lluDescription
给定空间里n个点，其中没有三点共线。每两个点之间都用红色或蓝色线段连接。如果一个三角形的三条边同色，则称这个三角形是单色三角形。给出红色线段的列表，求出单色三角形的总数。
Input
第一行测试数据的总数T。
对于每个测试数据。
第一行为点数n(3<=n<=1000).
第二行为红色线段的总数m(m<=250000).
接下来m行每行两个整数u和v，表示点u和点v之间的线段为红色线段。
Output
输出单色三角形的总数
Sample Input
1
6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6
Sample Output
2
//这题暴力三重循环也能过。。。数据较弱
328ms
1 #include <stdio.h> 2 #include <string.h> 3 4 int n,m; 5 int ans; 6 int bian[1005][1005];//0为蓝,1为红 7 8 int func(int u) 9 {10 int i,j;11 int s1,s2,s3;12 for (i=u+1;i<=n;i++)13 {14 if (i==u) continue;15 s1=bian[u][i];16 for (j=i+1;j<=n;j++)17 {18 if (j==u) continue;19 s2=bian[i][j];20 if (s2==s1)21 {22 s3=bian[j][u];23 if (s2==s3)24 {25 ans++;26 //printf("%d %d %d\n",u,i,j);27 }28 }29 }30 }31 }32 33 int main()34 {35 int T;36 scanf("%d",&T);37 while (T--)38 {39 scanf("%d",&n);40 memset(bian,0,sizeof(bian));41 scanf("%d",&m);42 int i;43 int u,v;44 for (i=1;i<=m;i++)45 {46 scanf("%d%d",&u,&v);47 bian[u][v]=bian[v][u]=1;48 }49 50 ans=0;51 for (i=1;i<=n;i++)52 {53 func(i);54 }55 printf("%d\n",ans);56 }57 return 0;58 }
//当然，必须上简便方法，方法是这样的，如果是 n 边形，看其中的一个点，如果有a个红边连着它，就有 n-1-a 的蓝边连着它。
a * (a-1-n) 的意思便是由这个点会组成多少不同颜色的三角形，将点遍历一遍，求出有多少不同颜色的三角形，关键在去重，不是除3，而是除2
因为要组成个三角形不但要连接每个点的两条边，还需要一个边，但是只有两种颜色，所以第三边肯定不是红就是蓝，所以每一个不同颜色的三角形被 2 个点重复计算了，所以除2
然后用组合公式 C(n,3) 减去就是答案
40ms
1 #include <stdio.h> 2 #include <string.h> 3 4 int dot[1005]; 5 int n,m; 6 7 int C(int a,int b)// a!/(a-b)!/b! 8 { 9 return n*(n-1)*(n-2)/6;10 }11 12 int main()13 {14 int T;15 scanf("%d",&T);16 while (T--)17 {18 memset(dot,0,sizeof(dot));19 scanf("%d",&n);20 scanf("%d",&m);21 int u,v;22 for (int i=0;i<m;i++)23 {24 scanf("%d%d",&u,&v);25 dot[u]++;26 dot[v]++;27 }28 int Q=0;29 for (int i=1;i<=n;i++)30 Q+=(n-1-dot[i])*dot[i];31 32 int ans=C(n,3)-Q/2;33 printf("%d\n",ans);34 }35 return 0;36 }
计数(数学题，思维技巧)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。