题目描述

给定一个由数字 $0$ 到 $9$ 组成的字符串 $S$，长度为 $n$。你需要用这个字符串生成一个变种的扫雷游戏。在这个变种中，一个格子可以包含多个地雷，并且每个格子的地雷数是基于其“4 邻域”（与其边相邻的格子），而不是传统的 8 邻域。

具体过程如下：

你选择一个整数 $w$（$1 \le w \le n$）作为网格的宽度。将 $n$ 个格子（编号 $0$ 到 $n-1$）按顺序排列成网格。网格共有 $\left\lceil n / w \right\rceil$ 行（从上到下编号为 $0$ 到 $\left\lceil n / w \right\rceil-1$），和 $w$ 列（从左到右编号为 $0$ 到 $w-1$）。对于每个 $0 \leq i < n$，编号为 $i$ 的格子位于第 $\left\lfloor i/w \right\rfloor$ 行、第 $i \bmod w$ 列，并对应 $S$ 的第 $(i+1)$ 位数字。因此，第 $0$ 行包含格子 $0$ 到 $w-1$，第 $1$ 行包含格子 $w$ 到 $2w-1$，以此类推。注意，最底下一行可能不足 $w$ 个格子。

将格子排列好后，进行如下两步：

1. 对于对应于非零数字 $x$（$1$ 到 $9$）的格子，在该格子中放入 $x$ 个地雷。
2. 对于其余对应 $0$ 的格子，在该格子里填写一个数字，表示与其相邻的所有格子中地雷的总数。两个格子相邻当且仅当它们有共同的边。每个格子至多有四个相邻的格子。

对于每个宽度 $w$，定义 $f(w)$ 为所有没有地雷的格子中填写数字之和。给定整数 $k$，问 $f(1), f(2), \ldots, f(n)$ 这 $n$ 个值中的第 $k$ 大值是多少。

输入格式

第一行输入两个整数 $n$ 和 $k$（$1\leq k \leq n \leq 500\,000$）。

第二行输入一个长度为 $n$ 的，仅包含数字 $0$ 到 $9$ 的字符串 $S$。

输出格式

输出 $f(1), f(2), \ldots, f(n)$ 中的第 $k$ 大的值。

5 3
20103

7

5 1
20103

11

8 4
60409003

35

提示

示例输入输出 #1 说明

下图展示了所有 $5$ 种宽度下的网格。每个格子的点表示一个地雷。

:::align{center}

图 F.1：所有 $5$ 种可能的宽度下生成的网格。 :::

将所有没有地雷格子的数字相加，可以得到如下结果：

• $f(1) = 7$
• $f(2) = 3$
• $f(3) = 11$
• $f(4) = 4$
• $f(5) = 7$

第 $3$ 大的值为 $7$。

由 ChatGPT 5 翻译