题解：AT_nikkei2019_2_final_c Largest N

题解：AT_nikkei2019_2_final_c Largest N

题意

给你一个矩阵，标记其中的一些点，让你求出最大的一个 N 满足：

• N 上的点不能有标记
• N 是“正”的，不允许翻转
• N 是“方”的，也就是说如果把 N 放进一个正方形，N 的两竖作为正方形的两条边的话，那 N 中间的一斜就在正方形对角线上

分析

注意此题时限 4 秒，我们考虑考虑有没有什么暴力的方法。

我们可以 \mathcal{O(n^2)} 预处理出每个点直向上最多能延伸到哪个没有标记的点，存 up 数组里；同时预处理出每个点斜向左上方最多能延伸到哪个没有标记的点，存进 sli 数组里。

统计答案时 \mathcal{O(n^2)} 枚举 N 的右下角 (i,j)，然后枚举 N 的边长 k，计算出 N 的左下角 (i,j-k+1)。如果 N 上没有标记的点，即 k\leq up_{i,j} 同时 k\leq sli_{i,j} 并且 k\leq up_{i,j-k+1}。那么用 k 更新答案。

时间复杂度 \mathcal{O(n^3)}，但实际可以跑的更快，具体看代码。

代码

//AT_nikkei2019_2_final_c

#include <iostream>
#include <cstdio>

using namespace std;

int read()
{
    int res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = -1;
    for (; isdigit(ch); ch = getchar())
        res = (res << 3) + (res << 1) + (ch - '0');
    return res * f;
}

const int N = 3005;

int n, m, k, ans;
int up[N][N], sli[N][N];
bool mp[N][N];

int main()
{
    n = read(), m = read(), k = read();
    for (int i = 1, x, y; i <= k; i ++)
    {
        x = read(), y = read();
        mp[x][y] = 1;
    }
    //预处理
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            if (!mp[i][j])
            {
                up[i][j] = up[i - 1][j] + 1;
                sli[i][j] = sli[i - 1][j - 1] + 1;
            }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            int tmp = min(up[i][j], sli[i][j]);
            if (mp[i][j] || tmp <= ans)
                continue;
            //只枚举能够对答案有贡献的k
            for (int k = ans; k <= tmp && j - k + 1 >= 1 && i - k + 1 >= 1; k ++)
                if (up[i][j - k + 1] >= k)
                    ans = max(ans, k);
        }
    printf("%d\n", ans);

    return 0;
}