【BZOJ 2351】 Matrix
2024-08-31 06:01:33
【题目链接】
https://www.lydsy.com/JudgeOnline/problem.php?id=2351
【算法】
哈希
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
typedef unsigned long long ull;
const int base1 = ;
const int base2 = ;
const int P = 1e5 + ; int i,j,m,n,a,b,q;
ull sum[MAXN][MAXN];
ull power1[MAXN],power2[MAXN];
ull t;
vector< ull > e[P];
char c;
char s[MAXN][MAXN]; inline void insert(ull x)
{
int h = (int)(x % P);
e[h].push_back(x);
}
inline bool query(ull x)
{
int i;
int h = (int)(x % P);
for (i = ; i < (int)e[h].size(); i++)
{
if (e[h][i] == x)
return true;
}
return false;
} int main()
{ scanf("%d%d%d%d",&m,&n,&a,&b);
for (i = ; i <= m; i++) scanf("%s",s[i]+);
for (i = ; i <= m; i++)
{
for (j = ; j <= n; j++)
{
sum[i][j] = s[i][j] - '';
}
}
for (i = ; i <= m; i++)
{
for (j = ; j <= n; j++)
{
sum[i][j] += sum[i-][j] * base1;
}
}
for (i = ; i <= m; i++)
{
for (j = ; j <= n; j++)
{
sum[i][j] += sum[i][j-] * base2;
}
}
power1[] = power2[] = ;
for (i = ; i < m; i++)
{
power1[i] = power1[i-] * base1;
power2[i] = power2[i-] * base2;
}
for (i = a; i <= m; i++)
{
for (j = b; j <= n; j++)
{
t = sum[i][j] - sum[i-a][j] * power1[a] - sum[i][j-b] * power2[b] + sum[i-a][j-b] * power1[a] * power2[b];
insert(t);
}
}
scanf("%d",&q);
while (q--)
{
for (i = ; i <= a; i++) scanf("%s",s[i]+);
for (i = ; i <= a; i++)
{
for (j = ; j <= b; j++)
{
sum[i][j] = s[i][j] - '';
}
}
for (i = ; i <= a; i++)
{
for (j = ; j <= b; j++)
{
sum[i][j] += sum[i-][j] * base1;
}
}
for (i = ; i <= a; i++)
{
for (j = ; j <= b; j++)
{
sum[i][j] += sum[i][j-] * base2;
}
}
if (query(sum[a][b])) printf("1\n");
else printf("0\n");
} return ; }
最新文章
- SQL 通过syscolumns.xtype动态查找指定数据类型字段所包含的数据
- js自执行函数注意事项
- [转载]ArcGIS Engine 中的多线程使用
- IOS创建目录接口createDirectoryAtPath:withIntermediateDirectories:中参数attributes的设置
- 为什么有的代码要用 base64 进行编码
- AIX和Linux中wtmp的不同处理方式
- 批量删除Kindle Personal Documents
- 【Trie】【HDU1247】【Hat’s Wordsfd2】
- css盒模型和块级、行内元素深入理解
- TotoiseSVN基本用法
- win7开启telnet客户端
- Python函数的定义、参数传入与函数的调用
- VMware 安装Linux系统 CentOS
- Java学习之JDBC 2019/3/10
- HBase Snapshot简介
- 2.1 View与ViewGroup的概念
- 数据结构入门之链表(C语言实现)
- win7下PHP+MySQL+CoreSeek中文检索引擎配置
- 对于iOS开发人工智能意味着什么
- java 读写文件例子
热门文章
- 【转】国外程序员整理的 PHP 资源大全
- 如何使windows系统ping通VMware下面的linux系统
- js基础标签用法
- (List)写一个函数reverseList,该函数能够接受一个List,然后把该List&#160;倒序排列。&#160;例如:&#160; List&#160;list&#160;=&#160;new&#160;ArrayList();&#160; list.add(“Hello”);&#160; list.add(“World”);&#160; list.add(“Learn”);&#160;//此时list&#160;为Hello&#160;World&#160;Learn&#160; rever
- 【Linux】tmpfs简介及增加方式
- python 上手
- hibernate 回顾
- MAMP PRO php的session保存在哪里
- wx小程序开发 1:小程序代码构成
- 团体程序设计天梯赛-练习集-L1-038. 新世界