solution - AT_nikkei2019_2_final_c Largest N

· · 题解

依然是人类智慧复杂度。

Solution

首先考虑 O(n^3) 的暴力如何做到更优。可以把整个 N 拆成两条向上的直线和一条向左上的斜线，那么对于每个右下角 (i,j)，如果选定的 N 的大小为 k，那么只需要满足三个限制就可以了，而且很好算，所以应该说是 O(n^3) 跑不满而且常数很小。

然后考虑剪枝，一个简单的剪枝就是只枚举 > 当前答案的 k，这个看起来好像作用不大，但细想一下，其实这个优化的是挺大的，因为题目中限制了白点的个数，于是在矩阵很大的时候，大部分点都是黑点，所以答案就很容易变得比较大，导致 k 的实际枚举范围很小。然后因为这样，从右下角往左上角枚举似乎也会更好一点。

发现快到起飞，甚至只跑了 605ms。

Code

int n,m,u[N][N],t[N][N];
bitset <N> a[N];

signed main()
{
    read(n,m); {int qwq,x,y; read(qwq); while(qwq--) read(x,y),a[x][y]=1;}

    rep(j,1,m) rep(i,1,n) u[i][j]=(a[i][j] ? u[i-1][j]+1 : 0);
    rep(id,1,n)
    {
        t[id][1]=a[id][1];
        for(int i=id,j=1;i<=n && j<=m;++i,++j) t[i][j]=(a[i][j] ? t[i-1][j-1]+1 : 0);
    }
    rep(id,2,m)
    {
        t[1][id]=a[1][id];
        for(int i=1,j=id;i<=n && j<=m;++i,++j) t[i][j]=(a[i][j] ? t[i-1][j-1]+1 : 0);
    }

    int ans=0;
    rpe(i,n,1) rpe(j,m,1) rpe(k,min(u[i][j],t[i][j]),ans+1) if(u[i][j-k+1]>=k)
    {
        ans=k;
        break;
    }

    write(ans);

    return 0;
}

华风夏韵，洛水天依！