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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

判断雪花是否相同,其实也不难,翻转和移动 6次 就能判断出来。

Posted by tangguojun at 2017-09-27 23:57:41 on Problem 3349
#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
struct node{
  int data[6];
  int sum;	
};
node A[100000];
bool cmp(node a,node b)
{
	if(a.sum<b.sum)
	  return true;
    else 
      return false;
}

void move(int t[])
{
  int temp=t[0];
  t[0]=t[1];
  t[1]=t[2];
  t[2]=t[3];
  t[3]=t[4];
  t[4]=t[5];
  t[5]=temp; 
} 
void turned(int t[])
{//1---5 swap
  int t1=t[1];
  t[1]=t[5];
  t[5]=t1;
  //2----4 swap
  int t2=t[2];
  t[2]=t[4];
  t[4]=t2; 
} 
 
bool isthesame(int t1[],int t2[])
{
   for(int i=0;i<6;i++)
    if(t1[i]!=t2[i])
	  return false;

   return true; 
} 
bool same(int i,int j) 
{
	//find min
	int temp1[6],temp2[6],temp3[6],temp4[6]; 
	int min_index=0;
	for(int k=0;k<6;k++)
	  {temp3[k]=temp1[k]=A[i].data[k];
	   temp4[k]=temp2[k]=A[j].data[k];
	  }
	 sort(temp1,temp1+6);
	 sort(temp2,temp2+6);
	 for(int k=0;k<6;k++)
	 {
	 	if(temp1[k]!=temp2[k])
		  return false;
		   
	 } 
	 
	 //构成的数字都相同
	 //逐个比较
	 int cnt=0;
	  while(cnt<6)
	  {  if(!isthesame( temp3,temp4))
	        { turned(temp3) ;
	          if(!isthesame( temp3,temp4))
	           { turned(temp3) ;
			    move(temp3);
	           }
			  else 
			    return true ;
	        }
         else
           return true;
           cnt++;
	  }
	 return false;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d%d%d",&A[i].data[0],&A[i].data[1],&A[i].data[2],&A[i].data[3],&A[i].data[4],&A[i].data[5]);
		A[i].sum=A[i].data[0]+A[i].data[1]+A[i].data[2]+A[i].data[3]+A[i].data[4]+A[i].data[5];
	}
	sort(A,A+n,cmp);
	
	int start=0 ;
	while(start<n)
	{   int target=A[start].sum;
	    int end=-1;
		for(int i=start;i<n;i++)
		{
			if(A[i].sum!=target)
		       { 
       			end=i-1;
       			break;
       		}
		}
		  
		if(end==-1)
		 end=n-1;//[start,end]有无相同雪花
		if(start<end)//2以上 
		{
		   for(int j=start;j<end;j++)
		      {
		      	for(int k=j+1;k<=end;k++)
				  {
				  	if(same(j,k))
					  {
					     printf("Twin snowflakes found.\n");
						 return 0; 
					  } 
				  }
		      }
		}
 
		start=end+1;
		  
		   
		
	}
	printf("No two snowflakes are alike.\n"); 
	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