题解 SP4354 【TWINSNOW - Snowflakes】

2021-01-09 13:30

阅读:718

标签:链式前向星   push   com   namespace   href   ||   vector   数组   顺时针   

首先友情提醒一下,搬题目的放漏了这题样例其实就是

input
2
1 2 3 4 5 6
4 3 2 1 6 5
output
Twin snowflakes found.

这题我做的很窝火,终于AC了,写篇题解添加点成就感。。。


一开始我以为是简单题,打算先找到每朵雪花中最小的数,顺时针逆时针都算一下,找字典序最小的

然后愉快WA0。因为一个雪花的手臂长度可能有相同的,比如什么1 2 1 3 1 6这种,我的想法就炸了。


那怎么找到一个唯一的表示方法呢?

最小表示法,不知道的可以看P1368

工艺的题解中这篇较详细

最小表示法有了,接下来咋办?不能用普通数组记录是否访问过,因为数据范围太大了。

有人会说hash。但是那太麻烦了其实是我不会

懒人标配:mapmp;

(pos是存雪花六个手臂的结构体)

struct pos{
	int a[10];
}snow[N];

太棒了!我们成功了!

以下是在洛谷AC代码,1.42s,我最多只能把它优化到1.05s。POJ无法AC,所以代码下面我会给出另一个稍有不同方法。

#include
using namespace std;
typedef long long ll;
#define debug printf("*");
//#define mo 1e9+7
#define inf 1e9+7
int n;
bool flag;
struct pos{
	int a[10];
	bool operator xx.a[i];
		}
		return a[6]>xx.a[6];
	}
};
mapmp;
int main(){
	scanf("%d",&n);
	for(int i=1;io[it2+l]) it1=it1+l+1;
			else it2=it2+l+1;
			if(it1==it2) it2++;
		}
		ans=min(it1,it2);
		pos x,y;
		for(int j=ans;jo2[it2+l]) it1=it1+l+1;
			else it2=it2+l+1;
			if(it1==it2) it2++;
		}
		ans=min(it1,it2);
		for(int j=ans;j1||mp[y]>1) flag=1;
	}
	if(flag) printf("Twin snowflakes found.\n");
	else printf("No two snowflakes are alike.\n");
	return 0;
}

兴高采烈地去老师的比赛提交——TLE*3

POJ机子很慢,4s时限我洛谷跑1.42s还过不去

咋办?都怪map常数大,那就换掉。

哈希?不太会。弄个简单版的。

int clac(pos emm){
	int sum=0;
	for(int i=1;i

雪花手臂之和%99991即可。

为什么要取99991?因为接近n的大小。

哈希之后可能会碰撞,所以我们要把clac值相同的给存起来,遇到有相同的就看看是不是真的相等。

别的题解用的是链式前向星,但是我喜欢STL,所以用了vector,会慢一些。

下面这个代码洛谷780msAC,POJ3829ms,vjudge上是3907ms

(我也不知道为什么vjudge和poj差了一点

#include
#include
#include
using namespace std;
//const int N=,mo=;
//#define inf
//#define long long ll
const int mo=99991,N=100010;
int hs[mo+10],n;
struct pos{
	int a[10];
}snow[N];
vectorvec[mo+10]; 
int ok(pos al,pos ar){
	for(int i=1;iar.a[i]) return -1;
		if(al.a[i]o[it2+l]) it1=it1+l+1;
			else it2=it2+l+1;
			if(it1==it2) it2++;
		}
		ans=min(it1,it2);
		pos x,y;
		for(int j=ans;jo2[it2+l]) it1=it1+l+1;
			else it2=it2+l+1;
			if(it1==it2) it2++;
		}
		ans=min(it1,it2);
		for(int j=ans;j

题解 SP4354 【TWINSNOW - Snowflakes】

标签:链式前向星   push   com   namespace   href   ||   vector   数组   顺时针   

原文地址:https://www.cnblogs.com/zdsrs060330/p/13095085.html


评论


亲,登录后才可以留言!