本帖主要分为两个部分。
看了讨论区,比如这个:https://www.luogu.com.cn/discuss/822458 他的思路是将雪花的六个长度进行 set 去重,然后看看有没有重复。而我一开始的思路是,对雪花的六个长度进行排序,然后看看有没有重复,代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n;
set< vector<int> > st;
bool cmp(const int& a,const int& b) {
return a<b;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i) {
vector<int> a;
for (int j=1;j<=6;++j) {
int v;
scanf("%d",&v);
a.push_back(v);
}
sort(a.begin(),a.end(),cmp);
if (st.find(a)!=st.end()) {
puts("Twin snowflakes found.");
return 0;
}
st.insert(a);
}
puts("No two snowflakes are alike.");
return 0;
}
然而,这种思路貌似是错的,比如下面这组数据:
2
1 2 3 4 5 6
1 2 3 4 6 5
正确输出应为:
No two snowflakes are alike.
这两片雪花并不相同,不能通过翻转或者是更换枚举的起点而得到。
而上方引用的帖子和上面我自己的代码均输出了错误的结果。
然而,这两份代码都 AC 了。
因为讨论区不能写题解,所以这里不说正确做法,但给出几个坑点。
枚举完每一片雪花所有可能的状态后,才将这些状态添加到 set。
unordered_set 比 set 快,如果 set 超时了,尝试使用 unordered_set。