AcWing 雪花雪花雪花
题目：
- 全是Latex，懒得打，详见
题解：
- 哈希表 / 字符串哈希。
- 因为题目中要比较六元组太花时间了！每比价一次需要O(6 * 6)，所以复杂度就是O(n ^ 2)。那么哈希表的思想的就是将一个复杂的状态表示为一个简单状态（通常是一个数），然后比较这个数下的链表中是否有相等的东西，有就意味着两个东西相等。那么这样复杂度就是一个预处理的复杂度 + O(N)（理想情况）。那怎么样将复杂状态转换成一个数呢？就要通过哈希函数。通常哈希函数的写法因人而异，写法各种玄学。因为反正使冲突机率低就好了。
这题的正解是将每片雪花Hash成一个数，然后检查在这个数下的链表中是否有相同的雪花。为什么不能直接比较哈希值是否相等，因为此题中顺序也是相等的条件之一！
- 我，懒人。所以不想写链表什么的。于是便用了字符串哈希。字符串哈希的思想是将一个字符串哈希成一个值，比较哈希值是否相等即可判断俩字符串是否相等。那么顺序对其哈希值是有影响的！所有这题把6个数当成一个字符串处理就好。这样就直接用哈希值判断俩雪花是否相等。
具体就是先找到6个数中的最大值所在位置，向左/右拓展得到两个哈希值（正着看和逆着看），最终哈希值取俩哈希值中的min。然后用排序检索的方法判相等。
#include#include #include #define N 100005#define ull unsigned long longusing namespace std;int n;ull v1, v2;int t[7];ull a[N];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x; }int main(){ cin >> n; for(int i = 1; i <= n; i++) { int val = -1, pos; v1 = v2 = 0; for(int j = 1; j <= 6; j++) t[j] = read(); for(int j = 1; j <= 6; j++) if(t[j] > val) val = t[j], pos = j; for(int j = pos; j <= 6; j++) v1 = v1 * 131 + t[j]; for(int j = 1; j < pos; j++) v1 = v1 * 131 + t[j]; for(int j = pos; j >= 1; j--) v2 = v2 * 131 + t[j]; for(int j = 6; j > pos; j--) v2 = v2 * 131 + t[j]; a[i] = min(v1, v2); } sort(a + 1, a + 1 + n); for(int i = 1; i < n; i++) if(a[i] == a[i + 1]) {cout << "Twin snowflakes found."; return 0;} cout << "No two snowflakes are alike."; return 0;}
- 但其实，这种方法有可能会GG… …
- 就是如果数据中出现重复的最大值且位置不一样的话，就有可能会GG。自己yy便知为啥。
- 幸运的是，就是这样跑到了AC。（逃，懒得改
更新：
- 嘛学了字符串哈希“最小表示法”这个技巧后，发现上文我提到的玄学办法其实本质思想就是“最小表示法”（只是写法不够优秀罢了）。
- 最小表示法就是对于一个字符串，可以将它的最后一位放到第一位来，依次类推，一共有n种变形串。在这n种变形串中字典序最小的那个串，用来代表这个串。
- 最小表示法有啥用咧，比如判断两个环是否相等。由于可以起点可以从环的任意一点开始，所以就要判断很多次，哈希很多次。那么这时最小表示法即可用一种情况表示这个环。
- 那么此题就是这样做，正着找一次最小表示串，反着找一次最小表示串，最终一个串的哈希值取两个最小表示串的哈希值的min。
#include#include #include #define N 100005#define ull unsigned long longusing namespace std;int n;int a[15];ull f[N];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int getPos(int a[]){ int it1 = 1, it2 = 2, k; while(it1 <= 6 && it2 <= 6) { k = 0; while(k < 6 && a[it1 + k] == a[it2 + k]) k++; if(k == 6) break; if(a[it1 + k] > a[it2 + k]) { it1 += k + 1; if(it1 == it2) it1++; } else { it2 += k + 1; if(it1 == it2) it2++; } } return min(it1, it2);}int main(){ cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= 6; j++) a[j] = read(), a[j + 6] = a[j]; ull v1 = 0, v2 = 0; int s1 = getPos(a); for(int j = s1; j <= s1 + 6 - 1; j++) v1 = v1 * 131 + a[j]; for(int j = 1; j <= 6; j++) swap(a[j], a[12 - j + 1]); int s2 = getPos(a); for(int j = s2; j <= s2 + 6 - 1; j++) v2 = v2 * 131 + a[j]; f[i] = min(v1, v2); } sort(f + 1, f + 1 + n); for(int i = 1; i < n; i++) if(f[i] == f[i + 1]) { cout << "Twin snowflakes found."; return 0; } cout << "No two snowflakes are alike."; return 0;}