1510 - Neon Sign

JungHeum recently opened a restaurant called ‘Triangle’ and has ordered the following neon sign for his
restaurant. The neon sign has N corners positioned on the circumference of a circle, and N ∗ (N −1)/2
luminous tubes that connect the corners. There are only two colors for luminous tubes, red and blue.
JungHeum wants the sign to show only one shape of a triangle at a time, whose luminous tubes
colors are same, continuously. Hence, he wants to know the number of uni-color triangles.
For example, the following neon sign has only two uni-color triangles (1, 3, 5) and (2, 3, 4).
Given the number of corners of the neon sign and the colors of the luminous tubes in the sign, write
a program that finds the number of uni-color triangles.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test
cases T is given in the first line of the input. Each test case starts with an integer N (3 ≤ N ≤ 1, 000),
which represents the number of corners of the neon sign. In the following N − 1 lines, the information
about the color of the luminous tubes are given. For the i-th line of these lines, the color information
of the luminous tubes that connect corner i to corners from corner i + 1 to N are given. Note that the
color red is represented as ‘1’ and the color blue is represented as ‘0’.

Output

Your program is to write to standard output. Print exactly one line for each test case. The line should
contain the number of uni-color triangles.
The following shows sample input and output for two test cases.

Sample Input

2
5
1 1 0 1
0 0 0
0 1
1
5
1 1 1 1
0 0 1
0 1
1

Sample Output

2
4

大意:

　　圆周上面有 n 个点, 两两之间有边, 输入每条边的颜色(2色).

　　求出同色三角形的颜色.

思路:

　　lrj 在例题里面讲了.我们只要求出非同色三角形的个数就ok了.

　　那么对于一个点 有 x 条蓝边, y 条黑边, 那么能够构成 x * y 个异色三角形.

　　如果全部加起来,每个三角形计算了2遍....(好好想想).

　　然后减掉就ok.

 1 #include<cstdlib> 2 #include<cstdio> 3 #include<iostream> 4 #include<cstring> 5 using namespace std; 6 int col[2000][3],c; 7 long long cnt,n; 8 int main() 9 {10     freopen("neon.in","r",stdin);11     freopen("neon.out","w",stdout);12     ios::sync_with_stdio(false);13     int T; cin >> T;14     while(T--){15         cin >> n;16         cnt = 0; memset(col,0,sizeof(col));17         for(int i = 1; i <= n; ++i)18             for(int j = i+1;j <= n; ++j){19                 cin >> c; col[i][c]++; col[j][c]++;20             }21         for(int i = 1; i <= n; ++i)22             cnt += col[i][0] * col[i][1];23         cout << n * (n-1) * (n-2) / 6 - cnt / 2 << endl;24     }25     return 0;26 }

View Code

uva 01510