2012-09-01 18:10:31Morris
[ACM-ICPC][Asia - Daejeon] 5846 - Neon Sign
數學解, 採用排容原理
對每個點, 都可以挑 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;
}
對每個點, 都可以挑 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;
}
太神了 看完解法 一時間想不過來<(_ _)>
一直在想DP.... O(n^3) 最暴力無優化
想了許久 複雜度都降不下來 解題好久沒用數學解 果然這就是與神之間的差距....