ZeroJudge 解題筆記：p924.水晶共鳴 (Crystal)

作者：王一哲
日期：2026年10月27日


ZeroJudge 題目連結：p924.水晶共鳴 (Crystal)

題目 pdf 檔連結：水晶共鳴 (Crystal)

解題想法

每組測資第一列為一個整數 $n$，代表共有 $n$ 個水晶；第二列有 $n$ 個數字，分別第 $i$ 個水晶的屬性。如果相鄰且相同屬性的水晶會共鳴，融合成一個能量團，融合的水晶個數為能量團的大小，求這些水晶由左到右組成的能量團大小。這題可以在記錄水晶屬性的陣列 $crystal$ 最後面加一個不在測資範圍內的數字，例如 $0$，用來強制結算最後一組能量團。假設目前的水晶屬性 $curr = crystal[0]$，目前的能量團大小 $isum = 1$；用一個 for 迴圈跑 $crystal[1]$ 到 $crystal[n]$，如果 $crystal[i]$ 等於 $curr$，相同屬性，$isum + 1$；反之，不同屬性，結算前一組能量團，$isum$ 加到答案 $ans$ 最後面，重置 $isum = 1$、$curr = crystal[i]$。

Python 程式碼

使用時間約為 54 ms，記憶體約為 22.4 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        # 各水晶屬性，結尾加一個 0，強制結算最後一組
        crystal = list(map(int, data[ptr : ptr + n])) + [0]
        ptr += n
        ans = []  # 答案
        curr = crystal[0]  # 目前的水晶屬性
        isum = 1  # 目前的能量團量值
        for v in crystal[1:]:  # 依序讀取水晶屬性
            if v == curr:  # 同屬性，能量團量值加 1
                isum += 1
            else:  # 不同屬性，結算前一組
                ans.append(isum)
                isum = 1
                curr = v
        result.append(" ".join(map(str, ans)) + "\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 77 ms，記憶體約為 15.6 MB，通過測試。

while True:
    try:
        n = int(input())
    except EOFError:
        break

    # 各水晶屬性，結尾加一個 0，強制結算最後一組
    crystal = list(map(int, input().split())) + [0]
    ans = []  # 答案
    curr = crystal[0]  # 目前的水晶屬性
    isum = 1  # 目前的能量團量值
    for v in crystal[1:]:  # 依序讀取水晶屬性
        if v == curr:  # 同屬性，能量團量值加 1
            isum += 1
        else:  # 不同屬性，結算前一組
            ans.append(isum)
            isum = 1
            curr = v
    print(*ans)

C++ 程式碼

使用時間約為 12 ms，記憶體約為 4.2 MB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        // 各水晶屬性，結尾加一個 0，強制結算最後一組
        vector<int> crystal (n + 1, 0);
        for(int i = 0; i < n; i++) {
            cin >> crystal[i];
        }
        vector<int> ans;  // 答案
        int curr = crystal[0], isum = 1;  // 目前的水晶屬性，目前的能量團量值
        for(int i = 1; i <= n; i++) {  // 依序讀取水晶屬性
            if (crystal[i] == curr) {  // 同屬性，能量團量值加 1
                isum++;
            } else {  // 不同屬性，結算前一組
                ans.push_back(isum);
                isum = 1;
                curr = crystal[i];
            }
        }
        
        int m = (int)ans.size();
        for(int i = 0; i < m; i++) {
            cout << ans[i] << " \n"[i == m-1];
        }
    }
    return 0;
}

C 語言程式碼

使用時間約為 14 ms，記憶體約為 2.4 MB，通過測試。

#include <stdio.h>

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        // 各水晶屬性，結尾加一個 0，強制結算最後一組
        int crystal[100001] = {0};
        for(int i = 0; i < n; i++) {
            scanf("%d", &crystal[i]);
        }
        int ans[100000], head = 0;  // 答案
        int curr = crystal[0], isum = 1;  // 目前的水晶屬性，目前的能量團量值
        for(int i = 1; i <= n; i++) {  // 依序讀取水晶屬性
            if (crystal[i] == curr) {  // 同屬性，能量團量值加 1
                isum++;
            } else {  // 不同屬性，結算前一組
                ans[head] = isum;
                head++;
                isum = 1;
                curr = crystal[i];
            }
        }
        
        for(int i = 0; i < head; i++) {
            printf("%d", ans[i]);
            if (i == head - 1) printf("\n");
            else printf(" ");
        }
    }
    return 0;
}