解题思路

长序列下，将历史 token 划分为固定大小的空间连续块，每块做均值池化后经一个两层 MLP 压缩成向量，再用固定查询向量 $q=\mathbf{1}$ 与压缩结果做打分。得到的压缩分数序列 $A=(a_1,\dots,a_m)$ 之后，需要将其划分为恰好两个连续非空子数组，使两段和的最小值最大。整体可分为两部分：

1. 数值构造：分块 + 池化 + MLP + 打分

• 设序列长度为 $n$、维度为 $d$、块大小为 $b$，块数 $m=\lceil n/b\rceil$。
• 第 $k$ 个块的均值池化

题目内容

在大语言模型推理过程中，随着上下文长度增加，标准 $Attention$ 的计算开销以 $O(n^2)$ 增长，成为性能瓶颈。为提升长序列处理效率，提出一种基于空间连续块的稀疏注意力机制。

具体流程如下：

1. 一个长度为 $n$ 的历史 $token$ 序列，每个 $token$ 表示为 $1$ 个 $d$ 维特征向量 $\mathbf{x}_j \in \mathbb{R}^d$

   。按固定块大小$b$，将序列划分为 $m = ceil(n/b)$个空间连续块（最后一个块可不满）

   $B_1, B_2, ..., B_m$，其中：$B_k = [x_{(k-1)b}, ..., x_{min(kn)-1}]$

2. 对每个块 $B_k$：

   (1) 计算平均池化向量：$\mathbf{h}_k = \frac{1}{B_k} \sum_{x \in B_k} \mathbf{x}$

   (2) 使用一个两层多层感知机（$MLP$）进行非线性压缩（隐藏维度$d_l = 1$）：$\mathbf{c}_k = W_2 \cdot \sigma(W_1 \cdot \mathbf{h}_k + b_1) + b_2$

   其中：

   ① $W_1 \in \mathbb{R}^{1 \times d}$，$W_2 \in \mathbb{R}^{d \times 1}$，输出 $\mathbf{c}_k \in \mathbb{R}^d$

   ②$b_1 = 2$，$b_2 = 1$

   ③$\sigma(x) = max(0, x)$（即 ReLU 激活函数）

3. 给定查询向量$\mathbf{q} \in \mathbb{R}^d$（题目中固定为全 $1$ 向量：$q_i = 1$），计算每个压缩块的注意力得分：

   $a_k = \frac{\mathbf{q} \cdot \mathbf{c}_k}{\sqrt{d}}$

   得到压缩块注意力得分序列 $A = (a_1, a_2, ..., a_m)$

4. 将序列 $A$ 划分为恰好 $2$ 个连续非空子数组，目标是最大化这两个子数组和中的最小值 $S$ 。

5. 最终输出该最大化的最小值 $S$ 的整数化得分，该子数组对应的 $token$ 块将跳过细粒度 $attention$ 计算，实现稀疏推理。

   其中，整数化得分即 $S$ 乘以 $100$ 后四舍五入得到的整数，以实现保留两位小数精度的整数化表示：

   $round(100 \cdot S)$

输入描述

第 $1$ 行：$n$ $d$ $b$，以空格分隔，分别为序列长度、$token$ 向量维度、块大小

接下来 $n$ 行：每行 $d$ 个数，以空格分隔，表示 $x_i$

倒数第 $2$ 行：$d$ 个数，以空格分隔，表示 $W_1$

最后 $1$ 行：$d$ 个数，以空格分隔，表示 $W_2$

约束条件：

$1 \leq n\leq 1000$

$1 \leq b\leq n$

$1 \leq d \leq 100$

所有向量非零

输出描述

返回一个整数，即上述步骤 $5$ 的整数化得分

样例1

输入

3 1 1
2.0
4.0
6.0
1.0
2.0

输出

1700

说明

①分块：$B_1 = [2.0]$，$B_2 = [4.0]$，$B_3 = [6.0]$

②平均池化：$h_1 = [2.0]$，$h_2 = [4.0]$，$h_3 = [6.0]$

③$MLP$ 压缩：$c_1 = [9.0]$，$c_2 = [13.0]$，$c_3 = [17.0]$

④注意力得分：$A=[9,13,17]$

⑤划分为 $2$ 个连续非空子数组，最大化$min(sum)$：

$[9]|[13,17]$ $→$ 和：$9, 30 → min = 9$

$[9,13]|[17]$ $→$ 和：$22, 17 → min = 17→ S=17$，输出 1700

样例2

输入

3 2 1
2.0 1.0
3.0 2.0
4.0 3.0
1.0 0.5
2.0 1.0

输出

1732

说明

①分块：$B_1 = [2.0, 1.0]$，$B_2 = [3.0, 2.0]$，$B_3 = [4.0, 3.0]$

②平均池化：$h_1 = [2.0, 1.0]$，$h_2 = [3.0, 2.0]$，$h_3 = [4.0, 3.0]$

③$MLP$ 压缩：$c_1 = [10.0, 5.5]$，$c_2 = [13.0, 7.0]$，$c_3 = [16.0, 8.5]$

④注意力得分：$A = [\frac{15.5}{\sqrt{2}}, \frac{20.0}{\sqrt{2}}, \frac{24.5}{\sqrt{2}}]$

⑤划分为 $2$ 个连续非空子数组，最大化(min(sum))：

$[\frac{15.5}{\sqrt{2}}] ， [\frac{20.0}{\sqrt{2}}, \frac{24.5}{\sqrt{2}}] →$和：$\frac{15.5}{\sqrt{2}}$，$\frac{44.5}{\sqrt{2}}$ $→ min =$ $\frac{15.5}{\sqrt{2}}$

$[\frac{15.5}{\sqrt{2}}, \frac{20.0}{\sqrt{2}}] ， [\frac{24.5}{\sqrt{2}}] →$ 和：$\frac{35.5}{\sqrt{2}}$，$\frac{24.5}{\sqrt{2}}$ $→ min = \frac{24.5}{\sqrt{2}}→ S = \frac{24.5}{\sqrt{2}}$，输出 1732