7 条题解
-
0
之前的样例代码会报错,命名冲突
非常抱歉!这是我的疏忽。在较新的 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", ¤t.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(歧义)错误,请记住以下三招:- 全局作用域符
::: 在调用自己的函数时,前面加上::(例如::check_same)。这告诉编译器:“请从全局命名空间找这个函数,不要去std命名空间里瞎猜。” - 避开敏感词汇:
以下词汇在
using namespace std;之后极易发生冲突,尽量避开或加后缀:is_same,count,rank,next,prevdistance,search,find,matchy1,y0,j1,j0(这些在<math.h>中是贝塞尔函数)
- 不使用全局
using: 虽然在比赛中为了快习惯写using namespace std;,但更好的习惯是在函数内部使用,或者只对特定的类使用,如using std::vector;。
三、 性能与空间总结
- 时间复杂度:平均 ,其中 是比对常数。由于 ,哈希冲突极少,处理 数据约耗时 。
- 空间复杂度:,每个雪花占 字节,加上
vector开销,总内存约 以内,远低于 限制。 - 关键点:一定要处理**逆时针(翻转)**的情况。题目样例中
1 2 3 4 5 6和4 3 2 1 6 5就是典型的翻转同构。
- 全局作用域符
信息
- ID
- 14976
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 4
- 已通过
- 3
- 上传者