P8317 [FOI2021] 幸运区间

2021 年福建省青少年信息学编程水平认证 第四题。

一个抽奖活动正在进行。每个参加活动的人拿到了 $n$ 个序列，每个序列包含了 $d$ 个正整数，以及一个数字 $k$，代表这些正整数中，存在 $k$ 个幸运数字。 每个拿到序列的人，会从自己手中的序列中选出连续的若干个序列形成一个区间，称之为待选区间。如果待选区间中的每一个序列都包含至少一个幸运数字，则称该区间为幸运区间。当然幸运区间可能不止一个。游戏规定，其中包含的序列最多的即总长度最长的那个幸运区间称为超级幸运区间。 例如：$d=2,k=3$ 时，序列如下： - 序列 $0$：``115 120``。 - 序列 $1$：``50 80``。 - 序列 $2$：``199 30``。 - 序列 $3$：``40 40``。 - 序列 $4$：``30 30``。 - 序列 $5$：``25 40``。 从序列 $0$ 到序列 $2$ 的区间是幸运区间，因为从 $0$ 到 $2$ 中的每个序列都包含了 $120,50$ 或 $30$，共 $3$ 个幸运数字。从序列 $1$ 到序列 $5$ 的区间也是幸运区间，因为 $1$ 到 $5$ 的所有序列都包含 $80,30$ 或 $40$，并且包含了 $5$ 个序列，是总长度最大的超级幸运区间。 每个有序列的人都想知道自己的超级幸运区间是怎样的。编程任务就是对于每个拿到序列的人，输出总长度最大的超级幸运区间的第一个元素的下标和最后一个元素的下标。如果有多个长度一样的，输出第一个元素下标最小的。请注意下标从 $0$ 开始。

第一行包含一个整数 $T$，表示拿到序列的人的数量。 接下来 $T$ 组数字，每组描述的是每个人的序列信息。 每组数据的第一行是三个正整数 $n,d,k$，描述如上。接下来一行，包含 $n\times d$ 个整数，前 $d$ 个整数表示第 $0$ 个序列，接下来 $d$ 个表示第 $1$ 个序列，以此类推。

对于每个人，输出一行，``Case #x: y z``，$x$ 表示 $\text{case}$ 标号（从 $1$ 开始），$y$ 和 $z$ 是答案区间的第一个和最后一个元素的下标。 （``Case`` 与 ``#`` 之间有一个空格，``#`` 与 ``x`` 之间没有空格，``:`` 后面 ``y`` 之前有一个空格，``y`` 与 ``z`` 之间有一个空格）

#### 数据范围 对于 $45\%$ 的数据，$n\le1000$。 对于 $50\%$ 的数据，$k=2$。 前两部分数据共计 $70\%$。 对于 $100\%$ 的数据，$2\le k\le 3$。 输入文件在 $\text{4.8M}$ 以内，$T=10,1\le d\le 4,1\le$ 每个序列中的数字 $\le10^5$。 对于最多 $6$ 个 $\text{case}$，$1\le n\le 10^5$，对于其他所有的 $\text{case}$，$1\le n\le 10^3$。