雪花雪花雪花
题目 雪花雪花雪花
思路分析
本来又想故技重施 用find偷懒
但是发现雪花的数目不止2个
它给出n片雪花 问有没有两片是同构的
如果用find的话 得把每个都翻倍 然后每个都对其他n-1个进行find 显然不现实
那这里就很明显得用最小表示法了
把所有的雪花的最小表示法求出来
然后看有没有两片相同
注意有顺时针还有逆时针 不仅得顺序做一遍最小表示法 还得翻转过来 再做一次
然后对于这片雪花取的是俩者的更小值
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int snows[N][6],idx[N];
int n;
bool cmp_array(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;
}
bool cmp(int a, int b)
{
return cmp_array(snows[a],snows[b]);
}
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)
{
k=0;
while( k < 6 && a[i + k] == a[j + k])
k++;
if (k == 6)
break;
if (a[i + k] > a[j + k])
i += k + 1;
else
j += k + 1;
if (i == j)
j ++ ;
}
k = min(i, j);
for (i = 0; i < 6; i ++ )
b[i] = a[i + k];
}
int main()
{
cin>>n;
int snow[6], isnow[6];//顺时针 逆时针
for (int i = 0; i < n; i ++ )
{
for (int j = 0, k = 5; j < 6; j ++, k -- )
{
scanf("%d", &snow[j]);
isnow[k] = snow[j];
}
get_min(snow);//正着取一遍最小表示法
get_min(isnow);//逆着也取一遍
//结果取更小的
if (cmp_array(snow, isnow))
memcpy(snows[i], snow, sizeof snow);
else
memcpy(snows[i], isnow, sizeof isnow);
idx[i] = i;
}
//因为不好直接两两相比 所以排好序后 两两比（如果有相同的肯定是临近的）
//二维不太好排序 所以用idx存好索引 根据索引来排序
sort(idx, idx + n, cmp);
for (int i = 1; i < n; i ++ )
{
//cmp得到的是小于 加个！意味着大于等于
//若i-1大于等于i 且 i大于等于i-1 表示i=i-1
if (!cmp(idx[i], idx[i - 1]) && !cmp(idx[i - 1], idx[i]))
{
puts("Twin snowflakes found.");
return 0;
}
}
puts("No two snowflakes are alike.");
return 0;
}
💬 评论