题目
题目描述
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 2 3 4 5 6 |
4 2 2 3 0 2 7 3 7 2 7 7 7 0 0 0 0 |
输出样例#1：
|
1 2 |
14 |
说明
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
样例的差分数组：
|
1 2 3 4 5 |
1 0 0 -1 0 1 0 0 0 0 -1 1 -1 -1 1 0 |
这样子统计前缀和后，每个点的前缀和的值就是该点被覆盖的次数。
细节见代码注释。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=1005,inf=0x7fffffff; int pos[MAXN*MAXN][4],ma[MAXN][MAXN],col,ans,sum[MAXN][MAXN],cnt; bool fla[MAXN*MAXN]; int main(){ int n; cin>>n; for(int i=0;i<=n*n;i++){//初始化 pos[i][0]=pos[i][1]=inf,pos[i][2]=pos[i][3]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>col; ma[i][j]=col; if(col){//非0 if(pos[col][2]==0)cnt++; if(i<pos[col][0])pos[col][0]=i;//矩形上边边界 if(j<pos[col][1])pos[col][1]=j;//矩形左边边界 if(i+1>pos[col][2])pos[col][2]=i+1;//矩形下边边界+1 if(j+1>pos[col][3])pos[col][3]=j+1;//矩形右边边界+1 } } } for(int i=1;i<=n*n;i++){ if(pos[i][0]==inf||pos[i][2]==0)continue;//枚举出现过的颜色 sum[pos[i][0]][pos[i][1]]++;//上面说的 sum[pos[i][2]][pos[i][3]]++; sum[pos[i][0]][pos[i][3]]--; sum[pos[i][2]][pos[i][1]]--; } //前缀和 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum[i][j]+=sum[i][j-1]; } } for(int j=1;j<=n;j++){ for(int i=1;i<=n;i++){ sum[i][j]+=sum[i-1][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(ma[i][j]&&sum[i][j]>1&&fla[ma[i][j]]==0){//每种颜色只能贡献一次答案 ans++,fla[ma[i][j]]=1; } } } if(n!=1&&cnt==1)ans++; printf("%d\n",n*n-ans); return 0; } |