画家

Posted on Edited on In

题目大意：一个 \(n\times m\)大小的矩形， k种颜色，每种用且只用一次一种颜色给一个连续的子矩阵上色，给出最后的形态，求有多少种颜色可能是第一次使用的。

考虑问题反面，求有多少种不可能第一次使用的，显然就是在一个矩形里面，出现了别的颜色，然后我们可以记录出每一种颜色的上限下限，左右边界，\(n^3​\)的暴力查找

貌似还可以用差分来优化，但是我不会

注意特判一种情况：n = 1, m = 1

代码如下：

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
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, k, res;
int a[320][N];
int u[N], d[N], l[N], r[N];
int has[N], cnt[N], used[N];

signed main()
{
    int i, j, col;
    n = read(), m = read(), res = k = read();
    if (n <= m) for (i = 1; i <= n; ++ i) for (j = 1; j <= m; ++ j) a[i][j] = read();
    else
    {
        for (i = 1; i <= n; ++ i) for (j = 1; j <= m; ++ j) a[j][i] = read();
        swap(n, m);
    }
    
    if (n == 1 && m == 1)
    {
        if (a[1][1] == 0) put(0);
        else
        {
            if (k == 1) put(1);
            else put(k - 1);
        }
        return 0;
    }

    memset(u, 0x3f, sizeof u), memset(l, 0x3f, sizeof l);

    for (i = 1; i <= n; i ++)
    {
        for (j = m; j >= 1; j --)
        {
            int x = a[i][j];
            has[x] = 1;
            u[x] = min(u[x], i);
            d[x] = max(d[x], i);
            l[x] = min(l[x], j);
            r[x] = max(r[x], j);
        }
    }

    cnt[0] = 1;
    for (col = 1; col <= k; col ++)
    {
        if (! has[col]) continue;
        for (i = u[col]; i <= d[col]; i ++)
        {
            for (j = l[col]; j <= r[col]; j ++)
            {
                if (a[i][j] != col && ! cnt[a[i][j]])
                    cnt[a[i][j]] = 1, --res;
            }
        }
    }

    put(res);
    return 0;
}