HACK & 警示后人
查看原帖
HACK & 警示后人
961972
Lele_Programmer楼主2024/5/17 23:07

本帖主要分为两个部分。

1. HACK

看了讨论区,比如这个: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 了。

2. 正确做法里面的坑(警示后人)

因为讨论区不能写题解,所以这里不说正确做法,但给出几个坑点。

  1. 枚举完每一片雪花所有可能的状态后,才将这些状态添加到 set。

  2. unordered_set 比 set 快,如果 set 超时了,尝试使用 unordered_set。

2024/5/17 23:07
加载中...