解题思路

问题抽象

• 给定按时间递增的文档集合 corpus[0…N-1]（下标既是时间点），每次查询给出时间点 t 与查询串 q。

• 窗口：只在 t 及其之前的最近 K 篇文档中检索，即区间 L = max(0, t-K+1), R = min(t, N-1)。

• 打分：使用（窗口内）TF-IDF 与余弦相似度，并加入动态权重强调新文档：

  • 第 j 篇（从新到旧计数，最新 j=1）的权重 weight = (K - j + 1) / K（最新 1，最旧 1/K）。
  • 为避免“向量整体同倍缩放使余弦相似度不变”的抵消问题，本解将 weight 仅乘到分子（点积），分母仍用未加权的 TF-IDF 范数，这样权重才会影响排序且门槛仍保持在 [0,1] 区间。

• 阈值与Tie：若窗口内最高相似度 < 0.6 输出 -1；若并列，取窗口中**最早（下标最小）**的文档。

细节实现

1. TF（词频）：tf(w, doc) = count(w)/len(doc)；查询同理。

2. IDF（逆文档频率）：仅在窗口内计算并用平滑避免除零： idf(w) = ln((M+1)/(df(w)+1)) + 1，其中 M 为窗口文档数、df(w) 为窗口内包含该词的文档数。

3. 仅用查询词构建向量：计算点积与范数时只考虑出现在查询中的词（常见的检索实现，效率更高）。

4. 相似度：

   $$\text{sim}(q, d_i) = \frac{\left(\sum_{w\in q} tf_q(w)idf(w)\cdot tf_{d_i}(w)idf(w)\right)\cdot weight_i}{\|q\|\cdot \|d_i\|} $$

   其中范数用未加权的 TF-IDF 值。

5. 输出：对每个查询输出一个文档编号，之间用空格分隔。

复杂度分析

• 设窗口大小上界为 K，窗口内文档平均长度为 L，查询长度为 Q。
• 统计 df 与逐文档计算相似度的总时间为 O(K·L + K·Q)，通常记为 O(K·L)；
• 额外空间为 O(Q + K)（存放查询词表、df 与临时计数）。

代码实现

Python

import sys, math
from collections import Counter, defaultdict
input = sys.stdin.readline

def main():
    N = int(input().strip())
    docs_raw = [input().strip() for i in range(N)]
    K = int(input().strip())
    P = int(input().strip())
    queries = []
    for i in range(P):
        q = input().strip().split(' ')
        queries.append((int(q[0]),q[1:]))
        
    # 预处理每篇文档的分词与词频
    doc_tokens =[s.split() for s in docs_raw]
    doc_lens = [len(tks) for tks in doc_tokens]
    doc_cnt = [Counter(tks) for tks in doc_tokens]

    ans = []

    for t, qstr in queries:
        # 构造时间窗口 [L, R]
        R = min(max(0, t), N - 1)
        L = max(0, R - K + 1)
        M = R - L + 1  # 窗口文档数

        q_words = qstr
        if not q_words or M <= 0:
            ans.append(-1)
            continue

        q_cnt = Counter(q_words)
        q_len = len(q_words)

        # 计算窗口内查询词的 df 与 idf
        df = defaultdict(int)
        q_set = set(q_cnt.keys())
        for i in range(L, R + 1):
            # 每篇文档只记一次（是否出现）
            for w in q_set:
                if doc_cnt[i].get(w, 0) > 0:
                    df[w] += 1
        idf = {}
        for w in q_set:
            idf[w] = math.log((M + 1.0) / (df[w] + 1.0)) + 1.0  # 平滑IDF

        # 预计算查询向量范数
        q_norm_sq = 0.0
        for w, c in q_cnt.items():
            tfq = c / q_len
            x = tfq * idf[w]
            q_norm_sq += x * x
        q_norm = math.sqrt(q_norm_sq) if q_norm_sq > 0 else 1.0

        best = (-1.0, -1)  # (分数, 文档id)

        for idx in range(R, L - 1, -1):  # 从新到旧，便于计算 j
            # 该文档对查询词的 tf-idf
            dl = doc_lens[idx] if doc_lens[idx] > 0 else 1
            dot = 0.0
            d_norm_sq = 0.0
            # 只遍历查询词，提高效率
            for w, qc in q_cnt.items():
                tfd = doc_cnt[idx].get(w, 0) / dl
                tfq = qc / q_len
                dq = tfq * idf[w]
                dd = tfd * idf[w]
                dot += dq * dd
                d_norm_sq += dd * dd

            if d_norm_sq == 0.0:
                sim = 0.0
            else:
                d_norm = math.sqrt(d_norm_sq)
                # 计算位置权重：j=1 表示最新
                j = (R - idx) + 1
                weight = (K - j + 1) / K
                # 仅将权重乘到分子（点积）
                sim = (dot * weight) / (q_norm * d_norm)

            # 只保留 ≥ 0.6 的
            if sim >= 0.6 - 1e-12:
                # 并列取最早：由于我们从新到旧遍历，需要比较 id
                if sim > best[0] - 1e-12:
                    # 如果分数几乎相等，则选择更小的 idx
                    if abs(sim - best[0]) <= 1e-12:
                        best = (sim, min(best[1], idx) if best[1] != -1 else idx)
                    else:
                        best = (sim, idx)

        ans.append(best[1] if best[1] != -1 else -1)

    print(' '.join(str(x) for x in ans))

