[USACO17OPEN]Modern Art

题目

题目描述

Art critics worldwide have only recently begun to recognize the creative genius behind the great bovine painter, Picowso.

Picowso paints in a very particular way. She starts with an N \times NN×N blank canvas, represented by an N \times NN×N grid of zeros, where a zero indicates an empty cell of the canvas. She then draws N^2N
2
rectangles on the canvas, one in each of N^2N
2
colors (conveniently numbered 1 \ldots N^21…N
2
). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:

2 2 2 0

2 2 2 0

2 2 2 0

0 0 0 0

She might then paint a rectangle in color 7:

2 2 2 0

2 7 7 7

2 7 7 7

0 0 0 0

And then she might paint a small rectangle in color 3:

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from 1 \ldots N^21…N
2
is used exactly once, although later colors might completely cover up some of the earlier colors.

Given the final state of the canvas, please count how many of the N^2N
2
colors could have possibly been the first to be painted.

小TY突然想画画,他有独特的艺术风格,他从N×N空白画布开始,其中0表示画布的空单元格。然后他会在画布上绘制恰好矩形,每个颜色是1到N×N中的一个。他每次可以选择任意一种未使用过的颜色进行绘画。例如,他可以从颜色2的矩形开始,画出这样的画布:

2 2 2 0

2 2 2 0

2 2 2 0

0 0 0 0

然后他可以用颜色7绘制一个矩形:

2 2 2 0

2 7 7 7

2 7 7 7

0 0 0 0

然后他可以在颜色3上绘制一个小矩形:

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

每个矩形都平行于画布边缘,而且矩形可以与整个画布一样大或者像一个单元一样小。每个颜色从1到正好使用一次,后来的颜色可能完全覆盖一些较早画上的颜色。

现在已知画布的最终状态,请计算有多少种颜色可能被第一个被画。

输入输出格式

输入格式:

The first line of input contains NN, the size of the canvas (1 \leq N \leq 10001≤N≤1000).

The next NN lines describe the final picture of the canvas, each containing NN integers that are in the range 0 \ldots N^20…N
2
. The input is guaranteed to have been drawn as described above, by painting successive rectangles in different colors.

输出格式:

Please output a count of the number of colors that could have been drawn first.

输入输出样例

输入样例#1:

输出样例#1:

说明

In this example, color 2 could have been the first to be painted. Color 3 clearly had to have been painted after color 7, and color 7 clearly had to have been painted after color 2. Since we don't see the other colors, we deduce that they also could have been painted first.

感谢@ yhf_2015 的翻译

题解

似乎没人写差分的代码,我这里就稍微介绍一下。
首先呢,这道题目很毒瘤,我花了好大功夫才读懂题目,无论它给你的矩阵里面有多少种颜色,它一共还是有\(N^2\)种颜色,所以显然我们找不合法的颜色就行。
观察样例我们可以发现,2颜色的矩阵显然被7的覆盖了一部分,7肯定不能第一个涂,3又把7给覆盖掉了,3也不能第一个涂。
那么我们可以把问题转化成,有x个矩形(有些被覆盖了的矩形左上角右下角还是可以算到的),求重叠部分上面的矩形的颜色总数。

当然用暴力就可以莽过去,但是遇到类似的问题用二维前缀和+二维差分显然是更优的。
参照一维差分的思想,我们可以在一个矩形的左上角+1,右下角+1,右边-1,下边-1
样例的差分数组:

这样子统计前缀和后,每个点的前缀和的值就是该点被覆盖的次数。
细节见代码注释。

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注