a858. 數三角形
Tags : 數學
Accepted rate : 80人/93人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-12-16 10:05

Content

給定一個大小為$N$的完全圖,其中的每條邊可能是紅色或黑色。任三個不同的點都可以形成一個三角形,請問三邊同色的三角形有幾個?

Input

輸入的第一行為一個正整數$N$。接下來的$N$行,每行有$N$個數字,其中第$i$行的第$j$個數字$c_{ij}$代表邊$(i,j)$的顏色,紅色用$1$表示,黑色用$2$表示,而當$i=j$時則用$0$表示。

  • $3 \leq N \leq 1000$。
  • 對於所有的$1 \leq i, j \leq N$,保證有$c_{ij}=c_{ji}$。
Output

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

Sample Input #1
4
0 1 2 1
1 0 1 1
2 1 0 2
1 1 2 0
Sample Output #1
1
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 0.2s , <1M
不公開 測資點#1 (20%): 0.2s , <1M
不公開 測資點#2 (20%): 0.2s , <10M
不公開 測資點#3 (20%): 0.2s , <10M
不公開 測資點#4 (20%): 0.2s , <10M
Hint :

(2017-12-16 更新)
這是我比較早期的題目
由於當時出題經驗不足 $N$設太小 讓一些$O(N^3)$的naïve做法AC了
只好降低時限並重測了@@
雖然還是可以把O(N^3)的code優化到在0.2s內跑完QAQ

Tags:
數學
出處:
ACM-ICPC5846 [管理者: xavier13540 (柊 四千) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
13146 xavier13540 (柊 四千) a858
$O(N^2)$演算法
1358 2017-12-17 20:44