HDU 5174：統計滿足條件的元素個數 (排序 + 去重 + 計數)

題目大意

給定 n 個數 (可能重複)，對數組排序去重。對於去重後的數組 b[1..m]，若 b[i] 的左右鄰居 (視為環狀) 滿足 `(b[i-1] + b[i]) % MOD == b[i+1]` (MOD = 2^31-1)，則計入原數組中 b[i] 的出現次數。求總計數。

解題步驟

1. 讀入 n 和數組，用 `map` 統計每個值的出現次數 `cnt`。
2. 將數組排序並 `unique` 去重，得到 b[1..m]。
3. 若 m == 1，無鄰居，輸出 -1。
4. 遍歷 i=1..m，檢查條件：
   • i=1：左鄰居 b[m]，右鄰居 b[2]
   • i=m：左鄰居 b[m-1]，右鄰居 b[1]
   • 其他：左鄰居 b[i-1]，右鄰居 b[i+1]
   條件：`(left + b[i]) % MOD == right`。
5. 滿足則 `ans += cnt[b[i]]`。
6. 注意用 `long long` 存儲數值和計算，避免溢出。

代碼實現 (C++)

#include 
using namespace std;
typedef long long LL;
const LL MOD = 2147483647; // 2^31 - 1

int main() {
    int n, icase = 1;
    while (~scanf("%d", &n)) {
        map cnt;
        vector a(n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
            cnt[a[i]]++;
        }
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        int m = a.size();
        
        printf("Case #%d: ", icase++);
        if (m == 1) { puts("-1"); continue; }
        
        int ans = 0;
        for (int i = 0; i < m; i++) {
            LL left = a[(i - 1 + m) % m];
            LL right = a[(i + 1) % m];
            if ((left + a[i]) % MOD == right) ans += cnt[a[i]];
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• `map` 統計頻率 + `vector` 排序去重，簡潔高效。
• 環狀鄰居用取模索引 `(i-1+m)%m` 和 `(i+1)%m` 處理。
• 模數 `2147483647` 是梅森素數 (2^31-1)，加法取模需用 64 位避免溢出後再模。
• 輸出格式 `Case #x: ans`。