#P15861. [Roi2026]广义国际象棋

    ID: 15072 传统题 2000ms 1024MiB 尝试: 3 已通过: 2 难度: 5 上传者: 标签>CF1800普及+/提高-奇偶分组有限候选集缩减增量维护离散化

[Roi2026]广义国际象棋

题目描述

米哈伊尔决定学习玩“广义国际象棋”,于是准备了一块大小为 n×nn\times n 的棋盘。位于第 ii 行第 jj 列的格子被涂成颜色 ai,ja_{i,j}。

米哈伊尔是初学者,可能把棋盘涂错了。因此,有些格子可能需要重新涂成其他颜色。若一块棋盘满足以下两个条件,则称它被正确染色:

  1. 棋盘上的格子使用的颜色不超过两种;
  2. 任意两个有公共边的相邻格子颜色不同。

米哈伊尔觉得大棋盘太难玩了。因此,他可能会从原棋盘中锯下一块较小的棋盘,只保留前 rr 行和前 cc 列组成的区域,并只要求这个区域被正确染色。

对于每一对整数 r,cr,c(1≤r≤n,1≤c≤n1\le r\le n,1\le c\le n),请计算 br,cb_{r,c}:为了使由前 rr 行、前 cc 列组成的矩形区域被正确染色,至少需要重新涂色多少个格子。

输入格式

第一行包含一个整数 nn(1≤n≤4001\le n\le 400),表示棋盘大小。

接下来 nn 行描述棋盘。第 ii 行包含 nn 个整数

$$a_{i,1},a_{i,2},\ldots,a_{i,n}\quad (1\le a_{i,j}\le 10^9),$$

表示第 ii 行各个格子的颜色。

输出格式

输出 nn 行,其中第 ii 行应包含 nn 个整数

bi,1,bi,2,…,bi,n。b_{i,1},b_{i,2},\ldots,b_{i,n}。

样例 1

2
7 7
7 7
0 1
1 2

样例 2

3
1 1 2
2 4 4
3 1 2
0 1 1
0 2 4
1 3 5

子任务与评分

子任务 分值 附加限制 必要子任务
1 11 n≤50n\le 50 样例
2 22 n≤200n\le 200 样例,1
3 8 ai,j≤2a_{i,j}\le 2 -
4 17 ai,j≤10a_{i,j}\le 10 样例,3
5 15 ai,j≤100a_{i,j}\le 100 样例,3-4
6 7 ai,j≤104a_{i,j}\le 10^4 样例,3-5
7 20 无 样例,1-6

评测说明

每个子任务内的全部测试点通过后,才能获得该子任务的分数;还需通过表中列出的必要子任务。「样例」或「题面测试」指子任务 0。