poj 3690 Constellations 矩阵的hash - c++编程基础

TOP

poj 3690 Constellations 矩阵的hash

2015-07-20 17:48:11 来源: 作者: 【大中小】浏览:1次

Tags：poj 3690 Constellations 矩阵 hash

给定一个n*m矩阵和t个p*q的矩阵，求这t个矩阵有多少个是n*m的子矩阵。

矩阵都是01矩阵，只有'0' '*'

矩阵的hash，先将每行q列hash，得到一个新矩阵，然后再每列p行hash 【注意行列hash时候取的magic数不能一样，不然很容易冲突，会WA，最好取2个素数】

这样原矩阵的每个子矩阵都由一个数字代替了，之后用map判断就够了。

注意：不能事先将原矩阵的所有子矩阵hash值存在map里，然后比较，由于子矩阵数量太大会MLE。

map里存的应该是t个矩阵的hash值，注意有重复的矩阵，次数还是要加上。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           using namespace std; typedef unsigned long long ull; int ba=131; int ba2=499; char mp[1005][1005]; char a[100][100]; ull H[1005]; ull xp[1005]; ull xp2[1005]; ull nmp[1005][1005]; map
          
            s; map
           
             ::iterator it; int n,m,t,q,p,ca=1; int main() { xp2[0]=xp[0]=1; for(int i=1;i<=1001;i++) xp[i]=xp[i-1]*ba,xp2[i]=xp2[i-1]*ba2; while(~scanf("%d%d%d%d%d",&n,&m,&t,&p,&q)) { if(n+m+t+p+q==0) break; s.clear(); int ans=0; for(int i=0;i
            
             =0;j--) tmp=tmp*ba+a[i][j]; H[i]=tmp; } tmp=0; for(int i=p-1;i>=0;i--) tmp=tmp*ba2+H[i]; s[tmp]++; } for(int i=0;i
             
              =0;j--) H[j]=H[j+1]*ba+mp[i][j]; for(int j=0;j+q<=m;j++) nmp[i][j]=H[j]-H[j+q]*xp[q]; } for(int j=0;j+q<=m;j++) { H[n]=0; for(int i=n-1;i>=0;i--) H[i]=H[i+1]*ba2+nmp[i][j]; for(int i=0;i+p<=n;i++) { it=s.find(H[i]-H[i+p]*xp2[p]); if(it!=s.end()) { ans+=it->second; s.erase(it); } } } printf("Case %d: %d\n",ca++,ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：uva 1492 - Adding New Machine(..	下一篇：HDU 4027 Can you answer these q..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: