ZeroJudge 解題筆記：b557. 直角三角形

作者：王一哲
日期：2025年7月26日


ZeroJudge 題目連結：b557. 直角三角形

解題想法

比較直接的作法是用三層迴圈掃過所有的邊長，找出可以組成直角三角形的邊長組合，這個作法在 C++ 很快，在 Python 會超時。另一種作法是先計算所有的邊長平方各有幾個，再由小到大取出邊長平方，如果兩者相加的值有在邊長平方的計數器之中，再用計數器中的數量相乘、計算直角三角形的數量。

Python 程式碼

使用 dict，使用時間約為 76 ms，記憶體約為 3.3 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):
    n = int(input())  # n 個邊長
    edges = sorted(list(map(int, input().split())))
    cnt = dict()  # 邊長平方的計數器
    cand = []  # 邊長平方
    for edge in edges:  # 計算各種邊長平方的數量
        x = edge * edge
        if x not in cnt:
            cnt[x] = 1
            cand.append(x)
        else:
            cnt[x] += 1
    m = len(cnt)  # 邊長平方的數量
    ans = 0  # 答案
    for i in range(m-1):  # 依序讀取由小到大的邊長平方
        for j in range(i+1, m):
            a, b = cand[i], cand[j]  # 邊長平方 a, b
            if a+b in cnt:  # 如果 cnt 之中有 a+b 才會更新 ans
                ans += cnt[a+b]* cnt[a] * cnt[b]
    print(ans)

使用 dict，但是第19行用 get 取值反而比較慢。使用時間約為 0.1 s，記憶體約為 3.3 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):
    n = int(input())  # n 個邊長
    edges = sorted(list(map(int, input().split())))
    cnt = dict()  # 邊長平方的計數器
    cand = []  # 邊長平方
    for edge in edges:  # 計算各種邊長平方的數量
        x = edge * edge
        if x not in cnt:
            cnt[x] = 1
            cand.append(x)
        else:
            cnt[x] += 1
    m = len(cnt)  # 邊長平方的數量
    ans = 0  # 答案
    for i in range(m-1):  # 依序讀取由小到大的邊長平方
        for j in range(i+1, m):
            a, b = cand[i], cand[j]  # 邊長平方 a, b
            ans += cnt.get(a+b, 0) * cnt[a] * cnt[b]  # 如果 cnt 之中有 a+b 才會更新 ans
    print(ans)

使用 defaultdict，使用時間約為 0.1 s，記憶體約為 6.3 MB，通過測試。

from collections import defaultdict

t = int(input())  # t 組測資
for _ in range(t):
    n = int(input())  # n 個邊長
    edges = sorted(list(map(int, input().split())))
    cnt = defaultdict(int)  # 邊長平方的計數器
    cand = []  # 邊長平方
    for edge in edges:  # 計算各種邊長平方的數量
        x = edge*edge
        cnt[x] += 1
        if x not in cand: cand.append(x)
    m = len(cnt)  # 邊長平方的數量
    ans = 0  # 答案
    for i in range(m-1):  # 依序讀取由小到大的邊長平方
        for j in range(i+1, m):
            a, b = cand[i], cand[j]  # 邊長平方 a, b
            ans += cnt[a+b] * cnt[a] * cnt[b]  # 如果 cnt 之中有 a+b 才會更新 ans
    print(ans)

C++ 程式碼

使用時間約為 9 ms，記憶體約為 48 kB，通過測試。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int n; scanf("%d", &n);
        int edges[n];
        for(int i=0; i<n; i++) scanf("%d", &edges[i]);
        sort(edges, edges+n);
        int ans = 0;
        for(int i=0; i<n-2; i++) {
            for(int j=i+1; j<n-1; j++) {
                for(int k=j+1; k<n; k++) {
                    int a = edges[i], b = edges[j], c = edges[k];
                    if (a*a + b*b == c*c) ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

使用時間約為 23 ms，記憶體約為 364 kB，通過測試。

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int n; scanf("%d", &n);
        map<int, int> cnt;
        for(int i=0, x; i<n; i++) {
            scanf("%d", &x);
            cnt[x*x]++;
        }
        vector<int> cand;
        for(auto it : cnt) cand.push_back(it.first);
        int ans = 0, m = (int)cnt.size();
        for(int i=0; i<m-1; i++) {
            for(int j=i+1; j<m; j++) {
                int a = cand[i], b = cand[j];
                ans += cnt[a+b] * cnt[a] * cnt[b];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}