USACO17OPEN Modern Art

题目传送门

很妙的差分题目

分别找到画布上每种颜色的最上、最下、最左和最右，然后进行差分，求出每个位置至少涂了几次。如果涂的次数> 1，则肯定不是先涂的
有一种特殊情况，如果涂的次数== 1，但只有一种颜色，且n != 1，则一定不是先涂的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int u[1000010], d[1000010], l[1000010], r[1000010], cnt;
int col[1010][1010], x[1010][1010], ans;
bool vis[1000010];
int main() {
    int n = read();
    memset(u, 127, sizeof(u)); memset(l, 127, sizeof(l));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) {
            int a = read(); x[i][j] = a;
            if(!d[a] && a) ++cnt;
            u[a] = min(u[a], i); d[a] = max(d[a], i);
            l[a] = min(l[a], j); r[a] = max(r[a], j);
        }
    for(int i = 1; i <= n*n; ++i) {
        if(!d[i]) continue;
        col[u[i]][l[i]] += 1;
        col[u[i]][r[i]+1] -= 1;
        col[d[i]+1][l[i]] -= 1;
        col[d[i]+1][r[i]+1] += 1;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            col[i][j] += col[i][j-1] + col[i-1][j] - col[i-1][j-1];
            if(x[i][j] && col[i][j] > 1)
                vis[x[i][j]] = 1;
        }
    }
    for(int i = 1; i <= n*n; ++i)
        if(!vis[i]) ++ans;
    if(cnt == 1 && n > 1) --ans;
    cout << ans << endl;
    
    return 0;
}

USACO17OPEN Modern Art

原文：https://www.cnblogs.com/morslin/p/11855849.html