这题一点也不简单, 需要提前知道最小表示法,主要也考察最小表示法:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n;
int snows[maxn][6];
int idx[maxn];
bool cmp_arr(int a[], int b[]) //比较两个数组字典序大小,a大于b返回false b大于a返回false ,如果两个数组一样false
{
for(int i = 0; i < 6; i ++)
{
if(a[i] > b[i]) return false;
if(a[i] < b[i]) return true;
}
return false;
}
void get_min(int a[]) //得到最小表示,我是百度搜的模板 自己改的
{
int len = 6;
int b[12];
for(int i = 0; i < len*2; i ++)
{
b[i] = a[i%len];
}
int i = 0, j = 1, k = 0;
while(i < len && j < len && k < len)
{
int t = a[(i+k)%len]-a[(j+k)%len];
if(t == 0) k ++;
else
{
if(t < 0) j = max(j+k+1,i +1);
else i = max(i+k+1, j +1);
k = 0;
}
}
int z = min(i, j);
for(int i = 0; i < 6; i ++)
{
a[i] = b[i+z];
}
}
bool cmp(int a, int b) //比较两个数组字典序大小, 二维数组
{
return cmp_arr(snows[a],snows[b]);
}
int main()
{
scanf("%d",&n);
int snow[6], fan_snow[6];
for(int i = 0; i < n; i ++)
{
for(int j = 0, k = 5; j < 6; j ++, k --)
{
scanf("%d",&snow[j]);
fan_snow[k] = snow[j]; //正向与反向
}
get_min(snow);
get_min(fan_snow);
if(cmp_arr(snow,fan_snow)) //无论正反, 把最小的一个放入snows数组中
{
for(int j = 0; j < 6; j ++)
{
snows[i][j] = snow[j];
}
}
else
{
for(int j = 0; j < 6; j ++)
{
snows[i][j] = fan_snow[j];
}
}
idx[i] = i; //二维数组排序不好排序,用一个索引来代替二维数组
}
sort(idx, idx+n, cmp); //利用索引 排序
bool flag = false;
for(int i = 1; i < n; i ++)
{
if(!cmp_arr(snows[idx[i-1]],snows[idx[i]]) && ! cmp_arr(snows[idx[i]],snows[idx[i-1]]))
//从头开始遍历,因为已经排完序了,如果有字典序一样的则一定相邻,我们比较前后就可知道是否有相同
{
flag = true;
}
}
if(flag) puts("Twin snowflakes found."); //如果存在相同的雪花
else puts("No two snowflakes are alike.");
return 0;
}