题目描述
邻接矩阵通常用于表示图的连接情况,其中矩阵的元素表示节点之间的连接关系。在这个问题中,你所说的 “邻接矩阵不能取0” 似乎是指在哈希表中,将 h 数组初始化为 0 的问题。
在一些情况下,将 h 数组初始化为 0 是没有问题的,但在这个特定的问题中,我们需要使用 -1 来表示链表的末尾,因为在 insert 函数中,我们使用 h[hval] 作为链表的头。如果我们将 h 数组初始化为 0,我们无法区分哪些元素是链表的开头,哪些是链表的末尾。
因此,为了确保链表的正确性,我们将 h 数组初始化为 -1。这样,在 insert 函数中,我们就可以通过检查 h[hval] 是否为 -1 来确定链表是否为空。
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int ne[N], h[N], idx = 0, snow[N][6];
int n;
const int HashVal = 99991;
int hasha(int *x) {
int sum = 0, mul = 1;
for (int i = 0; i < 6; i++) {
sum = (sum + x[i]) % HashVal;
mul = (1LL * mul * x[i]) % HashVal;
}
return (sum + mul) % HashVal;
}
bool cleck(int *a, int *b) {
for (int i = 0; i < 6; i++) {
bool flag = true;
for (int j = 0; j < 6; j++) {
for(int k =0;k<6;k++){
if(a[(i+k)%6]!=b[(j+k)%6])flag = false;
}
if(flag)return 1;
flag = true;
for(int k = 0;k<6;k++){
if(a[(i+k)%6]!=b[(j-k+6)%6])flag = false;
}
if(flag)return 1;
}
}
return false;
}
bool insert(int *x) {
int hval = hasha(x);
for (int i = h[hval]; ~i; i = ne[i]) {
if (cleck(snow[i], x)) {
return true;
}
}
// idx ++; // 先 ++ idx 因为(1)
for (int i = 0; i < 6; i++) {
snow[idx][i] = x[i];
}
ne[idx] = h[hval];
h[hval] = idx++;
return false;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i++) {
int x[6];
for (int j = 0; j < 6; j++) {
cin >> x[j];
}
if (insert(x)) {
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;
}
/*
*/
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla