大家好,欢迎来到IT知识分享网。
题目
有N片雪花,每片雪花由六个角组成,每个角都有长度。
第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6。
因为雪花的形状是封闭的环形,所以从任何一个角开始顺时针或逆时针往后记录长度,得到的六元组都代表形状相同的雪花。
例如ai,1,ai,2,…,ai,6和ai,2,ai,3,…,ai,6,ai,1就是形状相同的雪花。
ai,1,ai,2,…,ai,6和ai,6,ai,5,…,ai,1也是形状相同的雪花。
我们称两片雪花形状相同,当且仅当它们各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。
求这N片雪花中是否存在两片形状相同的雪花。
输入格式
第一行输入一个整数N,代表雪花的数量。
接下来N行,每行描述一片雪花。
每行包含6个整数,分别代表雪花的六个角的长度(这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到)。
同行数值之间,用空格隔开。
输出格式
如果不存在两片形状相同的雪花,则输出:
No two snowflakes are alike.
如果存在两片形状相同的雪花,则输出:
Twin snowflakes found.
数据范围
1≤n≤100000
0≤ai,j<10000000
这个题目我们可以将具有相同特征的雪花保存在一个邻接表中。
那么这道题目,我们可以采用雪花长度之和+雪花长度之积 并取于p。作为每个雪花的特征值。然后比较相同特征值的雪花是否完全一样即可。
#include"stdio.h"
#include"string.h"
#include"vector"
#include"algorithm"
using namespace std;
#define p 99991
typedef long long ll;
int n;
ll a[100100][8];
vector<ll> Q[99993];
int euqul(int x,int y)
{
int flag = 0;
for(int i = 0; i <= 5; i ++)//i = 偏移量
{
int k,j;
for( k = 0,j = 0; k < 6; k ++,j ++)
{
if(a[x][k] != a[y][(j + i)%6])
break;
}
if(k == 6) return 1;
}
for(int i = 0;i <= 5; i ++)
{
int k ,j;
for(k = 0,j = 5; k < 6; k ++,j --)
{
if(a[x][k] != a[y][(j + i)%6])
break;
}
if(k == 6) return 1;
}
return 0;
}
int main()
{
scanf("%d",&n);
int mark = 0;
for(int i = 1; i <= n; i ++)
{
ll s = 0,s1 = 1;
for(int j = 0; j < 6; j ++)
{
scanf("%lld",&a[i][j]);
s = s + (ll)a[i][j];
s1 *= (ll)a[i][j];
s %= p;
s1 %= p;
}
if(mark == 1)
continue;
s += s1;
s1 = s % (ll)p;
for(int j = 0; j < Q[s1].size(); j ++)
if(euqul(i,Q[s1][j]))
{
mark = 1;
break;
}
if(mark == 0)
Q[s1].push_back(i);
}
if(mark == 1)
printf("Twin snowflakes found.\n");
else
printf("No two snowflakes are alike.\n");
return 0;
}
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/28443.html