题解：P10467 [CCC 2007] Snowflake Snow Snowflakes

Fish_and_Chips_ · 2024-12-20 18:50:54 · 个人记录

校内模拟出了这道题，赛时想出一种非常好想且好写的做法，出来看了一圈题解区发现居然没有，遂写此题解。

这里提供一种思路非常简单的基于字符串拼接的写法。

首先，因为雪花每个角的长度小于 10000000，所以我们先把每个数后面添加字符补齐到 7 位，方便后面的字符串拼接。

对于每个雪花，我们枚举起点，并将 6 条边的数拼接为一个长的字符串，并对这个字符串进行标记。后续的雪花中如果再次出现这个字符串那么就找到了一样的雪花。不难发现这样操作不可能出现冲突。

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
string a[N][6], d1 = "Twin snowflakes found.", d2 = "No two snowflakes are alike.", s;
string tmp, rec[N];
unordered_map <string, bool> g;

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i) 
        for (int j = 0; j < 6; ++j) {
            cin >> a[i][j];
            while (a[i][j].size() < 8) //加字符补齐至7位
                a[i][j] += '$';
        }

    for (int i = 1; i <= n; ++i) {
        int en = 0;
        for (int st = 0; st < 6; ++st) { //枚举起点
            s = "";
            for (int u = 0; u < 6; ++u)
                s += a[i][(st + u) % 6]; //拼接字符串

            if (g[s]) {
                cout << d1;
                return 0;
            }
            rec[++ en] = s;
        }

        for (int st = 0; st < 6; ++st) {
            s = "";
            for (int u = 5; u >= 0; --u)
                s += a[i][(st + u) % 6];

            if (g[s]) {
                cout << d1;
                return 0;
            }
            rec[++ en] = s;
        }

        for (int i = 1; i <= en; ++i) g[rec[i]] = 1; //记录已出现过的串
    }

    cout << d2;

    return 0;
}

时间复杂度 O(n)，非常好写，缺点是字符串运算常数较大。