poj 3349 snowflake snow snowflakes 序号排序.txt

NUAA ACM OJ源码

//POJ 3349 Snowflake Snow Snowflakes 序号排序
/*
输入
2
1 2 3 4 5 6
4 3 2 1 6 5

输出：
Twin snowflakes found.
*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;

#define NMAX 100005
#define MAX 10000005

typedef struct xuehua
{	//如果排序时需要传入数组参数，可以将数组写成一个结构体，结构体里套一个数组，像这样
	int shu[6];
}xuehua;

xuehua shuru[NMAX];
xuehua xu1[NMAX];
xuehua xu2[NMAX];
int cixu[NMAX];

bool cmin(int a,int b)
{
	return a<b;
}

bool cmout(int a,int b)
{	//通过序号比较数组
	int i;
	for(i=0;i<6;i++) 
	{
		if(xu1[a].shu[i]<xu1[b].shu[i]) return true;
		if(xu1[a].shu[i]>xu1[b].shu[i]) return false;
	}
	return true;
}

bool cmouttt(xuehua xua,xuehua xub)
{	//通过数组比较数组
	int i;
	for(i=0;i<6;i++) 
	{
		if(xua.shu[i]<xub.shu[i]) return true;
		if(xua.shu[i]>xub.shu[i]) return false;
	}
	return true;
}

bool is_same(xuehua xua,xuehua xub)
{
	int i;
	for(i=0;i<6;i++) if(xua.shu[i]!=xub.shu[i]) return false;
	return true;
}

void get_bz(int num)
{
	int i,j,m,min,minnum,k1,k2,k11,k22,k;
	int mintemp;
	xuehua temp[12];

	for(i=0;i<num;i++)
	{
/*		//这段错误代码不删去，提醒自己，注意一个雪花中出现2个最小数的情况
		min=MAX;
		for(j=0;j<6;j++) 
		{
			if(min>shuru[i].shu[j]) {min=shuru[i].shu[j];minnum=j;}
		}
		j=minnum;
		k1=((minnum-1)+6)%6;k2=(minnum+1)%6;
		k11=k1;k22=k2;
		xu1[i].shu[0]=min;
		if(shuru[i].shu[k1]==shuru[i].shu[k2])
		{
			k1=((k1-1)+6)%6;
			k2=(k2+1)%6;
		}
		if(shuru[i].shu[k1]<shuru[i].shu[k2]) 
		{
			for(j=k11,m=1;m<6;m++,k11=((k11-1)+6)%6) xu1[i].shu[m]=shuru[i].shu[k11];
		}
		else 
			for(j=k22,m=1;m<6;m++,k22=((k22+1)%6)) xu1[i].shu[m]=shuru[i].shu[k22];
*/
		for(j=0;j<6;j++)
		{//起始位置
		 //向左走，向右走
			for(k=j,m=0;m<6;m++,k=(k+1)%6) temp[2*j].shu[m]=shuru[i].shu[k];
			for(k=j,m=0;m<6;m++,k=((k-1)+6)%6) temp[2*j+1].shu[m]=shuru[i].shu[k];
		}
		xu1[i]=temp[0];
		for(j=1;j<12;j++) if(cmouttt(temp[j],xu1[i])==true) xu1[i]=temp[j];
	}
}

bool solve(int num)
{
	int i,j;
	get_bz(num);
	//注意，这里的排序是针对序号，这样快排时只要交换2个数就可以了
	//若排序针对数组的话，会超时
	for(i=0;i<num;i++) cixu[i]=i;
	sort(cixu,cixu+num,cmout);
	for(i=1;i<num;i++)
	{
		if(is_same(xu1[cixu[i-1]],xu1[cixu[i]])==true) return true;
	}
	return false;
}

int main()
{
	int num,i,j;
	int aa;
	char c;
	scanf("%d",&num);
	for(i=0;i<num;i++)
	{
		for(j=0;j<6;j++)
		{	//用scanf会超时
			aa=0;
			c=getchar();
			while(c<'0'||c>'9') c=getchar();
			while(c>='0'&&c<='9')
			{
				aa=aa*10+c-'0';
				c=getchar();
			}
			shuru[i].shu[j]=aa;
		}
	}
	if(solve(num)==true) cout<<"Twin snowflakes found."<<endl;
	else cout<<"No two snowflakes are alike."<<endl;
	return 0;
}