AcWing 137. 雪花雪花雪花

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 137. 雪花雪花雪花原题链接困难

作者：

秦淮岸灯火阑珊 , 2019-01-30 20:11:29 , 所有人可见 , 阅读 5136

11

2

题目描述

latex不会写,建议看原版题面.

有N片雪花，每片雪花由六个角组成，每个角都有长度。

第i片雪花六个角的长度从某个角开始顺时针依次记为ai,1,ai,2,…,ai,6。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。

求这N片雪花中是否存在两片形状相同的雪花。

输入格式
第一行输入一个整数N，代表雪花的数量。

接下来N行，每行描述一片雪花。

每行包含6个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。

同行数值之间，用空格隔开。

输出格式
如果不存在两片形状相同的雪花，则输出：

No two snowflakes are alike.

如果存在两片形状相同的雪花，则输出：

Twin snowflakes found.

数据范围
$1≤n≤100000$
$0≤ai,j<10000000$
输入样例：

样例

2
1 2 3 4 5 6
4 3 2 1 6 5
输出样例：
Twin snowflakes found.

hash+空间灵异优化

这道题目空间卡的不得了,出题人用心狠毒,作者我通过不断地减小空间范围,从50~60~100的路上崩溃着.

代码很详细,绝对看得懂

hash其实任意一个hash都可,建议用李煜东老师的算法,精简容易还好做理解.也就是取模大法,记得取模最好要较大的素数,这样错误率低且容易计算.

这道题目主要是要注意,顺时针和逆时针,因为我们可以从任意一个方向动手,所以只要一个顺时针,一个逆时针就好了,过多容易爆掉空间.建议排序进行处理,时间浪费小,脑袋不用想那么多顺序.毕竟sort快排退化也就是N^2,而且这道题目排序也就6个数.不用恐慌

算法大致如此,如果有不懂的地方,欢迎call我.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int K = 99991;
const int N=100000+10;
struct Node
{
    int c[7];
};
int m[N],n,ok,sum;
Node snow[N][10];//如果你写个100,你五十分,如果你写个50,恭喜你加了10分,如果你很疯狂写个20,恭喜你分数不变,如果你破釜沉舟,写个10,恭喜你Ac了,出题人是多么的有趣啊.
bool solve(Node x,Node y) 
{
    sort(x.c+1,x.c+7);//排序有利于身心健康
    sort(y.c+1,y.c+7);
    for(int i=1;i<=6;i++)
    {
        if(x.c[i]!=y.c[i])//只要不一样,就直接退出
            return false;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        sum=0;
        Node now;
        for(int j=1; j<=6; j++)
        {
            scanf("%d",&now.c[j]);
            sum=(sum+now.c[j])%K;//取模运算也就是hash
        }
        for(int j=0; j<m[sum]; j++)//找到所有hash值是一样的雪花,然后每一个判断.
        {
            if(solve(now,snow[sum][j]))//如果这两个雪花一样大小
            {
                ok=1;//如果说hash值不一样,那么肯定不会一样,如果hash值一样,还要判断
                break;
            }
        }
        snow[sum][m[sum]]=now;//我们hash是记录这个值,以链表的方式存储,这里是静态存储,也就是数组模拟链表,我们要知道数据是死,人是活的,出题人是懒的.
        m[sum]++;
        if (ok)
            break;
    }
    if(ok)
        printf("Twin snowflakes found.\n");
    else
        printf("No two snowflakes are alike.\n");
    return 0;
}

24 评论

dennis2013 12个月前

请问，排序以后顺序不就乱套了吗，如果是123456和123465不就不一样了吗

gy2 2020-08-29 14:29

题解交上去都是错的

GRID 2020-12-07 15:06

y总说题目数据加强了

历历乡正趣果 2020-04-01 14:30

大佬为啥能直接排序啊，只要都是 1-6 怎么放不也都可以了，但是题目要求数字必须是相邻的

eeach 2020-03-05 20:24

这道题如果采用unordered_map来替换snow会不会好一些？可能unordered_map的哈希函数会相对好一些

wuxigk 2020-01-21 00:50

你这个hash函数也太水了，放在Codeforces上分分钟被hack掉……

kakazhang 2019-11-20 20:54

请问dalao，segmentation fault 是出什么错了？

kakazhang 2019-11-20 21:00

#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
long long head[13332],next1[100100],value[100100][10],tot=1;
long long h(long long a){
return (a[0]+a[1]+a[2]+a[3]+a[4]+a[5]+a[0]a[1]a[2]a[3]a[4]a[5])%13331;
}
bool equal(long long a,long long b){
sort(a,a+6);
sort(b,b+6);
for(int i=0;i<6;i++){
if(a[i]!=b[i]){
return false;
}
}
return true;
}
bool insertt(long long *a){
long long hash=h(a);
if(head[hash]==0){
next1[tot]=0;
head[hash]=tot;
value[tot][0]=a[0];
value[tot][1]=a[1];
value[tot][2]=a[2];
value[tot][3]=a[3];
value[tot][4]=a[4];
value[tot][5]=a[5];
return false;
}
else{
long long now=head[hash];
while(now){
if(equal(value[now],a)){
return true;
}
now=next1[now];
}
next1[tot]=next1[head[hash]];
head[hash]=tot;
value[tot][0]=a[0];
value[tot][1]=a[1];
value[tot][2]=a[2];
value[tot][3]=a[3];
value[tot][4]=a[4];
value[tot][5]=a[5];
return false;
}
}
long long snow[10];
int main(){
bool c,b=false;
ios::sync_with_stdio(false);
long long n;
cin>>n;
for(int i=0;i[HTML_REMOVED]>snow[i];
}
c=insertt(snow);
if(c){
b=true;
}
}
if(b){
cout<<”Twin snowflakes found.”<<endl;
}
else{
cout<<”No two snowflakes are alike.”<<endl;
}
return 0;
}