这是一道符合 GESP 4级 难度标准的OI风格编程题。GESP 4级主要考察一维/二维数组、基本算法逻辑（最大值/最小值查找）、简单数学函数的使用以及浮点数运算。

---

背景知识引入

好的，这是一份专门为 GESP 4级（中小学生）水平设计的启发式背景知识讲解。

我不直接把冷冰冰的公式甩给学生，而是通过一个 “侦探破案” 的故事场景，引导他们一步步发现“为什么我们要用余弦相似度”，以及“这个公式是怎么来的”。

---

🎨 启发式课堂引入：如何教计算机“看懂”名画？

同学们，今天我们来当一回“数字博物馆”的馆长。你的博物馆里有一幅非常珍贵的《星空》（我们叫它画作 A）。现在仓库里有一堆新画（画作 B），你需要从中找出一幅风格和《星空》最像的画挂在一起。

但计算机看不懂画，它只看得到一串数字（我们叫它“特征向量”）。

1. 陷入困境：距离近就是像吗？

假设我们把画简化，只看两个特征：[红色颜料量, 蓝色颜料量]。

• 画作 A（原版）：[1, 1]。 (1份红，1份蓝，颜色很平衡)
• 画作 B1（临摹版）：[100, 100]。 (这是一幅巨型壁画，用了100份红，100份蓝)
• 画作 B2（只有红）：[2, 0]。 (2份红，0份蓝)

🤔 思考时间： 如果你是观众，你觉得 B1 和 B2 谁更像 A？

• B1 虽然很大，但它的红蓝比例是 1:1，和 A 一模一样，只是更“亮”或者更“大”了。
• B2 离 A 的数值很近（2和1很接近），但它完全偏色了，根本没有蓝色。

❌ 传统的“距离法”失效了： 如果我们用直尺量距离（欧几里得距离），A(1,1) 离 B2(2,0) 很近，离 B1(100,100) 非常远。 结论： 简单的看数值差距（距离）不行，因为画幅的大小会干扰判断。我们要找的是**“方向”**（颜色的比例）是否一致！

2. 灵光一闪：看“角度”！

让我们把这三个点画在坐标轴上，从原点(0,0)出发画箭头指向它们。

• 箭头 A 指向右上方（45度方向）。
• 箭头 B1 也指向右上方（45度方向）。
• 箭头 B2 指向正右方（0度方向）。

✨ 发现秘密： B1 和 A 的箭头重合了！它们之间的夹角是 0 度。 B2 和 A 之间有一个明显的夹角。

💡 核心概念： 我们要比较两幅画像不像，其实就是看代表它们的两个箭头，张开的角度大不大：

• 角度越小，说明方向越一致，风格越相似。
• 角度越大，说明方向差得远，风格越不同。

3. 数学工具：余弦登场

在数学里，有什么工具能帮我们衡量“角度”的大小，而且结果是一个方便比较的分数呢？ 那就是——余弦（Cosine）！

还记得数学课上的知识吗（或者以后会学到）：

• 当两个箭头重合（0度）时，$\cos(0^\circ) = 1$ —— 相似度最高！
• 当两个箭头垂直（90度）时，$\cos(90^\circ) = 0$ —— 完全不相关！
• 当两个箭头反向（180度）时，$\cos(180^\circ) = -1$ —— 完全相反！

太棒了！我们只需要算出两个向量的余弦值，值越大（越接近1），画就越像！

4. 终极武器：怎么算余弦？

虽然我们知道了要算余弦，但在计算机里，我们只有坐标 (x, y)，不知道角度。这时候，数学家送给了我们一个万能公式，不需要知道角度也能算出余弦值：

$$\text{相似度} = \frac{\text{A和B的点积}}{\text{A的长度} \times \text{B的长度}} $$

我们来拆解一下这个公式，把它变成代码能写的样子（以二维为例）：

1. 分子（点积 / 内积）： 把对应的数字乘起来，再加在一起。

   • 就像是“握手”：A的x和B的x握手，A的y和B的y握手。
   • 计算：$a_1 \times b_1 + a_2 \times b_2$

