A. 网格图覆盖问题

    传统题 文件IO:cover 1000ms 256MiB

网格图覆盖问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

莫得。

题目描述

  • 有一个 nnmm 列网格图,现有 kk 种颜色,每个格子都被染成 kk 种颜色之一(不保证每种颜色都出现了)。
  • 对于每一种颜色,请你求出能覆盖所有该颜色格子的最小的正方形的面积。
  • 正方形不可旋转,正方形可以超出网格图边界。

输入格式

cover.in 读入。

  • 第一行,三个正整数 n,m,kn,m,k
  • 接下来 nn 行,每行 mm 个数 ai,1,ai,2,,ai,ma_{i,1},a_{i,2},\cdots,a_{i,m},表示第 ii 行第 jj 列的格子,颜色为 ai,ja_{i,j}

输出格式

输出到 cover.out

  • 一行 kk 个整数,每行一个非负整数,表示最小的正方形覆盖面积。

输入输出样例

3 5 2
1 2 1 2 2
1 1 2 2 2
2 2 2 2 2
9
25

样例解释

  • 颜色 11,颜色 22 的一种可能的最优覆盖方式如上。

数据范围

  • n,m,k106n,m,k\leq 10^6
  • nm106nm\leq 10^6

子任务

子任务编号 分值 限制
1 50 n,m,k50n,m,k\leq 50
2 N/A
  • 大样例下载
  • 编号为 ii 的大样例满足编号为 ii 的子任务的限制

24KOI 2025 体验赛 No.4

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-6-22 13:00
结束于
2025-6-22 16:30
持续时间
3.5 小时
主持人
参赛人数
33