您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

SWERC 2013 Trending Topic：滑動窗口 + 雜湊統計 Top-N 熱門詞

編輯：C++ 入門

問題重述

輸入為連續天數的文本（<text>...</text>）與查詢（<top N/>）交織。需維護最近 7 天（含查詢當天前 6 天）所有單詞頻次，查詢時輸出頻次最高的 N 個詞，同頻按字典序，且必須輸出所有與第 N 位同頻的詞。單詞長度 ≥ 4，全小寫，單日 ≤ 20,000 詞，總不同詞 ≤ 20,000，天數 ≤ 1000，N ≤ 20。

核心數據結構設計

雙層映射：字串 ⇄ 整數 ID

unordered_map str2id;
vector id2str; // id2str[id] = word

將字串映射為連續整數 ID，後續統計、排序均用整數運算，極大提升效能。

滑動窗口頻次陣列

維護循環陣列 day_sum[10][MAX_WORDS]，day_sum[d][id] 表示第 d 天（模 10）結束時該詞的累積出現次數。每日新增詞彙記錄於 dy[d] 向量，便於查詢時只遍歷當天出現過的詞。

查詢算法：O(當天詞彙數) 解法

void get_top(int cur_day, int k) {
    int week_ago = (cur_day + 3) % 10; // 7 天前 = (cur_day - 7) mod 10
    vector freq;
    // 收集當天所有詞的 7 天增量頻次
    for (int id : dy[cur_day]) {
        if (!vis[id]) {
            freq.push_back(day_sum[cur_day][id] - day_sum[week_ago][id]);
            vis[id] = true;
        }
    }
    // 找第 k 大頻次作為門檻
    nth_element(freq.begin(), freq.begin() + min(k, (int)freq.size()) - 1, freq.end(), greater());
    int threshold = freq[min(k, (int)freq.size()) - 1];
    // 收集所有 ≥ 門檻的詞
    vector> ans;
    for (int id : dy[cur_day]) if (!vis2[id]) {
        int f = day_sum[cur_day][id] - day_sum[week_ago][id];
        if (f >= threshold) ans.emplace_back(f, id2str[id]), vis2[id] = true;
    }
    // 排序：頻次降序，字典序升序
    sort(ans.begin(), ans.end(), [](auto &a, auto &b) {
        return a.first != b.first ? a.first > b.first : a.second < b.second;
    });
    // 輸出
}

關鍵優化點

只遍歷當天出現詞：dy[cur_day] 平均遠小於總詞彙量，避免全量掃描 20,000 詞。
累積頻次差分：day_sum 存前綴和，7 天頻次 = 當前累積 - 7天前累積，O(1) 查詢。
nth_element 找門檻：平均 O(n) 找第 k 大，優於全排序 O(n log n)。
循環陣列模 10：天數 ≤ 1000，模 10 足夠覆蓋 7 天窗口且無衝突。

複雜度分析

預處理：O(總詞數) 建立映射 + O(天數 × 單日詞數) 更新累積頻次
單次查詢：O(當天詞彙數) 平均 ~幾千，極快
空間：O(10 × 總詞數) ≈ 200,000 整數，極小

完整代碼骨架

#include <bits/stdc++.h>
using namespace std;
const int MAXD = 1005, MAXW = 20005;

unordered_map mp;
vector rev(MAXW);
vector day_words[10];
int sum[10][MAXW];
bool vis[MAXW], vis2[MAXW];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string token;
    int cur = 0, nxt = 1, tot = 0;
    while (cin >> token) {
        if (token == "<text>") {
            cur = nxt; nxt = (nxt + 1) % 10;
            day_words[nxt] = day_words[cur];
            copy(begin(sum[cur]), end(sum[cur]), begin(sum[nxt]));
            while (cin >> token, token[0] != '<') {
                if (token.size() < 4) continue;
                int id = mp.count(token) ? mp[token] : (mp[token] = ++tot, rev[tot] = token, tot);
                if (sum[cur][id] == 0) day_words[nxt].push_back(id);
                sum[nxt][id]++;
            }
        }
        if (token == "<top") {
            int k; cin >> k >> token; // 讀掉 "/>"
            // 執行上述 get_top 邏輯
        }
    }
}