题目描述
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;
}