Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

C++是wa,G++是AC,而且我的mark没用,但是删了就会超时,试试啊

Posted by liyuweihuo at 2016-04-26 20:06:20 on Problem 1204
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<set>
#pragma comment(linker,"/STACK:102400000,102400000")
#define lowbit(i) (i) & (-i) 
#define LL long long
#define sqr(a) ((a)*(a))
#define MOD 1000000007
#define lson(step) step<<1
#define rson(step) step<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const LL INF=9223372036854775807;
const int M=100000+5;
char Map[1000+5][1000+5];
int l,c,w;
int dis[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int da[1000+5][3],mark[1000+5];
char ss[1000+5][1000+5];
typedef struct node
{
	node *next[26],*fail;
	int num;
	void init()
	{
		for(int i=0;i<26;i++)
		next[i]=NULL;
		fail=NULL;
		num=0;
	}
}tree;
tree *root;
void insert(char s[],int num)
{
	int l=strlen(s);
	tree *nownode=root;
	for(int i=0;i<l;i++)
	{
		if(nownode->next[s[i]-'A']==NULL)
		{
			nownode->next[s[i]-'A']=new tree;
			nownode->next[s[i]-'A']->init();
			nownode=nownode->next[s[i]-'A'];
		}
		else
		nownode=nownode->next[s[i]-'A'];
	}
	nownode->num=num;
}
void getfail()
{
	tree *son,*temp,*p=root;
	queue<tree *>q;
	q.push(p);
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			son=temp->next[i];
			if(son!=NULL)
			{
				if(temp==root)
				son->fail=root;
				else
				{
					p=temp->fail;
					while(p)
					{
						if(p->next[i])
						{
							son->fail=p->next[i];
							break;
						}
						p=p->fail;
					}
					if(p==NULL)
					son->fail=root;
				}
				q.push(son);
			}
		}
	}
}
int ok(int X,int Y)
{
	if(X>=0&&Y>=0&&X<l&&Y<c)
	return 1;
	return 0;
}
void quetion(int NUM,int I,int ii,int X,int Y)
{
	da[NUM][0]=X+(ii)*dis[I][0]-strlen(ss[NUM])*dis[I][0];
	da[NUM][1]=Y+(ii)*dis[I][1]-strlen(ss[NUM])*dis[I][1];
	da[NUM][2]=I;
}
void Query(char s[],int I,int X,int Y)
{
	int l=strlen(s);
	tree *p=root,*temp;
	for(int i=0;i<l;i++)
	{
		while(p!=root&&!p->next[s[i]-'A'])
		p=p->fail;
		p=p->next[s[i]-'A'];
		if(!p)
		p=root;
		temp=p;
		while(temp!=root)
		{
			if(temp->num)
			{
				quetion(temp->num,I,i+1,X,Y);
				mark[temp->num]=1;
			}
			else
			break;
			temp=temp->fail;
		}
	}
}
void query(int X,int Y)
{
	int l;
	char s[1000];
	for(int i=0;i<8;i++)
	{
		int xx=X,yy=Y;
		l=0;
		while(ok(xx,yy))
		{
			s[l++]=Map[xx][yy];
			xx+=dis[i][0],yy+=dis[i][1];
		}
		s[l]='\0';
	    Query(s,i,X,Y);
	}
}
int deal(tree* T)
{
    int i;
    if(T==NULL)
    return 0;
    for(i=0;i<26;i++)
    {
        if(T->next[i]!=NULL)
        deal(T->next[i]);
    }
    free(T);
   return 0;
}
int main()
{
	while(~scanf("%d%d%d",&l,&c,&w))
	{
		memset(mark,0,sizeof(mark));
		root=new tree;
		root->init();
		for(int i=0;i<l;i++)
		scanf("%s",Map[i]);
		for(int i=1;i<=w;i++)
		{
			scanf("%s",ss[i]);
			insert(ss[i],i);
		}
		getfail();
		for(int i=0;i<l;i++)
		{
		query(i,0);
		query(i,c-1);
	    }
	    for(int i=0;i<c;i++)
	    {
	    	query(0,i);
	    	query(l-1,i);
		}
		for(int i=1;i<=w;i++)
		printf("%d %d %c\n",da[i][0],da[i][1],da[i][2]+'A');
		deal(root);
	}
	return 0;
 } 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator