D. 4a矩阵
time limit per test
memory limit per test
input
output
有一个 n × m 的矩阵, 行 1 到 n, 列1 to m.
4a矩阵定义:
- k个 "a" ;
- 4个角相等，长宽大于1.
请在给定矩阵中数出有几个子矩阵是4a矩阵.
Input
n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).
接下来为矩阵.
Output
一个整数，表示4a矩阵数.
Sample test(s)
input
3 4 4 aabb baab baab
output
2
input
4 5 1 ababa ccaca ccacb cbabc
output
1
Note
(2, 2) (3, 3), (2, 1) (3, 4).
这题是状态压缩问题。
用s[i][j]=∑a[1][j]+a[2][j]+..+a[i][j]
那么我们只需要枚举3个量
行的上下，还有列的
显然r列的关系可以由r-1的关系推出。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (400+10)
#define MAXM (400+10)
int n,m,k;
char a[MAXN][MAXM];
int s[MAXN][MAXM]; //表示s[i][j]=a[1][j]+a[2][j]+..a[i][j]
int c[1<<8];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
memset(s,0,sizeof(s));
scanf("%d%d%d\n",&n,&m,&k);
for (int i=1;i<=n;i++)
{
gets(a[i]+1);
for (int j=1;j<=m;j++)
{
s[i][j]=s[i-1][j]+(a[i][j]=='a');
}
}
long long ans=0;
/*
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
cout<<s[i][j]<<' ';
cout<<endl;
}
*/
;
for (int i=1;i<n;i++)
{
for (int j=i+1;j<=n;j++)
{
int l=1,tot=0;
memset(c,0,sizeof(c));
for (int r=1;r<=m;r++)
{
tot+=s[j][r]-s[i-1][r];
while (tot>k)
{
tot-=s[j][l]-s[i-1][l];
c[a[i][l]]-=(a[i][l]==a[j][l]);
l++;
}
if (l<r&&a[i][r]==a[j][r]) ans+=c[a[i][r]];
if (a[i][r]==a[j][r]) c[a[i][r]]++;
}
}
}
cout<<ans<<endl;
return 0;
}