a858. 數三角形

contents

1. 1. 題目
   1. 1.1. 內容：
   2. 1.2. 輸入說明：
   3. 1.3. 輸出說明：
   4. 1.4. 範例輸入：
   5. 1.5. 範例輸出：
2. 2. 解法

題目

內容：

你有一個大小為N的完全圖，這N(N-1)/2條邊可能是紅色或黑色。任三個不同的點都形成一個三角形，請問三邊同色的三角形有幾個？

輸入說明：

第一行輸入一個正整數N，其中N<=1,000。接下來的N行，每行有N個數字，其中第i行的第j個數字代表邊(i,j)的顏色，紅色用1表示，黑色用2表示，i=j時則用0表示。

輸出說明：

請輸出同色三角形的數目。

範例輸入：

4
0 1 2 1
1 0 1 1
2 1 0 2
1 1 2 0

範例輸出：

1

---

解法

• 作法：
  分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。

a858.cpp

/**********************************************************************************/
/*  Problem: a858 "數三角形" from                                             */
/*  Language: CPP (462 Bytes)                                                     */
/*  Result: AC(0.1s, 264KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-17 11:06:20                                     */
/**********************************************************************************/


#include <stdio.h>
int main() {
    int n, x;
    while (scanf("%d", &n) == 1) {
        int p = (n) * (n-1) * (n-2) / 6;
        int s = 0;
        for (int i = 0; i < n; i++) {
            int b = 0, r = 0;
            for(int j = 0; j < n; j++) {
                scanf("%d", &x);
                r += x == 1;
                b += x == 2;
            }
            s += r * b;
        }
        printf("%d\n", p - s/2);
    }
    return 0;
}