题解 P6404 【[COCI2014-2015#2] BOB】

Kevin_Wa · 2020-10-25 21:20:52 · 题解

本题作者思考很久，感受颇深。认为比较有价值，故写题解尽量详细。

题目大意

给你一个矩阵，问你这个矩阵所包含的所有每个元素相等的子矩阵的个数。

20pts

非常显然，使用O(n^4)的dp。开一个四维数组w[x1][y1][x2][y2]来记录以(x1,y1)为左上角，(x2,y2)为右上角的这个矩形是否满足每个元素都相等。

转移方程为：

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
int n,m,ans;
bool w[51][51][51][51];
template <typename T> void read(T &x) {
x = 0; char c = getchar();int f=1;
for (; !isdigit(c); c = getchar())if (c=='-') f=-1;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x*=f;
}
int main()
{
read(n);read(m);
for (int i=1;i<=n;i++)
  for (int j=1;j<=m;j++)
    read(a[i][j]);
if (n<=50 && m<=50)
  {
    for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
        {
        w[i][j][i][j]=true;
        for (int x=0;x<i;x++)
          for (int y=0;y<=m;y++)
            w[i][j][x][y]=true;
        for (int x=0;x<=n;x++)
          for (int y=0;y<j;y++)
            w[i][j][x][y]=true;
        for (int x=i;x<=n;x++)
          for (int y=j;y<=m;y++)
            if (w[i][j][x-1][y] && w[i][j][x][y-1] && (a[i][j]==a[x][y])) w[i][j][x][y]=true;
        }
    ans=0;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
        for (int x=i;x<=n;x++)
          for (int y=j;y<=m;y++)
            if (w[i][j][x][y]) ans++;
    printf("%d\n",ans);
    return 0;
  }

return 0;
}

理论上为60pts

#include<bits/stdc++.h>
using namespace std;
struct node{
    int num,v;
}q[1010];
int a[1010][1010],l[1010][1010],up[1010][1010];
int n,m,sum,h,x;
long long ans;
template <typename T> void read(T &x) {
x = 0; char c = getchar();int f=1;
for (; !isdigit(c); c = getchar())if (c=='-') f=-1;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x*=f;
}
int main()
{
//freopen("bob.in","r",stdin);
//freopen("bob.out","w",stdout);
read(n);read(m);
for (register int i=1;i<=n;i++)
  for (register int j=1;j<=m;j++)
    {
      read(a[i][j]);
      if (a[i][j]==a[i-1][j]) up[i][j]=up[i-1][j]+1;
      else up[i][j]=1;
      if (a[i][j]==a[i][j-1]) l[i][j]=l[i][j-1]+1;
      else l[i][j]=1;
    }
sum=0;
ans=0;
/*for (register int j=1;j<=m;j++)
  for (register int i=1;i<=n;i++)
    {
        sum=l[i][j];
        for (register int k=i;k>=i-up[i][j]+1;k--)
          {
            if (sum>l[k][j]) sum=l[k][j];
            ans+=sum;
          }
    }*/
for (register int j=1;j<=m;j++)
  {
    h=0;sum=0;
    for (register int i=1;i<=n;i++)
      {
        if (up[i][j]==1) h=0,sum=0;
        x=l[i][j];
        q[++h].num=x;
        q[h].v=1;
        sum+=x;
        while (h>1 && q[h-1].num>=q[h].num)
          {
            h--;
            sum=sum-q[h].num*q[h].v-q[h+1].num*q[h+1].v;
            q[h].v+=q[h+1].v;
            q[h].num=q[h+1].num;
            sum=sum+q[h].num*q[h].v;
          }
        ans+=sum;
        }
  }
printf("%lld\n",ans);
return 0;
}

此题区分度明显，部分分足。不失为一道好题。

撰写不易，望君满意。