题解 SP4354 【TWINSNOW - Snowflakes】
2021-01-09 13:30
标签:链式前向星 push com namespace href || vector 数组 顺时针 首先友情提醒一下, 这题我做的很窝火,终于AC了,写篇题解添加点成就感。。。 一开始我以为是简单题,打算先找到每朵雪花中最小的数,顺时针逆时针都算一下,找字典序最小的 然后愉快WA0。因为一个雪花的手臂长度可能有相同的,比如什么1 2 1 3 1 6这种,我的想法就炸了。 那怎么找到一个唯一的表示方法呢? 最小表示法,不知道的可以看P1368 工艺的题解中这篇较详细 最小表示法有了,接下来咋办?不能用普通数组记录是否访问过,因为数据范围太大了。 有人会说hash。但是那太麻烦了 懒人标配:map (pos是存雪花六个手臂的结构体) 太棒了!我们成功了! 以下是在洛谷AC代码,1.42s,我最多只能把它优化到1.05s。POJ无法AC,所以代码下面我会给出另一个稍有不同方法。 兴高采烈地去老师的比赛提交——TLE*3 咋办?都怪map常数大,那就换掉。 哈希?不太会。弄个简单版的。 雪花手臂之和%99991即可。 为什么要取99991?因为接近n的大小。 哈希之后可能会碰撞,所以我们要把clac值相同的给存起来,遇到有相同的就看看是不是真的相等。 别的题解用的是链式前向星,但是我喜欢STL,所以用了vector,会慢一些。 下面这个代码洛谷780msAC,POJ3829ms,vjudge上是3907ms 题解 SP4354 【TWINSNOW - Snowflakes】 标签:链式前向星 push com namespace href || vector 数组 顺时针 原文地址:https://www.cnblogs.com/zdsrs060330/p/13095085.html搬题目的放漏了这题样例其实就是input
2
1 2 3 4 5 6
4 3 2 1 6 5
output
Twin snowflakes found.
其实是我不会。struct pos{
int a[10];
}snow[N];
#include
POJ机子很慢,4s时限我洛谷跑1.42s还过不去int clac(pos emm){
int sum=0;
for(int i=1;i
(我也不知道为什么vjudge和poj差了一点#include
文章标题:题解 SP4354 【TWINSNOW - Snowflakes】
文章链接:http://soscw.com/index.php/essay/41175.html