雪花雪花雪花
雪花雪花雪花
题目来源
这道题可以在以下几个地方找到
1.acwing137. 雪花雪花雪花 - AcWing题库
2.北大的POJ3349 — Snowflake Snow Snowflakes (poj.org)
3.算法竞赛进阶指南
题目介绍
有 N 片雪花，每片雪花由六个角组成，每个角都有长度。
第 i片雪花六个角的长度从某个角开始顺时针依次记为 ai,1,ai,2,…,ai,6
因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。
例如 ai,1,ai,2,…,ai,6 和 ai,2,ai,3,…,ai,6，ai,1 就是形状相同的雪花。
ai,1,ai,2,…,ai,6和 ai,6,ai,5,…,ai,1 也是形状相同的雪花。
我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。
求这 N 片雪花中是否存在两片形状相同的雪花。
输入格式
第一行输入一个整数 N，代表雪花的数量。
接下来 N 行，每行描述一片雪花。
每行包含 6 个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。
同行数值之间，用空格隔开。
输出格式
如果不存在两片形状相同的雪花，则输出：
No two snowflakes are alike.如果存在两片形状相同的雪花，则输出：
Twin snowflakes found.数据范围
1≤N≤100000
0≤ai,j<10000000
输入样例：
2
1 2 3 4 5 6
4 3 2 1 6 5输出样例：
Twin snowflakes found.题目分析
一开始，我是这么分析的，我先找到6个数字的最小值，然后从最小值开始按照题目的顺序找到一个顺序，然后再把这个顺序的雪花倒过来找到第二个顺序，然后对于这两个顺序的雪花构成一个哈希值，最后再判断是否存在两个哈希值一样的数，如果存在，那么就输出yes，反之no
但是，通过实践后看了一些测试数据才发现(acwing的数据几乎半公开)，在题目上并没有说明数字不可以重复，这就导致了测试数据中包含有明明不是一个雪花，但是哈希值计算是一样的，经过2天的思考(看题解)，才发现了字符串表示的最小值这么个方法，由于雪花只有6瓣，数据较少，可以直接枚举找到每一个雪花的字符串的最小表示，找到最小表示后，再全部加入到一个二维数组里面，然后，整个二维数组里面的所有数据就是每一个雪花的最小表示，然后对整个二位数组进行排序，然后一个一个比较，有匹配的就输出yes，反之则no
首先，给出基础的库函数和初始定义
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
//snows用来存储所有的雪花，idx用来方便排序
int snows[N][6], idx[N];然后，我们把创建两个数组，分别保存雪花的正向和反向数据，比如说，我们有3 2 1 4 5 6这个雪花，我们先不排序，直接把3 2 1 4 5 6和6 5 4 1 2 3这两个顺序存进两个数组里面，然后用一个函数分别计算出正向雪花和反向雪花的最小表示，然后对这两个最小表示取最小值加入snows数组里面
int main()
{
int n;
cin >> n;
//两个数组保存正向和反向
int snow[6], isnow[6];
for(int i = 0;i < n;i++) {
for(int j = 0, k = 5;j < 6;j++, k--) {
cin >> snow[j];
isnow[k] = snow[j];
}
//得到两种雪花方向的最小值
get_min(snow);
get_min(isnow);
//比较
if(cmp2(snow, isnow)) memcpy(snows[i], snow, sizeof(snow));
else memcpy(snows[i], isnow, sizeof(isnow));
//便于数组排序进行记数
idx[i] = i;
}
}最后，我们把数组进行排序，然后依次比较，如果发现匹配的就输出结果
sort(idx, idx + n, cmp);
for(int i = 1;i < n;i++) {
if(!cmp(idx[i - 1], idx[i]) && !cmp(idx[i], idx[i - 1]))
{
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;函数介绍
好了，上面我们已经介绍了这道题的大致框架，现在我们来写一下在框架中出现的比较函数
首先，是函数1 get_min
void get_min(int *b) {
//定义一个静态数组
static int a[12];
//把b数组里面的值写两遍放到a数组里面, 便于分析
for(int i = 0;i < 12;i++) a[i] = b[i % 6];
//定义两个指针i, j通过指针来寻找字符串的最小表示
int i = 0,j = 1, k;
while(i < 6 && j < 6) {
//排除重复
for(k = 0;k < 6 && a[i + k] == a[j + k];k++);
//直接匹配
if(k == 6) break;
//i一定不是最小的了
if(a[i + k] > a[j + k]) {
i += k + 1;
if(i == j) i++;
}
//j一定不是最小的了
else {
j += k + 1;
if(i == j) j++;
}
}
//取到最小值，对应的就是最小表示
k = min(i, j);
//刷新原来的数组
for(int i = 0;i < 6;i++) b[i] = a[i + k];
}下面，我来介绍一下字符串的最小表示法，也就是对上述函数的算法解释。
就是说，给定我们一个字符串，要我们找到这个字符串里面的最小字典序对应的顺序，比如说这么一个数3 2 1 4 5 6,它有一下几种顺序
3 2 1 4 5 6
2 1 4 5 6 3
1 4 5 6 3 2
4 5 6 3 2 1
5 6 3 2 1 4
6 3 2 1 4 5相信大家已经看出来了，第三行的1 4 5 6 3 2就是这个字符串的最小表示法，那么我们该怎么在O(n)的时间里面求出来这个最小的呢
一开始，我们先把这个字符串*2，写两遍，放指针i和j
i
3 2 1 4 5 6 3 2 1 4 5 6
j
3 2 1 4 5 6 3 2 1 4 5 6我们先来比较i和j两个指针，i指针对应的字符串是3 2 1 4 5 6，j指针对应的字符串是2 1 4 5 6 3，我们对比第一个字符就可以发现，i指针对应的字符串一定不是最小字符串，它的首位数就比j的要大了，所以我们就对应的把i加1，欸，这下i和j的位置相同了，这样是不可以的，因为我们现在找到的j字符串是最小的，那么为了继续找下去，我们要把i再往右移动一格，i到1的位置上，变成这样
i
3 2 1 4 5 6 3 2 1 4 5 6
j
3 2 1 4 5 6 3 2 1 4 5 6现在，我们继续匹配，发现i对应的字符串比j的小，现在我们按照第一种情况，把j移动两格，变成这样
i
3 2 1 4 5 6 3 2 1 4 5 6
j
3 2 1 4 5 6 3 2 1 4 5 6现在我们看得出来，i对应的一定是最小的了,后面的循环就是j一直往后走，走到while循环结束，然后，我们得到了i和j对应的位置,一个是2，一个是6，我们找到最小的那个，也就是2，那么2的位置开始，把这段字符串赋给原来的b数组，那么b数组就是最小表示了，上面的k是用来防止有重复数字的，如果有重复数字的话，就用k先去重，然后再判断即可
接下来，是函数2，cmp2
bool cmp2(int a[], int b[]) {
for(int i = 0;i < 6;i++) {
if(a[i] < b[i]) return true;
else if(a[i] > b[i]) return false;
}
return false;
}这个函数很好理解，就是依次比较字符串的每一位，遇到不同的就开始判断
最后，是函数3，cmp
bool cmp(int a, int b) {
for(int i = 0;i < 6;i++) {
if(snows[a][i] < snows[b][i]) return true;
else if(snows[a][i] > snows[b][i]) return false;
}
return false;
}这个函数就体现出来一开始的idx函数的妙用了，我们用idx记录每一个位置，然后我们用idx进行比较，放在cmp里面就是指对应的数组的位置了，其次，判断是否相同的方法也很巧妙，我们进行两次cmp判断
if(!cmp(idx[i - 1], idx[i]) && !cmp(idx[i], idx[i - 1]))如果两个都成立，那就说明第一个大于等于第二个，第二个大于等于第一个，那么就只可能是第二个和第一个相等，那么就可以找到符合的一对字符串了
这样，我们就可以解决这道题了，注意，上述方法只能在acwing里面过，在poj上的数据输入较大，需要把cin和cout换成scanf和printf才可以过
写在最后
这是蒟蒻第一次写题解，由于第一次写，所以不是很懂应该怎么样才可以写出一个比较好的，可以让更多人理解的题解，所以我还需要不断地努力，不断刷题，得到更多的思路，写出更多让大家可以理解清晰的题解！
如果大家有什么不是很理解的地方，或者说有写的有问题的地方还烦请告知本蒟蒻(qq1594463152)
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int snows[N][6], idx[N];
void get_min(int *b)
{
static int a[12];
for(int i = 0;i < 12;i++) a[i] = b[i % 6];
int i = 0, j = 1, k;
while(i < 6 && j < 6) {
for(k = 0;k < 6 && a[i + k] == a[j + k];k++);
if(k == 6) break;
if(a[i + k] > a[j + k]) {
i += k + 1;
if(i == j) i++;
}
else {
j += k + 1;
if(i == j) j++;
}
}
k = min(i, j);
for(i = 0;i < 6;i++) b[i] = a[i + k];
}
bool cmp(int a, int b)
{
for(int i = 0;i < 6;i++) {
if(snows[a][i] < snows[b][i]) return true;
else if(snows[a][i] > snows[b][i]) return false;
}
return false;
}
bool cmp2(int a[], int b[]) {
for(int i = 0;i < 6;i++) {
if(a[i] < b[i]) return true;
else if(a[i] > b[i]) return false;
}
return false;
}
int main()
{
int n;
cin >> n;
int snow[6], isnow[6];
for(int i = 0;i < n;i++) {
for(int j = 0, k = 5;j < 6;j++, k--) {
cin >> snow[j];
isnow[k] = snow[j];
}
get_min(snow);
get_min(isnow);
if(cmp2(snow, isnow)) memcpy(snows[i], snow, sizeof(snow));
else memcpy(snows[i], isnow, sizeof(isnow));
idx[i] = i;
}
sort(idx, idx + n, cmp);
for(int i = 1;i < n;i++) {
if(!cmp(idx[i - 1], idx[i]) && !cmp(idx[i], idx[i - 1]))
{
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;
}