2. 分母（长度的乘积）： 我们需要消除“画幅大小”的影响，所以要除以它们各自的“长度”。

   • 根据勾股定理，A的长度 $||A|| = \sqrt{a_1^2 + a_2^2}$
   • B的长度 $||B|| = \sqrt{b_1^2 + b_2^2}$

最终代码要实现的公式（推广到 n 维）：

$$\text{Result} = \frac{\sum (A_i \times B_i)}{\sqrt{\sum A_i^2} \times \sqrt{\sum B_i^2}} $$

---

📝 总结一下我们的任务：

1. 输入：拿到两组数字（数组）。
2. 分子：对应位置相乘，求和。
3. 分母：各自平方求和，开根号，再相乘。
4. 结果：分子 除以 分母，谁的结果大，谁就是最像的画！

现在，你准备好用代码来通过这个数学挑战了吗？🚀

---

题目名称：寻找最相似的画作 (The Most Similar Painting)

题目描述

在数字博物馆中，每一幅画作都被计算机抽象成了一个由 $n$ 个整数组成的“特征向量”。为了找到风格最相近的两幅画，我们需要计算向量之间的余弦相似度。

现在给出一个目标画作的特征向量 $A$，以及博物馆仓库中 $m$ 幅候选画作的特征向量 $B_1, B_2, \dots, B_m$。

请你编写程序，计算目标画作 $A$ 与每一幅候选画作 $B_k$ 的余弦相似度，并找出相似度最大的那幅画作的编号。

余弦相似度计算公式如下： 假设向量 $A = (a_1, a_2, \dots, a_n)$，向量 $B = (b_1, b_2, \dots, b_n)$。 它们的余弦相似度 $Sim(A, B)$ 为：

$$Sim(A, B) = \frac{A \cdot B}{||A|| \times ||B||} = \frac{\sum_{i=1}^{n} (a_i \times b_i)}{\sqrt{\sum_{i=1}^{n} a_i^2} \times \sqrt{\sum_{i=1}^{n} b_i^2}} $$

公式解释：

1. 分子（点积）：对应位置的数字相乘，然后求和。即 $a_1 \times b_1 + a_2 \times b_2 + \dots + a_n \times b_n$。
2. 分母（模长的乘积）：先分别计算两个向量的模长，再相乘。
   • $A$ 的模长 $||A|| = \sqrt{a_1^2 + a_2^2 + \dots + a_n^2}$
   • $B$ 的模长 $||B|| = \sqrt{b_1^2 + b_2^2 + \dots + b_n^2}$

如果有多幅画作的相似度通过计算后数值完全相同且均为最大值，则输出编号最小的那幅。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示特征向量的维度和候选画作的数量。 第二行包含 $n$ 个整数，表示目标画作 $A$ 的特征向量元素 $a_1, a_2, \dots, a_n$。 接下来 $m$ 行，每行包含 $n$ 个整数。第 $k$ 行（从 $1$ 开始计数）表示第 $k$ 幅候选画作 $B_k$ 的特征向量元素。

输出格式

输出一个整数，表示与目标画作余弦相似度最高的候选画作的编号（$1 \sim m$）。

样例 #1

样例输入 #1

2 3
1 2
2 4
1 0
2 1

样例输出 #1

1

样例 #2

样例输入 #2

3 2
1 1 1
1 0 0
2 2 2

样例输出 #2

2

提示与说明

样例 1 解释：

• 目标向量 $A = (1, 2)$。
• 候选 1 $B_1 = (2, 4)$。
  • 分子 $= 1\times2 + 2\times4 = 10$。
  • $||A|| = \sqrt{1^2+2^2} = \sqrt{5}$。
  • $||B_1|| = \sqrt{2^2+4^2} = \sqrt{20} = 2\sqrt{5}$。
  • 相似度 $= 10 / (\sqrt{5} \times 2\sqrt{5}) = 10 / 10 = 1.0$。
• 候选 2 $B_2 = (1, 0)$。相似度算出来约等于 $0.447$。
• 候选 3 $B_3 = (2, 1)$。相似度算出来0.8。
• 最大值为 $1.0$，对应编号 1。

数据范围：

• $1 \le n \le 100$
• $1 \le m \le 100$
• 向量中的整数范围在 $[0, 100]$ 之间。
• 保证所有向量的模长均不为 0（即不会出现分母为 0 的情况）。

