注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2462][BeiJing2011]矩阵模板  

2014-11-22 16:21:50|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2462: [BeiJing2011]矩阵模板

白书上的例题。。
用STL无限MLE
双倍经验:BZOJ2351
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int N = 1000+10;
const int HN = 6e5+10;
int n,m,na,ma;
char mat[N][N],str[N];
int ans[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
int hn;
struct list{
list(){next =NULL;d=0;}
list *next;short d;
void push(short);
//~list();
}lh[HN];
queue<list*>pupa;
list *newlist(){
if(hn < HN){lh[hn]=list();return &lh[hn++];}
return new list();
}
void list::push(short a){
list *l = newlist();d++;
l->next = next;next = l;
l->d = a;
}
struct Node{
Node(){ch[0] = ch[1] = NULL;end.next=NULL;}
//deque<short>end;
list end;
Node *fail,*ch[2],*last;
}house[HN];
Node *newNode(){
if(hn < HN){house[hn]=Node();return &house[hn++];}
return new Node();
}
queue<Node*>dui;
struct AC{
Node *ROOT;
AC(){ROOT=newNode();ROOT->fail=ROOT->last=ROOT;}
void clear(){hn=0;AC();}
void insert(char str[],int bh){
Node *r = ROOT;
int len = strlen(str+1);
for(int i=1;i<=len;i++){
if(!('0'<=str[i] && str[i]<='1'))break;
int c = str[i]-'0';
if(!r->ch[c]){r->ch[c]=newNode();}
r=r->ch[c];
}r->end.push(bh);
}
void makefail(){
for(int i=0;i<=1;i++)
if(ROOT->ch[i]){
ROOT->ch[i]->fail=ROOT->ch[i]->last = ROOT;
dui.push(ROOT->ch[i]);
}else ROOT->ch[i] = ROOT;
while(!dui.empty()){
Node *r = dui.front();dui.pop();
for(int i=0;i<=1;i++)
if(r->ch[i]){
Node *l = r->fail;
while(l->ch[i]==ROOT && l!=ROOT)l=l->fail;
r->ch[i]->fail = l->ch[i];
r->ch[i]->last = l->ch[i]->end.next?l->ch[i]:l->ch[i]->last;
dui.push(r->ch[i]);
}else r->ch[i] = r->fail->ch[i];
}
}
void count(Node *r,int x,int y){
while(r->end.next){
for(list *i=r->end.next;i!=NULL;i=i->next){
int k = i->d;
if(x-k +1>=1)ans[x-k +1][y-ma+1]++;
}
r = r->last;
}
}
}ac;
void find(char s[],int x){
int len = m;
Node *r = ac.ROOT;
for(int i=1;i<=len;i++){
if(!('0'<=s[i] && s[i]<='1'))break;
int c = s[i]-'0';
r = r->ch[c];
if(r->end.next)ac.count(r,x,i);
else ac.count(r->last,x,i);
}
}
void print(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)printf("%d ",ans[i][j]);
printf("\n");
}
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;char cc;
n = scan();m = scan();
na = scan();ma = scan();
for(i=1;i<=n;i++){
scanf("%s",mat[i]+1);
//printf("%s\n",mat[i]+1);
}
int nn = scan();
while(nn--){
ac.clear();
for(i=1;i<=na;i++){
scanf("%s",str+1);
ac.insert(str,i);
}

ac.makefail();
//printf("[%d]",ac.ROOT->ch[1]->ch[1]->end.d);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
ans[i][j]=0;
for(i=1;i<=n;i++){
find(mat[i],i);
}
short ok=0;
//print();
for(i=1;i<=n&&!ok;i++)
for(j=1;j<=m&&!ok;j++)
if(ans[i][j] == na){ok=1;break;}
printf("%d\n",ok);
//clear
if(nn)
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
ans[i][j]=0;
}
return 0;
}


题解:
AC自动机。
把每个小矩阵拆成一行一行加到AC自动机里,然后每次匹配就把cot[左上角]++
最后检查有没有一个位置的cot等于小矩阵的行数。
因为一个节点可能是多个行的结尾,所以结束节点需要存多个值,一开始我用的STL的队列,结果不知道为啥无限MLE,改成自己手写的链表之后300M->30M
为了快速找到上一个结尾,需要设一个被称作suffix link的last指针,保存上一个末尾节点、
之前写的时候都没有读过白书……现在好好重新学了一下。
Update:
程序里有个严重的问题……两个内存池用了同一个变量作为指针
不过只会导致内存浪费,不会WA,所以就不改了。。

另外:
如果写矩阵哈希的话这两道题有一道可以过(据说)
然后如果写暴力KMP搞常数好像也可以过,而且速度和我写的AC自动机差不多。。

下面是我8月份写的T掉的hash
改成单关键字+自然溢出可能能过,懒得改了……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000+5;
const long long MAXINT = 1LL<<31;
int n,m,n1,m1;
typedef short Matrix[N][N];
Matrix map;
int lin[N][N];
int pow(int x,int k){
int re=1;
for(;k;k/=2,x=x*x)
if(k&1)re=re*x;
return re;
}
struct Hash{
int h[4],c[4],P[4];
int hash[N][N];
Hash(){h[1]=31;h[2]=57;c[1]=3721;c[2]=7397;P[1]=1000000007;P[2]=959759777;}
void preset(){
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
hash[i][j]=hash[i][j-1]*h[1]+map[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
hash[i][j]=hash[i-1][j]*c[1]+hash[i][j];
}
int calc(int y0,int x0){
x0--;y0--;int x1=x0+m1,y1=y0+n1;
int re=0,l;
re=hash[y1][x1]-hash[y0][x1]*pow(c[1],n1);
l=hash[y1][x0]-hash[y0][x0]*pow(c[1],n1);
re=re-l*pow(h[1],m1);
return re;
}
}hash;
int main(){
int i,j,k;
//freopen("input.txt","r",stdin);
scanf("%d%d%d%d",&n,&m,&n1,&m1);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
char cc=' ';
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='1')map[i][j]=1;
else map[i][j]=0;
}
hash.preset();
int l,nn;scanf("%d",&nn);
for(int ii=1;ii<=nn;ii++){
for(i=1;i<=n1;i++)
for(j=1;j<=m1;j++){
char cc=' ';
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='1')l=1;else l=0;
lin[i][j]=lin[i][j-1]*hash.h[1]+l;

}
for(i=1;i<=n1;i++)
for(j=1;j<=m1;j++)
lin[i][j]=lin[i-1][j]*hash.c[1]+lin[i][j];
bool ok=0;
for(i=1;i<=n-n1+1&&!ok;i++)
for(j=1;j<=m-m1+1&&!ok;j++){
int a = lin[n1][m1], b=hash.calc(i,j);
if(a<0)a = a+MAXINT;
if(b<0)b = b+MAXINT;
if(a==b){ok=1;break;}
}
if(ok)printf("1\n");else printf("0\n");
}
return 0;
}


  评论这张
 
阅读(209)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017