a064 - SPOJ 4580.ABCDEF
題目描述
題目給定一個包含 N 個整數的集合 S。要求計算滿足 arr[a] * arr[b] + arr[c] = arr[d] * (arr[e] + arr[f]) 的六元組 (a, b, c, d, e, f) 的總數，其中 a, b, c, d, e, f 的值都在 0 到 N-1 之間。
解題思路
題目要求計算滿足特定等式的六元組數量。由於 N 的範圍較小 (N <= 100)，因此可以採用暴力枚舉的方法。首先，計算所有可能的 arr[a] * arr[b] + arr[c] 的值，並使用一個 map 來儲存每個值的出現次數。然後，對於所有可能的 arr[d] * (arr[e] + arr[f])，檢查它是否在 map 中存在，如果存在，則將 map 中對應的值加到答案中。
複雜度分析
- 時間複雜度: O(n^6)
- 空間複雜度: O(n^3)
程式碼
#include <iostream>
#include <map>
using namespace std;
int n;
long long int arr[201];
int main() {
while(cin >> n){
long long int ans=0;
for(int i=0;i<n;++i)
cin >> arr[i];
map <long long int,long long int> left;
for(int a=0;a<n;++a)
for(int b=0;b<n;++b)
for(int c=0;c<n;++c)
++left[arr[a]*arr[b]+arr[c]];
for(int d=0;d<n;++d)
if(arr[d])
for(int e=0;e<n;++e)
for(int f=0;f<n;++f)
ans+=left[arr[d]*(arr[e]+arr[f])];
cout << ans << "\n";
}
}