注意:本文转载于:https://www.cnblogs.com/BigYellowDog/p/11343477.html
题目描述
blablabla
样例
blablabla
算法1
(字符串哈希) $O(n^2)$
因为题目中要比较六元组太花时间了!每比价一次需要O(6 * 6),所以复杂度就是O(n ^ 2)。那么哈希表的思想的就是将一个复杂的状态表示为一个简单状态(通常是一个数),然后比较这个数下的链表中是否有相等的东西,有就意味着两个东西相等。那么这样复杂度就是一个预处理的复杂度 + O(N)(理想情况)。那怎么样将复杂状态转换成一个数呢?就要通过哈希函数。通常哈希函数的写法因人而异,写法各种玄学。因为反正使冲突机率低就好了。
这题的正解是将每片雪花Hash成一个数,然后检查在这个数下的链表中是否有相同的雪花。为什么不能直接比较哈希值是否相等,因为此题中顺序也是相等的条件之一!
我,懒人。所以不想写链表什么的。于是便用了字符串哈希。字符串哈希的思想是将一个字符串哈希成一个值,比较哈希值是否相等即可判断俩字符串是否相等。那么顺序对其哈希值是有影响的!所有这题把6个数当成一个字符串处理就好。这样就直接用哈希值判断俩雪花是否相等。
具体就是先找到6个数中的最大值所在位置,向左/右拓展得到两个哈希值(正着看和逆着看),最终哈希值取俩哈希值中的min。然后用排序检索的方法判相等。
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100005
#define ull unsigned long long
using 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。(逃,懒得改)
算法2
(最小表示法)
嘛学了字符串哈希“最小表示法”这个技巧后,发现上文我提到的玄学办法其实本质思想就是“最小表示法”(只是写法不够优秀罢了)。
最小表示法就是对于一个字符串,可以将它的最后一位放到第一位来,依次类推,一共有n种变形串。在这n种变形串中字典序最小的那个串,用来代表这个串。
最小表示法有啥用咧,比如判断两个环是否相等。由于可以起点可以从环的任意一点开始,所以就要判断很多次,哈希很多次。那么这时最小表示法即可用一种情况表示这个环。
那么此题就是这样做,正着找一次最小表示串,反着找一次最小表示串,最终一个串的哈希值取两个最小表示串的哈希值的min。
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100005
#define ull unsigned long long
using 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;
}
注意:本文转载于:https://www.cnblogs.com/BigYellowDog/p/11343477.html