if __name__ == "__main__":
    main()

Java 实现

import java.io.*;
import java.util.*;

public class Main {

    // 将一行按任意空白分词（保留大小写）
    static List<String> splitWords(String s) {
        s = s.trim();
        if (s.isEmpty()) return Collections.emptyList();
        return Arrays.asList(s.split("\\s+")); // 自动压缩多空格/制表符
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 读 N
        int N = Integer.parseInt(br.readLine().trim());

        // 读 N 行文档；去掉结尾换行，按空白分词
        String[] raw = new String[N];
        for (int i = 0; i < N; i++) raw[i] = br.readLine().replace("\r", "");

        int K = Integer.parseInt(br.readLine().trim());
        int P = Integer.parseInt(br.readLine().trim());

        // 预处理：每篇文档的词频与长度（按词计数）
        ArrayList<HashMap<String, Integer>> dcnt = new ArrayList<>(N);
        int[] dlen = new int[N];
        for (int i = 0; i < N; i++) {
            List<String> tks = splitWords(raw[i]);
            dlen[i] = tks.size();
            HashMap<String, Integer> mp = new HashMap<>();
            for (String w : tks) mp.put(w, mp.getOrDefault(w, 0) + 1);
            dcnt.add(mp);
        }

        StringBuilder out = new StringBuilder();

        for (int qi = 0; qi < P; qi++) {
            String line = br.readLine();
            if (line == null) line = "";
            line = line.replace("\r", "").trim();

            // 解析 t 与查询串（查询可能为空）
            int sp = line.indexOf(' ');
            int t = Integer.parseInt(sp == -1 ? line : line.substring(0, sp).trim());
            List<String> qWords = (sp == -1) ? Collections.emptyList()
                    : splitWords(line.substring(sp + 1));

            // 构造时间窗口 [L, R]
            int R = Math.min(Math.max(0, t), N - 1);
            int L = Math.max(0, R - K + 1);
            int M = R - L + 1;

            if (qWords.isEmpty() || M <= 0) {
                out.append(-1);
                if (qi + 1 < P) out.append(' ');
                continue;
            }

            // 查询词频与长度
            HashMap<String, Integer> qcnt = new HashMap<>();
            for (String w : qWords) qcnt.put(w, qcnt.getOrDefault(w, 0) + 1);
            int qlen = qWords.size();

            // 计算窗口内查询词 df 与 idf（仅对查询中出现的词）
            HashMap<String, Integer> df = new HashMap<>();
            for (String w : qcnt.keySet()) df.put(w, 0);

            for (int i = L; i <= R; i++) {
                HashMap<String, Integer> dm = dcnt.get(i);
                for (String w : qcnt.keySet()) {
                    if (dm.containsKey(w)) df.put(w, df.get(w) + 1);
                }
            }

            HashMap<String, Double> idf = new HashMap<>();
            for (String w : qcnt.keySet()) {
                double v = Math.log((M + 1.0) / (df.get(w) + 1.0)) + 1.0; // 平滑IDF
                idf.put(w, v);
            }

            // 查询向量范数
            double qnorm2 = 0.0;
            for (Map.Entry<String, Integer> e : qcnt.entrySet()) {
                String w = e.getKey();
                double tfq = e.getValue() * 1.0 / qlen;
                double x = tfq * idf.get(w);
                qnorm2 += x * x;
            }
            double qnorm = qnorm2 > 0 ? Math.sqrt(qnorm2) : 1.0;

            double bestScore = -1.0;
            int bestId = -1;

            // 从新到旧遍历，便于计算 j
            for (int idx = R; idx >= L; idx--) {
                int dl = dlen[idx] > 0 ? dlen[idx] : 1;
                HashMap<String, Integer> dm = dcnt.get(idx);

                // 点积与文档范数（仅遍历查询词）
                double dot = 0.0, dnorm2 = 0.0;
                for (Map.Entry<String, Integer> e : qcnt.entrySet()) {
                    String w = e.getKey();
                    int cdoc = dm.getOrDefault(w, 0);
                    double tfd = cdoc * 1.0 / dl;          // 文档内词频
                    double tfq = e.getValue() * 1.0 / qlen; // 查询内词频
                    double dq = tfq * idf.get(w);
                    double dd = tfd * idf.get(w);
                    dot += dq * dd;
                    dnorm2 += dd * dd;
                }

                double sim = 0.0;
                if (dnorm2 > 0) {
                    double dnorm = Math.sqrt(dnorm2);
                    int j = (R - idx) + 1;             // 最新位置 j=1
                    double weight = (K - j + 1.0) / K; // 动态权重（假设 K>=1）
                    sim = (dot * weight) / (qnorm * dnorm); // 仅分子加权
                }

                // 阈值筛选 + 并列规则（取更早的文档）
                if (sim >= 0.6 - 1e-12) {
                    if (sim > bestScore + 1e-12) {
                        bestScore = sim; bestId = idx;
                    } else if (Math.abs(sim - bestScore) <= 1e-12) {
                        if (bestId == -1 || idx < bestId) bestId = idx;
                    }
                }
            }

            out.append(bestId == -1 ? -1 : bestId);
            if (qi + 1 < P) out.append(' ');
        }

        System.out.print(out.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

/**
 * 按空白分词（保留大小写），窗口内 TF-IDF + 余弦相似度（仅分子加权），
 * 阈值0.6，分数并列取更早的文档（编号更小）。
 */

// 将一行按任意空白分词（保留大小写）
static vector<string> splitWords(const string& s0) {
    vector<string> res;
    string s = s0;
    int n = (int)s.size();
    int i = 0;
    while (i < n) {
        while (i < n && isspace((unsigned char)s[i])) i++; // 跳过空白
        if (i >= n) break;
        int j = i;
        while (j < n && !isspace((unsigned char)s[j])) j++; // 读一个词
        res.emplace_back(s.substr(i, j - i));
        i = j;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;

    // 读 N
    getline(cin, line);
    int N = stoi(line);

    // 读文档原文
    vector<string> raws(N);
    for (int i = 0; i < N; ++i) {
        getline(cin, raws[i]);
        if (!raws[i].empty() && raws[i].back() == '\r') raws[i].pop_back(); // 处理 \r
    }

    getline(cin, line);
    int K = stoi(line);
    getline(cin, line);
    int P = stoi(line);

    // 预处理：每篇文档的词频与长度
    vector<unordered_map<string,int>> dcnt(N);
    vector<int> dlen(N);
    for (int i = 0; i < N; ++i) {
        vector<string> tks = splitWords(raws[i]);
        dlen[i] = (int)tks.size();
        auto &mp = dcnt[i];
        for (auto &w : tks) mp[w]++;
    }

    vector<int> answers;
    answers.reserve(P);

    for (int qi = 0; qi < P; ++qi) {
        getline(cin, line);
        if (!line.empty() && line.back() == '\r') line.pop_back();
        // 解析 t 与查询串（查询可能为空）
        auto sp = line.find(' ');
        int t = stoi(sp == string::npos ? line : line.substr(0, sp));
        vector<string> qWords = (sp == string::npos) ? vector<string>() : splitWords(line.substr(sp + 1));

        // 窗口 [L, R]
        int R = min(max(0, t), N - 1);
        int L = max(0, R - K + 1);
        int M = R - L + 1;

        if (qWords.empty() || M <= 0) {
            answers.push_back(-1);
            continue;
        }

        // 查询词频与长度
        unordered_map<string,int> qcnt;
        for (auto &w : qWords) qcnt[w]++;
        int qlen = (int)qWords.size();

        // df & idf（仅查询词）
        unordered_map<string,int> df;
        for (auto &kv : qcnt) df[kv.first] = 0;

        for (int i = L; i <= R; ++i) {
            auto &dm = dcnt[i];
            for (auto &kv : qcnt) {
                const string &w = kv.first;
                if (dm.find(w) != dm.end()) df[w]++;
            }
        }

        unordered_map<string,double> idf;
        for (auto &kv : qcnt) {
            const string &w = kv.first;
            double v = log((M + 1.0) / (df[w] + 1.0)) + 1.0; // 平滑IDF
            idf[w] = v;
        }

        // 查询向量范数
        double qnorm2 = 0.0;
        for (auto &kv : qcnt) {
            const string &w = kv.first;
            double tfq = kv.second * 1.0 / qlen;
            double x = tfq * idf[w];
            qnorm2 += x * x;
        }
        double qnorm = qnorm2 > 0 ? sqrt(qnorm2) : 1.0;

        double bestScore = -1.0;
        int bestId = -1;

        // 新->旧遍历，便于计算 j
        for (int idx = R; idx >= L; --idx) {
            int dl = dlen[idx] > 0 ? dlen[idx] : 1;
            auto &dm = dcnt[idx];

            double dot = 0.0, dnorm2 = 0.0;

            // 只遍历查询词
            for (auto &kv : qcnt) {
                const string &w = kv.first;
                int cdoc = 0;
                auto it = dm.find(w);
                if (it != dm.end()) cdoc = it->second;

                double tfd = cdoc * 1.0 / dl;           // 文档内词频
                double tfq = kv.second * 1.0 / qlen;     // 查询内词频
                double dq = tfq * idf[w];
                double dd = tfd * idf[w];
                dot += dq * dd;
                dnorm2 += dd * dd;
            }

            double sim = 0.0;
            if (dnorm2 > 0) {
                double dnorm = sqrt(dnorm2);
                int j = (R - idx) + 1;                 // 最新位置 j=1
                double weight = (K - j + 1.0) / K;     // 动态权重（假设 K>=1）
                sim = (dot * weight) / (qnorm * dnorm); // 仅分子加权
            }

            // 阈值与并列规则（更早编号优先）
            if (sim >= 0.6 - 1e-12) {
                if (sim > bestScore + 1e-12) {
                    bestScore = sim; bestId = idx;
                } else if (fabs(sim - bestScore) <= 1e-12) {
                    if (bestId == -1 || idx < bestId) bestId = idx;
                }
            }
        }

        answers.push_back(bestId == -1 ? -1 : bestId);
    }

    // 输出
    for (int i = 0; i < (int)answers.size(); ++i) {
        if (i) cout << ' ';
        cout << answers[i];
    }
    return 0;
}

题目内容

传统$TF-IDF$方法对突发新闻的敏感度不足，为提高热点词识别效果，某新闻热点追踪平台提出基于历史窗口的TF-IDF方法，具体地，在某个时间点$t$提出一个查询$q$时，系统不应该在整个历史文档库中进行大海捞针式的搜索。

相反，它需要智能地聚焦于查询发生时间点 $t$ 前的一段”历史时间窗口“内的文档，并且只需考虑这个窗口内最新的信息。

您的任务就是实现这个“历史窗口”检索引擎的核心逻辑。

历史窗口：仅计算从查询时间点 $t$ 开始之前的 $K$ 篇文档的词频，而非全部历史文档。

动态权重：为了使该搜索模型更关注短期趋势，窗口内越新(文档编号$m$越大)的文档权重越高，窗口内第$j$篇文档的权重为$(K-j+1)/K$(最新文档权重$=1$，最旧文档权重$=1/K$)。

筛选与输出：计算查询内容$q$与窗口内每一篇文档向量之间的余弦相似度$(Cosine Similarity)$,返回本次查询中余弦相似度$>=0.6$且余弦相似度最高的文档编号$m$，若未找到满足条件的文档编号(余弦相似度$<0.6$)，则本次查询返回$-1$；若存在多个相同最高相似度的文档，返回时间窗口中最早的一篇文档编号。

相似度计算方法：查询$q$向量(向量$A$)的第$i$维计算公式为，$q_i = TF(w_i,q)×IDF(w_i)$ ，其中 $TF(w_i,q)$表示词 $w_i$在所有查询内容$query$中的词频，$IDF(w_i)$表示词$w_i$在窗口文档集合中的中逆文档频率。窗口文档集合中第$n$篇文档(向量$B$)的第$i$维向量计算公式为:$d_i = TF(w_i,doc) × IDF(w_i) × weight_n$,其中 $TF(w_i,doc)$ 表示词 $w_i$在查询窗口文档集合中的词频，$IDF(w_i)$表示词 $w_i$在窗口文档中的中逆文档频率，$weight_n$表示第$n$篇文档的动态权重。

提示:向量$A.B$的余弦相似度:$\cos (A, B)=\frac{\mathbf{A} \cdot \mathbf{B}}{\|\mathbf{A}\|\|\mathbf{B}\|}$

输入描述

输入第一行表示文档集合$corpus$ 总数$N$

第二行开始每一行为从时间点$0$开始的文档，时间点和文档编号按行递增 (注:文档编号、查询时间点均可理解为数组下标，下标从$0$开始)

之后的一行为查询窗口的大小$K$

接下来的下一行表示总查询次数$P$

然后紧跟每个查询，格式为搜索时间点$t$具体查询内容$q$，$t$和$q$中间用空格隔开

参数限制

$1.1<=K<=$文档总数$N$

$2.0<$文档总数$N<=100$

$3.0<$总查询次数$P<=100$

在处理完基本题目的$I/O$操作后，你可能需要实现的函数原型

是$history$_$search$$(corpus,K，query)$，参数说明如下:

1.$corpus$：从时间点0开始的文档集合，$corpus[i]$表示第i篇文档，文档编号$m$和时间点$t$均对应数组下标，下标从$0$开始。

2.$K$:窗口大小。

3.$query$：查询列表。每个查询是一个二元组(查询时间点$t$，查询内容$q$)。

输出描述

输出空格分隔的最匹配的文档编号$m$，文档编号和查询顺序 一 一 对应，若两篇文档最高相似度相同，则返回窗口中最早的文档编号

若无匹配则对应位置返回$-1$

样例1

输入

5
long short term memory
data science
natural language processing
python for data science
a tutorial on python
3
3
2 natural language
4 python data science
4 long short term memory

输出

2 3 -1

说明

第一行$5$表示新闻文档集合$corpus$的总数$N$

然后紧跟从时间点$0$开始的具体的每篇文档，时间点和文档编号按行递增:

时间点$0$文档编号$0$："$long$ $short$ $term$ $memory$"

时间点$1$文档编号$1$：“$data$ $science$”

时间点$2$文档编号$2$：“$natural$ $language processing$"

时间点$3$文档编号$3$：“$python$ $for$ $data$ $science$"

时间点$4$文档编号$4$：“$a$ $tutorial$ $on$ $python$"

下一行的“$3$”为窗口的大小$K$

接下来的“$3$”表示查询$query$的个数

然后紧跟每个查询，格式为搜索时间点$t$具体查询内容$q$

第一次查询"$natural$ $language$"在时间点$2$，我们正好可以看到$0-2$号文档，因为只有2号文档"$natural$ $language$ $processing$"出现了关键词，因此第一个查询返回$2$

第二次查询"$python$ $data$ $science$"在时间点$4$，由于窗口大小是$3$，我们可以看到$2,3,4$号文档我们无法看到$0,1$号文档，本次查询最匹配的是文档编号 $3$

第三次查询“$long$ $short$ $term$ $memory$"在时间点$4$，同样的我们只能看到$2,3,4$号文档，无法看到$0,1$号文档，且$2,3,4$号文档中没有与查询相似文档，

所以本次查询返回$-1$

提示

1.$q$可能存在不在窗口文档集合中的查询词，因此在计算逆文档频率的时候你需要进行平滑操作，公式如下$I D F(x)=\log \left(\frac{N+1}{N(x)+1}\right)+1$其中$N$代表窗口文档的总数，而$N(x)$代表包含词$x$的文档总数

2.新闻文档集合$corpus$ 所包含的文档内容是空格分隔的小写英文文档字符串