• 雪花雪花雪花


    /*
     * Project: 0x14_Hash
     * File Created:Monday, January 18th 2021, 10:21:24 am
     * Author: Bug-Free
     * Problem:AcWing 137. 雪花雪花雪花
     */
    #include
    #include
    #include
    #include

    #define ll long long

    using namespace std;

    const int N = 1e5 + 10, P = 1e5 + 3;

    int n, a[6], b[6];

    struct S {
        int s[6];
    };

    vector snow[N];

    int H() {  //设计Hash函数
        int s = 0, k = 1;
        for (int i = 0; i < 6; i++) {
            (s += a[i]) %= P;      //和
            k = (ll)k * a[i] % P;  //积
        }
        return (s + k) % P;  // 和与积相加
    }

    bool judge() {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                bool v = 1;
                for (int k = 0; k < 6; k++) {
                    if (a[(i + k) % 6] != b[(j + k % 6)]) {
                        v = 0;
                        break;
                    }
                }
                if (v) {
                    return true;
                }
                v = 1;
                for (int k = 0; k < 6; k++) {
                    if (a[(i + k) % 6] != b[(j - k + 6) % 6]) {
                        v = 0;
                        break;
                    }
                }
                if (v) {
                    return true;
                }
            }
        }
        return false;
    }

    bool insert() {
        int h = H();  //获取Hash值
        for (unsigned int i = 0; i < snow[h].size(); i++) {
            memcpy(b, snow[h][i].s, sizeof b);
            if (judge()) {
                return true;
            }
        }
        S s;
        memcpy(s.s, a, sizeof(s.s));
        snow[h].push_back(s);
        return 0;
    }

    int main() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 6; j++) {
                cin >> a[j];
            }
            if (insert()) {
                cout << "Twin snowflakes found." << endl;
                return 0;
            }
        }
        cout << "No two snowflakes are alike." << endl;
        return 0;
    }

  • 相关阅读:
    C++ 中生成随机数的代码
    知识图谱增强的KG-RAG框架
    面试突击88:加入事务和嵌套事务有什么区别?
    java毕业设计仓库管理系统mybatis+源码+调试部署+系统+数据库+lw
    java基于ssm的共享快递盒管理系统
    LRU算法 vs Redis近似LRU算法
    linux系统安装 -----Centos 8 64位
    【App自动化测试】(十五)手机浏览器(webview)自动化测试
    计算机毕设(附源码)JAVA-SSM基于的校园疫情防控管理
    Python3 函数式编程
  • 原文地址:https://blog.csdn.net/tesla_shy/article/details/139562860