CF253D Table with Letters - 2 优美枚举

题目描述

Vasya has recently started to learn English. Now he needs to remember how to write English letters. He isn't sure about some of them, so he decided to train a little.

He found a sheet of squared paper and began writing arbitrary English letters there. In the end Vasya wrote nn lines containing mm characters each. Thus, he got a rectangular n×mn×m table, each cell of the table contained some English letter. Let's number the table rows from top to bottom with integers from 1 to nn , and columns — from left to right with integers from 1 to mm .

After that Vasya looked at the resulting rectangular table and wondered, how many subtables are there, that matches both following conditions:

• the subtable contains at most kk cells with "a" letter;
• all letters, located in all four corner cells of the subtable, are equal.

Formally, a subtable's definition is as follows. It is defined by four integers x_{1},y_{1},x_{2},y_{2}x1,y1,x2,y2 such that 1<=x_{1}<x_{2}<=n , 1<=y_{1}<y_{2}<=m . Then the subtable contains all such cells (x,y)(x,y) ( xx is the row number, yy is the column number), for which the following inequality holds x_{1}<=x<=x_{2},y_{1}<=y<=y_{2}x1<=x<=x2,y1<=y<=y2 . The corner cells of the table are cells (x_{1},y_{1})(x1,y1) , (x_{1},y_{2})(x1,y2) , (x_{2},y_{1})(x2,y1) , (x_{2},y_{2})(x2,y2) .

Vasya is already too tired after he's been writing letters to a piece of paper. That's why he asks you to count the value he is interested in.

输入格式

The first line contains three integers n,m,kn,m,k (2<=n,m<=400; 0<=k<=n·m) .

Next nn lines contain mm characters each — the given table. Each character of the table is a lowercase English letter.

输出格式

Print a single integer — the number of required subtables.

输入输出样例

输入 #1复制

3 4 4
aabb
baab
baab

输出 #1复制

2

输入 #2复制

4 5 1
ababa
ccaca
ccacb
cbabc

输出 #2复制

1

说明/提示

There are two suitable subtables in the first sample: the first one's upper left corner is cell (2,2)(2,2) and lower right corner is cell (3,3)(3,3) , the second one's upper left corner is cell (2,1)(2,1) and lower right corner is cell (3,4)(3,4) .

题意：

给你n*m的矩阵，统计满足一个矩阵四个角的字母相同，且满足a的个数<=k的子矩阵个数。

分析：

神级的优化枚举，固定枚举上行i和下行j，枚举左列和右列需要一定的技巧，我们依旧枚举从1到n枚举左列l，右列r从1开始，寻找可以满足的子矩阵，如果符合则就用num数组记录下来，如果不满足则r不变，l往下继续，注意要当前列消除num。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
char a[500][500];
int sum[500][500];//sum[i][j]代表 宽为i 长为j的矩阵中a的数量
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=n; i++)
        scanf("%s",a[i]+1);
    
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            if(a[i][j]=='a')
                sum[i][j]++;
        }
    ll ans=0;
    int num[300];//选取矩阵中各个字母的出现的对数
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++) //枚举矩阵的上边i和下边j
        {
            int r=1;//代表矩阵右边
            memset(num,0,sizeof(num));
            for(int l=1; l<=m; l++) //矩阵左边
            {
                if(a[i][l]!=a[j][l])
                    continue;//不满足矩形四个点相同
                num[a[i][l]]--;
                while(r<=m&&sum[j][r]-sum[i-1][r]-sum[j][l-1]+sum[i-1][l-1]<=k)
                {
                    if(a[i][r]==a[j][r])
                        num[a[i][r]]++;
                    r++;//矩形满足a个数小于kk的要求，矩阵右边增大，直到不满足，那么增大左边k++
                }
                if(num[a[i][l]]>0)
                    ans+=num[a[i][l]];//因为矩形左边固定，看右边满足四个点相同条件下有多少个这样的矩形
            }
        }
    }
    printf("%lld\n",ans);

}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=505;
int a[N][N];
char mp[N][N];
int num[400],sum[N][N];
int n,m,k; 

int get(int x1, int y1, int x2, int y2)
{
    return sum[x1][y1] - sum[x1][y2 - 1] - sum[x2 - 1][y1] + sum[x2 - 1][y2 - 1];
}
int init()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j];
        }
    }
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<=n; i++)
    {
        scanf("%s",mp[i]+1);
        for(int j=1; j<=m; j++)
        {
            if(mp[i][j]=='a')
                a[i][j]=1;
        }
    }

    init();
    LL ans=0;

    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            int r=1;
            
            memset(num,0,sizeof(num));
            for(int l=1; l<=m; l++)
            {
                if(mp[i][l]!=mp[j][l])
                {
                     continue;
                }
                 num[mp[i][l]]--;
                while(r<=m&&get(j,r,i,l)<=k)
                {
                    if(mp[i][r]==mp[j][r])
                    {
                        num[mp[i][r]]++;
                    }
                    r++;
                }
                
                if(num[mp[i][l]]>0)
                    ans+=num[mp[i][l]];
            }
        }
    }
    printf("%lld",ans);
    //cout<<ans<<endl;

    return 0;
}