题解：P10467 [CCC 2007] Snowflake Snow Snowflakes

· · 题解

这道题问是否存在：与另一个串或反串循环同构的串。当然一片雪花的六个角分别是六个整体。

What is 循环同构？a b c d 和 c d a b 就是。把前缀 a b 放在了最后。

反串是什么？就是把一个串倒过来。这道题比如 12 3 4 56 的反串视为 56 4 3 12。12、3、4 和 56 看作 4 个整体。

看样例就能看出来吧……

然后代码很好写。只需要把给出的六个角依次放在第一个位置上，但要保证相对位置不变或者全部反过来。

时间复杂度是线性的。

注意要放入的是正倒序的最小字典序，这样避免自己与自己比较。

#include <bits/stdc++.h>
using namespace std;

unordered_map <string, int> mp;
string a[7];
int n;

string add(int st, int dis) { //st开始位置，dis偏移量 
    string s = ""; int i = st;
    do {
        s += a[i] + ' ';
        i = (i + dis + 5) % 6 + 1; // (i+dis+6-1)%6+1 的化简。既保证了 i 不为负数，又不取到 0（最小为 1）
    } while (i != st);
    return s;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 6; j++) cin >> a[j];
        string ms = "999999"; // 记录最小字典序
        for (int j = 1; j <= 6; j++) ms = min({ms, add(j, -1), add(j, 1)});
        if (mp[ms] ++) { // 说明之前有可能相同的雪花，直接结束程序
            cout << "Twin snowflakes found.";
            exit(0);
        }
    }
    cout << "No two snowflakes are alike.";
}

还有什么不懂的可以发在评论区哦。