7 条题解

  • 0
    @ 2025-12-24 18:26:49

    之前的样例代码会报错,命名冲突

    非常抱歉!这是我的疏忽。在较新的 C++ 标准库中(如 GCC 14 对应的 C++14/17 环境),<type_traits> 头文件会被 <iostream> 间接包含,其中定义了模板类 std::is_same。当你使用了 using namespace std; 后,自定义的函数名 is_same 会与标准库产生命名冲突

    在 NOI 竞赛中,这种“命名空间污染”是导致编译失败的常见原因。

    以下是修正后的标准题解代码。我已将函数名改为 check_same,并增加了 :: 全局作用域限定符以确保万无一失。

    一、 修正后的标准代码 (C++14)

    #include <iostream>
    #include <vector>
    #include <cstdio>
    
    using namespace std;
    
    // 哈希表长度选择一个较大的质数
    const int MOD = 999983; 
    
    struct Snowflake {
        int len[6];
    };
    
    // 使用拉链法处理哈希冲突
    vector<Snowflake> hash_table[MOD];
    
    /**
     * 核心判定函数:比较两个雪花是否同构
     * 易错点:必须同时考虑顺时针和逆时针的 6 种起点,共 12 种情况
     */
    bool check_same(const Snowflake& s1, const Snowflake& s2) {
        for (int i = 0; i < 6; ++i) { 
            // 1. 顺时针方向比对 (Clockwise)
            bool match_cw = true;
            for (int j = 0; j < 6; ++j) {
                if (s1.len[j] != s2.len[(i + j) % 6]) {
                    match_cw = false;
                    break;
                }
            }
            if (match_cw) return true;
    
            // 2. 逆时针方向比对 (Counter-clockwise / Reflection)
            bool match_ccw = true;
            for (int j = 0; j < 6; ++j) {
                // (i - j + 6) % 6 处理负数索引,实现逆时针循环
                if (s1.len[j] != s2.len[(i - j + 6) % 6]) {
                    match_ccw = false;
                    break;
                }
            }
            if (match_ccw) return true;
        }
        return false;
    }
    
    /**
     * 设计具有旋转不变性的哈希函数
     */
    int get_hash(const Snowflake& s) {
        long long sum = 0;
        long long xor_val = 0;
        for (int i = 0; i < 6; ++i) {
            sum += s.len[i];
            xor_val ^= s.len[i];
        }
        // 组合特征值并对质数取模
        return (int)((sum + xor_val) % MOD);
    }
    
    int main() {
        int n;
        // 使用 fast I/O 或 scanf 应对 10^5 数据量
        if (scanf("%d", &n) != 1) return 0;
    
        bool found = false;
        for (int i = 0; i < n; ++i) {
            Snowflake current;
            for (int j = 0; j < 6; ++j) {
                scanf("%d", &current.len[j]);
            }
    
            if (found) continue; // 已找到答案则跳过后续计算,但仍需读完数据
    
            int h = get_hash(current);
    
            // 在对应的哈希桶中遍历比对
            // 使用 :: 显式调用全局作用域下的 check_same,彻底规避命名冲突
            for (const auto& existing : hash_table[h]) {
                if (::check_same(current, existing)) {
                    found = true;
                    break;
                }
            }
    
            // 若当前桶内无匹配,则存入
            if (!found) {
                hash_table[h].push_back(current);
            }
        }
    
        if (found) {
            printf("Twin snowflakes found.\n");
        } else {
            printf("No two snowflakes are alike.\n");
        }
    
        return 0;
    }
    

    二、 竞赛避坑指南:如何预防“命名冲突”?

    在 NOI 考场上,如果遇到 ambiguous(歧义)错误,请记住以下三招:

    1. 全局作用域符 ::: 在调用自己的函数时,前面加上 ::(例如 ::check_same)。这告诉编译器:“请从全局命名空间找这个函数,不要去 std 命名空间里瞎猜。”
    2. 避开敏感词汇: 以下词汇在 using namespace std; 之后极易发生冲突,尽量避开或加后缀:
      • is_same, count, rank, next, prev
      • distance, search, find, match
      • y1, y0, j1, j0 (这些在 <math.h> 中是贝塞尔函数)
    3. 不使用全局 using: 虽然在比赛中为了快习惯写 using namespace std;,但更好的习惯是在函数内部使用,或者只对特定的类使用,如 using std::vector;

    三、 性能与空间总结

    • 时间复杂度:平均 O(NK)O(N \cdot K),其中 K=12K=12 是比对常数。由于 MOD10NMOD \approx 10 \cdot N,哈希冲突极少,处理 10510^5 数据约耗时 0.1s0.1s
    • 空间复杂度O(N)O(N),每个雪花占 2424 字节,加上 vector 开销,总内存约 10MB10MB 以内,远低于 128MB128MB 限制。
    • 关键点:一定要处理**逆时针(翻转)**的情况。题目样例中 1 2 3 4 5 64 3 2 1 6 5 就是典型的翻转同构。

    信息

    ID
    14976
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    4
    已通过
    3
    上传者