题目#

你有一个大小为 $n\times n$ 的矩阵，矩阵每个格子有一个颜色 $a_{i,j}\le n$ 。

你喜欢大正方形，但你不喜欢丰富的颜色，具体的，给定讨厌值 $k \le n$ ，你需要对于所有格子，计算出以这个格子为左上角的最大正方形，满足内部颜色种数不超过 $k$ 。

你需要对于每个格子输出最大正方形的边长 $len$ 。

注意，正方形不能超出边界。

对于所有数据，满足 $1\le n\le 500,1\le k \le n,1\le a_{i,j}\le n$ 。

题解#

首先考虑暴力枚举 $n^5$ ，显然不可行

考虑优化

看到值域较小，于是乎枚举每一个元素，对于每个元素计算出g[i][j]代表这个元素A在(i, j)这个点扩展到长度为len时候正好被新加入正方形中

g[i][j] = min(g[i + 1][j] + 1, g[i][j + 1] + 1, g[i + 1][j + 1] + 1);

然后设f[i][j][len]表示当i, j这个点扩展到长度为len时会新加入多少点

在计算g[i][j]的时候顺便f[i][j][g[i][j]]++即可

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 510;
6
int a[N][N];
7

8
int read()
9
{
10
  int f = 1, x = 0;
11
  char ch = getchar();
12
  while(ch < '0' || ch > '9')
13
  {
14
    if(ch == '-') f = -1;
15
    ch = getchar();
16
  }
17

18
  while(ch >= '0' && ch <= '9')
19
  {
20
    x = x * 10 + ch - '0';
21
    ch = getchar();
22
  }
23

24
  return f * x;
25
}
26

27
int n, k;
28

29
int g[N][N];//第A个数会在以(i, j)为左上角的正方形 边长为g[i][j] 时出现
30
int f[N][N][N];
31

32
int main()
33
{
34
    freopen("square.in", "r", stdin);
35
    freopen("square.out", "w", stdout);
36
  n = read(), k = read();
37
  for(int i = 1;i <= n;i++)
38
  {
39
    for(int j = 1;j <= n;j++)
40
    {
41
      a[i][j] = read();
42
    }
43
  }
44

45
  for(int A = 1;A <= n;A++)
46
  {
47
    for(int i = n;i >= 1;i--)
48
    {
49
      for(int j = n;j >= 1;j--)
50
      {
51
        g[i][j] = 0x3f3f3f3f;
52
        if(i + 1 <= n) g[i][j] = min(g[i][j], g[i + 1][j] + 1);
53
        if(j + 1 <= n) g[i][j] = min(g[i][j], g[i][j + 1] + 1);
54
        if(i + 1 <= n && j + 1 <= n) g[i][j] = min(g[i][j], g[i + 1][j + 1] + 1);
55
        if(a[i][j] == A) g[i][j] = 1;
56
        if(g[i][j] <= n) f[i][j][g[i][j]]++;
57
      }
58
    }
59
  }
60

61
  for(int i = 1;i <= n;i++)
62
  {
63
    for(int j = 1;j <= n;j++)
64
    {
65
      int len = 1, tot = f[i][j][1];//以i，j为左上角， 边长为len第一次出现了多少新颜色
66
      while(i + len <= n && j + len <= n && f[i][j][len + 1] + tot <= k) len++, tot += f[i][j][len];
67
      printf("%d ", len);
68
    }
69
    printf("\n");
70
  }
71

72
  return 0;
73
}

正方形

https://blog.histcat.top/posts/square/

作者

Histcat

发布于

2023-09-29

许可协议

CC BY-NC-SA 4.0

等差

P1541 [NOIP2010 提高组] 乌龟棋