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

能通过的hash基本都可以构造数据卡掉??

Posted by ACAccepted at 2019-02-11 22:47:29 on Problem 3349
In Reply To:这题有问题,正解会超时,能通过的hash基本都可以构造数据卡掉 Posted by:HIT_TOM at 2018-02-09 20:28:04
#include <cstdio>
using namespace std;

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=1200010;
const int MAXH=1200007;
int n,id;
bool flag=false; 
int num[2][12];

struct memory
{
	int num[6],nx;
}get_num[MAXN];
int head[MAXH];

int get_hash(int num[],int loca)
{
	int res=0;
	for (int i=0;i<6;i++)res+=num[loca+i];
	return res%MAXH;
}

bool cmp(int a[],int loca,int b[])
{
	for (int i=0;i<6;i++)if (a[i+loca]!=b[i])return false;
	return true;
}

void cpy(int a[],int loca,int b[])
{
	for (int i=0;i<6;i++)b[i]=a[i+loca];
}

void insert(int save[],int loca,int Hash_code)
{
	id++;cpy(save,loca,get_num[id].num);get_num[id].nx=head[Hash_code];
	head[Hash_code]=id;
}

bool find(int num[],int loca)
{
	int code=get_hash(num,loca);
	for (int k=head[code];k>0;k=get_num[k].nx)
		if (cmp(num,loca,get_num[k].num))return true;
	insert(num,loca,code);
	return false;
}

int main()
{
	n=read();
	while (n--)
	{
		for (int i=0;i<6;i++)
		{
			num[0][i]=read();
			num[0][i+6]=num[0][i];
		}
		if (flag)continue;
		for (int i=0;i<6;i++)num[1][i]=num[1][i+6]=num[0][5-i];
		for (int i=0;i<6;i++)
		{
			if (find(num[0],i)||find(num[1],i))
			{
				flag=true;break;
			}
		}
	}
	printf("%s\n",flag?"Twin snowflakes found.":"No two snowflakes are alike.");
	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