2026 杭电春季联赛 4——1002/1003-通行证（Easy Version/Hard Version）

题目大意

题目大意

给定一个 $n \times n$ 的方阵 $a$，其外围被一圈值为 $10^{100}$ 的元素包围，共同形成一个 $(n+2) \times (n+2)$ 的方阵。
每个元素代表一个人的识别码。对于给定的通行证 $card$，如果一个人的识别码 $x$ 满足 $x$ 按位或 $card \neq card$（即 $x$ 的二进制表示中存在 $card$ 没有的 $1$），则该人被视为“坏蛋”。（由于外围一圈元素的值极大，它们一定会满足该条件被判定为坏蛋）。

每个人（包含坏蛋自身）的安全感定义为：从当前位置出发，沿上下左右四个直线方向寻找，距离其最近的坏蛋的距离。如果自身是坏蛋，则距离为 $0$。

现在有 $q$ 次询问，每次给定一个 $card$，求方阵 $a$ 中所有人的安全感之和。

数据范围

• $1 \le T \le 10$

• $1 \le n \le 300$

• $1 \le q \le 5 \times 10^4$

• $0 \le a_{i,j} < 2^{15}$

• $0 \le card < 10^9$

样例输入

1
5 1
5 5 1 5 5
5 5 1 5 5
1 1 1 1 1
5 5 1 5 5
1 5 1 5 5
1

样例输出

12

样例解释

在样例中，$n=5$，$card = 1$。
由于坏蛋的条件是 $x$ 按位或 $1 \neq 1$，因此识别码为 $1$ 的是好人（用 G 表示），识别码为 $5$ 的是坏蛋（用 B 表示）。外围一圈全部是极大值，均为 B。方阵的状态如下：

B B B B B B B
B B B G B B B
B B B G B B B
B G G G G G B
B B B G B B B
B G B G B B B
B B B B B B B

我们可以计算每个好人位置上，在上下左右四个直线方向中，遇到最近的坏蛋的距离：

• 对于 $(1, 3)$ 的 G，向上一步即为外围的 B，距离为 $1$。

• 对于 $(2, 3)$ 的 G，向左一步为内部的 B，距离为 $1$。

• 对于第三行的四个 G（除了中心 $(3, 3)$）：

  • $(3, 1)$ 向上一步为 B，距离为 $1$。
  • $(3, 2)$ 向上一步为 B，距离为 $1$。
  • $(3, 4)$ 向上一步为 B，距离为 $1$。
  • $(3, 5)$ 向上一步为 B，距离为 $1$。

• 对于中心的 $(3, 3)$，它的上下左右连续两个位置都是 G，直到第三个位置才是外围或内部的 B，因此最近距离为 $3$。

• 对于 $(4, 3)$ 的 G，向左一步为内部的 B，距离为 $1$。

• 对于第五行的两个 G：

  • $(5, 1)$ 向右一步为内部的 B，距离为 $1$。
  • $(5, 3)$ 向左一步为内部的 B，距离为 $1$。

将所有好人的距离相加：$1 + 1 + 1 \times 4 + 3 + 1 + 1 \times 2 = 12$。坏蛋自身的最近距离为 $0$，因此安全感总和为 $12$，与样例输出一致。

思路讲解

AI 生成的 latex 题解代码

No content to show

AC代码

源代码

心路历程（WA，TLE，MLE……）