hrbust2300

hrbust2300

下雪啦

Time Limit: 4000 MS Memory Limit: 32768 KB

64-bit integer IO format: %lld , %llu Java class name: Main

[Submit] [Status] [Discuss]

Description

陈月亮最喜欢的季节就是冬天了，这不看着窗外飘起了雪花，陈月亮开心的跑出屋来看雪。但是迷迷糊糊的陈月亮不知道自己是在做梦还是真的下起了雪。突然她想起了一句话，在真实世界中是没有两片一样的雪花的。于是你的任务就是比较这场雪中的所有雪花，如果出现了两朵完全一致的雪花，则证明陈月亮是在梦中。

每朵雪花用六个整数表示，范围在（1 – 10000000）之间，表示雪花六个花瓣的长度，六个整数的先后出现顺序可能是顺时针顺序也可能是逆时针顺序，并且可能是从任意一个花瓣开始的。比如说对同一个花瓣，描述方法可能是1 2 3 4 5 6 或者 4 3 2 1 6 5

Input

第一行为一个整数T，表示有T组测试数据。

每组测试数据第一行为一个整数N(0 < N <= 100000),表示雪花的数目。

接下来n行每行六个整数，描述一朵雪花。

Output

如果没有相同的雪花，输出“No two snowflakes are alike.”，否则输出“Twin snowflakes found.”

Sample Input

1

2

1 2 3 4 5 6

4 3 2 1 6 5

Sample Output

Twin snowflakes found.

本题是一道典型的数字哈希，用直接枝叶之和mod 9000作为key值，再用vector数组写个拉链即可！！！注意判断是否相同时，应该是有两个方向，并且6个不同顺序进行判断。最后注意每个vector应该是在每个情况里面的，这样避免写.clear()，不同的t会把vector直接清空.（忘记清空。。。逃）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
const int maxn=9000;
using namespace std;
int snow[100001][6];
bool same(int a,int b)
{for (int i=0; i<6; i++){if ((   snow[a][0] == snow[b][i]     &&snow[a][1] == snow[b][(i+1)%6]  &&snow[a][2] == snow[b][(i+2)%6]  &&snow[a][3] == snow[b][(i+3)%6]  &&snow[a][4] == snow[b][(i+4)%6]  &&snow[a][5] == snow[b][(i+5)%6] )||(snow[a][0] == snow[b][i] &&snow[a][1] == snow[b][(i+5)%6]  &&snow[a][2] == snow[b][(i+4)%6]  &&snow[a][3] == snow[b][(i+3)%6]  &&snow[a][4] == snow[b][(i+2)%6]  &&snow[a][5] == snow[b][(i+1)%6]))return true;}return false;
}
int main()
{int n;int t;scanf("%d",&t);while (t--){int flag=0;scanf("%d",&n);for (int i=0; i<n; i++){for (int j=0; j<6; j++){scanf("%d",&snow[i][j]);}}int sum,key;vector<int>hashs[maxn+5];for (int i=0; i<n; i++){sum=0;for (int j=0; j<6; j++){sum+=snow[i][j];}key=sum % maxn;int s=hashs[key].size();for(int j=0; j<hashs[key].size(); j++){if (same(hashs[key][j],i)){flag=1;break;}}if(flag)break;hashs[key].push_back(i);}if (flag==0)printf("No two snowflakes are alike.\n");else printf("Twin snowflakes found.\n");}return 0;
}