http://poj.org/problem?id=3690

题目大意:给一个图和几个子图,判断有多少种子图在原图出现过。

——————————————————————

二维哈希即可,操作看代码,我觉得蛮好看的。

注意这题恶心的时限。

pow预处理能少时间,读入字符用getchar不然会TLE。

用multiset查找然后再一个个erase即可,这样set前后size的差值即是答案。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<set>
using namespace std;
typedef unsigned long long ll;
const int N=;
const int M=;
const int P=;
const int Q=;
const ll b=;
const ll w=1e8+;
ll ha0[N][M];
ll ha1[P][Q];
ll qpow[][P];
inline ll tn(char ch){
if(ch=='')return ;
return ;
}
void init(){
qpow[][]=qpow[][]=;
for(int i=;i<P;i++){
qpow[][i]=qpow[][i-]*b;
qpow[][i]=qpow[][i-]*w;
}
return;
}
int main(){
init();
int n,m,t,p,q,casenum=;;
while(cin>>n>>m>>t>>p>>q){
if(n+m+t+p+q==)break;
multiset<ll>app;
casenum++;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
char ch=getchar();
while(ch==' '||ch=='\n')ch=getchar();
ha0[i][j]=ha0[i][j-]*b+tn(ch);
}
}
for(int j=;j<=m;j++){
for(int i=;i<=n;i++){
ha0[i][j]+=ha0[i-][j]*w;
}
}
for(int k=;k<=t;k++){
for(int i=;i<=p;i++){
for(int j=;j<=q;j++){
char ch=getchar();
while(ch==' '||ch=='\n')ch=getchar();
ha1[i][j]=ha1[i][j-]*b+tn(ch);
}
}
for(int j=;j<=q;j++){
for(int i=;i<=p;i++){
ha1[i][j]+=ha1[i-][j]*w;
}
}
app.insert(ha1[p][q]);
}
for(int i=p;i<=n;i++){
for(int j=q;j<=m;j++){
int si=i-p,sj=j-q;
app.erase(ha0[i][j]-ha0[si][j]*qpow[][p]-ha0[i][sj]*qpow[][q]+ha0[si][sj]*qpow[][p]*qpow[][q]);
}
}
printf("Case %d: %d\n",casenum,t-(int)app.size());
}
return ;
}

最新文章

  1. Visual Studio 2015中创建C#的Android项目提示&quot;Value cannot be null&quot;的解决方法
  2. XAF视频教程来啦,已出15课
  3. djangocms安装技巧
  4. ps技巧
  5. 想在Images.xcassets 只能用 imageNamed 加载里边的素材 其他方法 你就别费老劲了
  6. javascript中字符串的常用方法
  7. python 数据加密以及生成token和token验证
  8. EasyUI-标签(Tabs)用法
  9. 全面理解Unity加载和内存管理
  10. Delphi编程中资源文件的应用
  11. linux kickstart 自动安装
  12. ubuntu12.04的NFS配置
  13. PAT1005
  14. HTML表格边框的设置小技巧-表格
  15. Objective-C中的Hello World
  16. 常用FastJSON的SerializerFeature特性及日期转换格式
  17. linkin大话设计模式--代理模式
  18. __c语言__整型、实型的存储(十进制转二进制)
  19. lua语言三目运算符
  20. 慢工出细活 JS 等待加载效果

热门文章

  1. 移动onenet基础通信套件V1.08版本的AT指令测试
  2. python 终极篇 --- django 路由系统
  3. Java学习笔记-13.创建窗口和程序片
  4. 技本功丨知否知否,Redux源码竟如此意味深长(下集)
  5. [HNOI2017]大佬
  6. error:no module named StringIO or cStringIO
  7. leetcode个人题解——#18 4sums
  8. crt0.S(_main)代码分析
  9. Python3 小工具-ICMP扫描
  10. POJ 3525/UVA 1396 Most Distant Point from the Sea(二分+半平面交)