---

题解思路与教学分析 (GESP 4级视角)

1. 题目考察点

• 多维数组/一维数组的使用：需要存储目标向量和当前输入的候选向量。
• 循环结构：需要遍历每一幅候选画作，同时在内部遍历向量的每一个维度。
• 数学函数：使用 sqrt() 计算平方根。
• 浮点数运算：余弦相似度结果是小数，需要使用 double 类型，并进行大小比较。
• 打擂台算法：在遍历过程中维护“当前最大值”及其对应的“索引”。

2. 解题步骤

1. 读取输入：先读取 $n$ 和 $m$，再用数组读取目标向量 $A$。
2. 预处理目标向量：可以先计算出目标向量 $A$ 的模长（分母的一部分），避免重复计算，不过在 $n, m$ 较小的情况下，每次重新计算也不会超时。
3. 遍历候选画作：使用一个循环 i 从 $1$ 到 $m$。
   • 在循环内读取当前画作 $B$ 的 $n$ 个特征值。
   • 计算点积（分子）：累加 $A[j] \times B[j]$。
   • 计算模长（分母）：分别累加平方和，最后开根号。
   • 计算相似度：分子 / (A模长 * B模长)。
4. 找最大值：
   • 定义一个变量 maxSim 初始为 -1.0。
   • 定义一个变量 ansIndex 记录答案。
   • 如果当前计算出的相似度 currentSim > maxSim，则更新 maxSim 和 ansIndex。
   • 注意：题目要求“相似度相同输出编号最小”，因为我们是从 $1$ 到 $m$ 顺序遍历，且只有 > 时才更新，所以自动满足该条件。

3. 参考代码 (C++ 标准)

#include <iostream>
#include <vector>
#include <cmath> // 必须包含，用于 sqrt 函数

using namespace std;

int main() {
    // 1. 定义并读取 n 和 m
    int n, m;
    cin >> n >> m;

    // 2. 读取目标向量 A
    // GESP 4级通常可以使用定长数组 int a[105]，也可以用 vector
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 提前计算 A 的模长（虽然在循环里算也没问题，但这样效率更高）
    double lengthA = 0;
    for (int i = 0; i < n; i++) {
        lengthA += a[i] * a[i];
    }
    lengthA = sqrt(lengthA);

    // 3. 变量用于记录最大相似度和对应的编号
    double maxSim = -2.0; // 余弦相似度范围是 [-1, 1]，设个更小的数做初始值
    int bestIndex = 1;

    // 4. 循环处理 m 个候选画作
    for (int k = 1; k <= m; k++) {
        vector<int> b(n);
        // 读取当前候选向量 B
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }

        // 计算点积 (分子)
        double dotProduct = 0;
        for (int i = 0; i < n; i++) {
            dotProduct += a[i] * b[i];
        }

        // 计算 B 的模长 (分母的一部分)
        double lengthB = 0;
        for (int i = 0; i < n; i++) {
            lengthB += b[i] * b[i];
        }
        lengthB = sqrt(lengthB);

        // 计算相似度
        // 题目保证分母不为0，直接除
        double currentSim = dotProduct / (lengthA * lengthB);

        // 打擂台：找最大值
        if (currentSim > maxSim) {
            maxSim = currentSim;
            bestIndex = k;
        }
    }

    // 5. 输出结果
    cout << bestIndex << endl;

    return 0;
}

4. 易错点分析

1. 数据类型：点积和模长的平方和可能会超过 int 的范围吗？题目中数最大 100，n 最大 100，$100 \times 100^2 = 1,000,000$，在 int 范围内。但计算相似度涉及到除法和开根号，必须使用 double。
2. 公式实现：初学者容易忘记给分母开根号（sqrt），或者忘记分母是两个模长相乘。
3. 精度比较：虽然浮点数比较通常需要考虑精度误差（EPS），但在GESP 4级难度中，直接使用 > 通常能通过测试数据，或者数据会设计得区分度明显。
4. 编号问题：题目要求输出 $1 \sim m$ 的编号，如果循环从 $0$ 开始写，记录答案时记得 +1。