Snowflake Snow Snowflakes
| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions: 43504 | Accepted: 11411 |
Description
You may have heard that no two snowflakes are alike. Your task is to write a program to determine whether this is really true. Your program will read information about a collection of snowflakes, and search for a pair that may be identical. Each snowflake has six arms. For each snowflake, your program will be provided with a measurement of the length of each of the six arms. Any pair of snowflakes which have the same lengths of corresponding arms should be flagged by your program as possibly identical.
Input
The first line of input will contain a single integer n, 0 < n ≤ 100000, the number of snowflakes to follow. This will be followed by n lines, each describing a snowflake. Each snowflake will be described by a line containing six integers (each integer is at least 0 and less than 10000000), the lengths of the arms of the snow ake. The lengths of the arms will be given in order around the snowflake (either clockwise or counterclockwise), but they may begin with any of the six arms. For example, the same snowflake could be described as 1 2 3 4 5 6 or 4 3 2 1 6 5.
Output
If all of the snowflakes are distinct, your program should print the message:
No two snowflakes are alike.
If there is a pair of possibly identical snow akes, your program should print the message:
Twin snowflakes found.
Sample Input
2
1 2 3 4 5 6
4 3 2 1 6 5
Sample Output
Twin snowflakes found.
Source
- 可以每次对于一个输入查询之前的雪花中是否有相同的
- 但是难点在于题目不保证雪花输入的方向和起点我们只能枚举
- 如果On枚举。。。还是算了吧
- 但是这里出了枚举好像也没有其他的办法了，因为我们没法定义一种对于雪花长短的一种排列方式使得通过这种排序在map中实现对于相同类型雪花的一个聚集效果
- 所以还是要在枚举上下功夫
- 显然两个完全一致的雪花各个花瓣之和相等
- 这里花瓣长度之和如果不加处理是不能用数组存的（好吧，做完题发现其实是可以用map来存，但是我们这里练hash）
- 我们对于sumi用素数p来进行hash，将对p取模结果相同的雪花合并为一类存储起来
- 进行比较的过程中就减少了枚举的个数
- 之后就是朴素的对于每一种可能性的检测，枚举起点和顺逆
- 这里需要以后注意的一点是对于hash结果的存放最好用vector，不要用数组，数组可能爆内存
- 说实在的，后来看看好像离散化后map存下也是可以的？
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL ;
typedef unsigned long long ULL ;
const int maxn = + ;
const int inf = 0x3f3f3f3f ;
const int npos = - ;
const int mod = 1e9 + ;
const int mxx = + ;
const double eps = 1e- ;
const double PI = acos(-1.0) ; int n, ans;
int c[maxn][], b[maxn];
int use[maxn];
std::vector<int> v[maxn];
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%d",&n)){
ans=;
memset(use,,sizeof(use));
for(int i=;i<=n;i++){
int sum=;
for(int j=;j<;j++){
scanf("%d",&c[i][j]);
sum+=c[i][j];
}
sum%=;
b[i]=sum;
if(!use[sum]){
v[sum].clear();
}
use[sum]=;
v[sum].push_back(i);
if(!ans){
int sz=v[sum].size();
if(sz>){
for(int j=;j<sz;j++){
int idx=v[b[i]][j];
if(i!=idx){
int e, f, st;
if(!ans){
for(st=;st<;st++){
for(e=,f=st;e<;e++,f=(f++)%)
if(c[i][e]!=c[idx][f])
break;
if(e==)
ans=;
}
}
if(!ans){
for(st=;st<;st++){
for(e=,f=st;e<;e++,f=(f-+)%)
if(c[i][e]!=c[idx][f])
break;
if(e==)
ans=;
}
}
}
if(ans)
break;
}
}
}
}
puts(ans?"Twin snowflakes found.":"No two snowflakes are alike.");
}
return ;
}
