[ABC278E] Grid Filling 题解

FFTotoro · 2022-11-21 16:23:29 · 题解

本题需要使用类似高维前缀和的做法。

首先预处理，用 F_{i,j,x} 表示 (1,1) 为左上角、(i,j) 为右上角的矩阵中 x 的个数。易得 F 的转移式：

转移方程的依据是容斥原理，考虑到学过二维前缀和的人较多，这里不多赘述。

然后对于每一对 (k,l) 我们只需统计题目所示的小矩阵中每个数的个数（可以由 F 推导出来）。具体地，以 (k+1,l+1) 为左上角，(k+h,l+w) 为右下角的子矩阵中 x 的个数即为：

可以发现，\forall 1\le x\le N，如果上述式子的值等于 F_{H,W,x} 的值，就说明这个子矩阵外已经不包含任何的 x。

如果我们称满足上述条件的的 x 为“独特的”，那么每次询问的答案就是整个矩阵中包含的不同种类的数的数量减去子矩阵内“独特的”数的数量。

具体地，每次询问中对于每个在矩阵中有出现过的 x 判断一下即可。

总时间复杂度 O(HWN)，可以通过本题。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300;
int c[N+1][N+1][N+1];
bool v[N+1];
set<int> s;
main(){
  ios::sync_with_stdio(false);
  int h,w,n,a,b; cin>>h>>w>>n>>a>>b;
  for(int i=1;i<=h;i++)
    for(int j=1;j<=w;j++){
      int x; cin>>x;
      for(int k=1;k<=n;k++)
        c[i][j][k]=c[i-1][j][k]+c[i][j-1][k]-c[i-1][j-1][k]+(x==k);
      s.emplace(x); v[x]=true;
    } // 前缀和预处理
  for(int i=0;i<=h-a;i++,cout<<endl)
    for(int j=0;j<=w-b;j++){
      int r=0;
      for(int k=1;k<=n;k++)
        if(v[k])r+=(c[i+a][j+b][k]-c[i][j+b][k]-c[i+a][j][k]+c[i][j][k]==c[h][w][k]); // 统计“独特的”x
      cout<<s.size()-r<<' ';
    } // 枚举 (k,l)
  return 0;
}