大概题意：给出一个由大小写英文构成的n*m矩阵，问有多少个子矩阵满足每行每列没有重复元素。
题解：首先我们知道 总共有52个字母 所以我们可以用52位的二进制表示有哪些字母出现过，每行每列用一个状压值表示元素，来保证可以快速判断一个新加入点的元素在纵向和横向是否冲突。
简单可知我们只要找到以每个点作为子矩阵左上角，对应的合法右下角点个数总和，就是我们要的答案。
对于第一列做如图操作 每一行向右遍历找最长可达到的点，直到一行合法长度为0停止。这样我们就找到了1️⃣第一列第一行的贡献。 
然后我们再去求第一列第二行的贡献，此时我们分别在横纵的状压值上删去第一行，然后接下来在之前找到的合法范围的基础上继续向外遍历找到新的最大范围即可。 这样我们在找到一列所有行贡献合的复杂度就是m*52
故总复杂度就是n*m*52
以下附上代码
#include<bits/stdc++.h>
using namespace std;
int i,i0,i1,i2,n,m,pos[1005];
long long dp1[1005],dp2[1005];
char a[1005][1005];
long long cal(char c)
{
if(c<='z'&&c>='a')return (1ll)<<(c-'a');
else return (1ll)<<(c-'A'+26);
}
int main()
{
scanf("%d %d",&n,&m);
long long ans=0;
for(i=1;i<=n;i++)scanf("%s",a[i]+1);
for(i1=1;i1<=m;i1++)
{
for(i2=1;i2<=n;i2++)
{
for(i=i2;i<=n;i++)
{
for(i0=pos[i]+1;i0<=m;i0++)
{
if(!(dp1[i]&cal(a[i][i0]))&&!(dp2[i0]&cal(a[i][i0])))
{
dp1[i]^=cal(a[i][i0]);
dp2[i0]^=cal(a[i][i0]);
pos[i]=i0;
}
else break;
}
if(pos[i]<i1)break;
ans+=pos[i]-i1+1;
}
for(i=i2,i0=i1;i0<=m;i0++)
{
if(dp2[i0]&cal(a[i][i0]))dp2[i0]^=cal(a[i][i0]);
else break;
}
}
for(i=1;i<=n;i++)pos[i]=i1,dp1[i]=0;
}
printf("%lld\n",ans);
return 0;
}
全部评论
(0) 回帖