島嶼渡假↘下殺$4900起來自星星的你也會打廣告?法人:14檔今年本業虧定了黃國昌嗆周祝瑛 教室一...
2012-09-01 18:10:31 人氣(325) | 回應(1) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[ACM-ICPC][Asia - Daejeon] 5846 - Neon Sign

0
收藏
0
推薦

數學解, 採用排容原理

對每個點, 都可以挑 2 個邊做一個角, 因此 C(n-1, 2) * n 個角,
對每個點, 不可能構成的角個數是 ri * bi,
但對於不可能構成單一顏色的三角形是 藍藍紅, 或者是 紅紅藍, 因此比例是 2/3,

最後將剩餘的角個數 /3 (三角形三個角), 便是答案



#include <stdio.h>
int g[1000][1000];
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, i, j;
        scanf("%d", &n);
        long long ans = (long long)(n-1)*n/2*(n-2), sum = 0;
        for(i = 0; i < n; i++) {
            for(j = i+1; j < n; j++) {
                scanf("%d", &g[i][j]);
                g[j][i] = g[i][j];
            }
            long long r = 0, b = 0;
            for(j = 0; j < n; j++) {
                if(i == j)  continue;
                if(g[i][j] == 0)    b++;
                else    r++;
            }
            sum = sum + (long long)r*b;
        }
        ans = ans - sum*3/2;
        printf("%lld\n", ans/3);
    }
    return 0;
}

5846Neon Sign
台長:Morris
人氣(325) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[ACM-ICPC][Asia - Daejeon] 5844 - Leet
此分類上一篇:[ACM-ICPC][Asia - Daejeon] 5840 - Chemical Products

asas
太神了 看完解法 一時間想不過來<(_ _)>

一���在想DP.... O(n^3) 最暴力無優化

想了許久 複雜度都降不下來 解題好久沒用數學解 果然這就是與神之間的差距....
2012-09-15 01:18:38
版主回應
只是突然靈光一閃
2012-09-16 08:20:20
我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文