切換
舊版
前往
大廳
主題

ZeroJudge - a064: SPOJ 4580.ABCDEF 解題心得

Not In My Back Yard | 2019-04-04 21:35:44 | 巴幣 0 | 人氣 255

題目連結:


題目大意:
給定一個整數集合 S (裡面的元素皆介於 -30, 000 ~ 30, 000 之間(含)),求有多少數組(a, b, c, d, e, f)滿足:
(a × b + c) ÷ d - e = f,其中 a 、 b 、 c 、 d 、 e 、 f 屬於 S 且 d ≠ 0 。

每組測試資料給定一個正整數 N (1 ≦ N ≦ 100),代表上述集合 S 的大小。接著的一列輸入即為 S 的內容(皆相異)。



範例輸入:
1
1

2
2
3

2
-1
1

3
5
7
10


範例輸出:
1

4

24

10


解題思維:
將方程式移項一下變為:
a × b + c = d(e + f)

因此,我們可以先窮舉出等式左半邊可能的值(同一個值有可能出現多次,這個次數也要記錄);再窮舉等式右邊可能的值是否有出現在左半邊。如果有出現,則將結果加上這個值在左半邊出現的次數。

以上可以使用 C++ 中內建的 map 容器輕鬆達成。因為 map 內建雜湊(Hash)函式,可以快速得知是否有重複的項次,以及紀錄出現次數。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作