题解 P3664 【[USACO17OPEN]Modern Art 现代艺术】

· · 题解

思路

这道题要求求出可能被第一个画的颜色的数量。

正向思维明显不好求，因为可能存在被完全覆盖的颜色（事实上也是这样的）。

因此我们不妨逆向思维：求出所有肯定不是第一个画的颜色数量，然后用总数n^2减，剩余的即为答案。

那么，不能成为第一个画的颜色有什么特征呢？

可以想到，如果一种颜色盖住了另一种颜色，那么它肯定不是第一个画的。

那么直观的思路是：我们假定图中给出的颜色即为其真实大小，然后对每一种出现的颜色占据的区域+1，最后统计所有的格子，如果一个格子上出现的颜色数量大于1中，那么最上层的颜色必然不能成为第一个画的颜色。

暴力维护显然不行，因此我们可以考虑使用二维前缀和。

这里有两个细节需要注意：

  1. 为什么不用知道真实颜色面积就可以有正确性：

  2. 假如能见得只有一种颜色的特判。

对于第一个，很多人在观察样例的时候可能会产生这样的疑问：按照这个思路，样例中2覆盖的是2*3，但事实上覆盖的是3*3，为什么不会错呢？

产生这种想法是因为题目说明了样例的形成原因，但事实上完全可以采用与题目不同的覆盖，来达到同样的结果。因此，仅根据最后结果假定面积才是正确的。

对于第二个，我第一次提交就WA在了test3，原因是对于只有一种颜色的情况程序发现没有任何一个格子的颜色数量大于1，也就是所有格子都能是第一个放的了。

然而我们知道所有颜色都必定被画了，所以只有一种颜色的情况必定是它覆盖住了其他所有颜色，因此这种颜色不能成为第一个放的。

代码

272ms 32124kb

#include<bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Fate {

    const int N=1010;
    const int INF=0x3f3f3f3f;

    int n,cnt,ans;
    int mp[N][N];
    int border[N*N][4],pre[N][N],sum[N][N],flag[N*N];

    inline void Stay_Night () {
        read(n);
        for (register int i=1; i<=n*n; ++i) {
            border[i][0]=border[i][1]=INF;
        }
        for (register int i=1; i<=n; ++i) {
            for (register int j=1; j<=n; ++j) {
                read(mp[i][j]);
                if (!mp[i][j]) continue;
                if (border[mp[i][j]][0]==INF) ++cnt;
                border[mp[i][j]][0]=min(border[mp[i][j]][0],i);
                border[mp[i][j]][1]=min(border[mp[i][j]][1],j);
                border[mp[i][j]][2]=max(border[mp[i][j]][2],i);
                border[mp[i][j]][3]=max(border[mp[i][j]][3],j);
            }
        }
        for (register int i=1; i<=n*n; ++i) {
            if (border[i][0]!=INF) {
                pre[border[i][0]][border[i][1]]++;
                pre[border[i][2]+1][border[i][3]+1]++;
                pre[border[i][0]][border[i][3]+1]--;
                pre[border[i][2]+1][border[i][1]]--;
            }
        }
        for (register int i=1; i<=n; ++i) {
            for (register int j=1; j<=n; ++j) {
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+pre[i][j];
            }
        }
        for (register int i=1; i<=n; ++i) {
            for (register int j=1; j<=n; ++j) {
                if (mp[i][j]&&sum[i][j]>1&&flag[mp[i][j]]==0) {
                    ++ans,flag[mp[i][j]]=1;
                }
            }
        }
        if (n!=1&&cnt==1) ++ans;
        write(n*n-ans);
    }

}

int main () {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    Fate::Stay_Night();
}