雪花雪花雪花

文章列表

雪花雪花雪花

问题

有 N 片雪花，每片雪花由六个角组成，每个角都有长度。

第 i 片雪花六个角的长度从某个角开始顺时针依次记为 $a_i,_1,a_i,_2,…,a_i,_6$ 。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

例如 $a_i,_1,a_i,_2,…,a_i,_6$ 和 $a_i,_2,a_i,_3,…,a_i,_6$ 就是形状相同的雪花。

$a_i,_1,a_i,_2,…,a_i,_6$ 和 $a_i,_6,a_i,_5,…,a_i,_1$ 也是形状相同的雪花。

我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。

求这 N 片雪花中是否存在两片形状相同的雪花。

输入格式

第一行输入一个整数 NN，代表雪花的数量。

接下来 N 行，每行描述一片雪花。

每行包含 6 个整数，分别代表雪花的六个角的长度（这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到）。

同行数值之间，用空格隔开。

输出格式

如果不存在两片形状相同的雪花，则输出：

No two snowflakes are alike.

如果存在两片形状相同的雪花，则输出：

Twin snowflakes found.

数据范围

1≤N≤100000
0≤ $a_i,_j$ <10000000

输入样例：

2
1 2 3 4 5 6
4 3 2 1 6 5

输出样例：

Twin snowflakes found.

Solve

给你n片6个角的雪花，求n片中是否存在相同形状的雪花。（相同形状指：各自从某一角开始顺时针或逆时针6角相同）。
那么，对每片雪花，6个位置上分别求一次顺序和逆序的组合，然后得到每片雪花的最小组合，最后排序最小组合，如果有相同则说明存在相同形状的雪花，否则无。
例如， 1 2 3 4 5 6 ，我们从第1位，顺取，1 2 3 4 5 6，逆取 1 6 5 4 3 2 ...依次类推到第6位,顺取6 1 2 3 4 5,逆取6 5 4 3 2 1。顺取最小组合为1 2 3 4 5 6，逆取最小组合为1 6 5 4 3 2 ，则最终最小组合为 1 2 3 4 5 6.
那么实际上，就是对正序 1 2 3 4 5 6 ，翻转后的逆序 6 5 4 3 2 1 ，分别求1次最小组合，最后再比较2者的最小组合，得到这片雪花的最小组合。（为了方便操作，我们可以拼接1次。1 2 3 4 5 6 1 2 3 4 5 6，按顺序取即可）

参考代码:

import java.util.*;/*** @ClassName: Main* @Description:* @author: Danbobo* @date: 2023/4/12 16:11*/
public class Main {static Scanner sz= new Scanner(System.in);static Comparator<int[]> cmp1 = new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {int len =o1.length;for (int i = 0 ;i<len;i++){if(o1[i]<o2[i])return -1;else if (o1[i]>o2[i])return 1;}return 0;}};public static void main(String[] args) {int n = sz.nextInt();List<int[]> list =new ArrayList<>();int a[] = new int[6];int b[] = new int[6];for(int i = 0 ;i<n; i++){for(int j = 0,k=5;j<6;j++,k--){int t = sz.nextInt();a[j]=t;b[k]=t;}a = getmin(a);b = getmin(b);if (cmp(a,b) == 1) {list.add(a.clone());}else {list.add(b.clone());}}
//         for (int[] g:list) System.out.println(Arrays.toString(g));Collections.sort(list,cmp1);boolean ok =false;for(int i =1;i<n;i++){if(cmp(list.get(i),list.get(i-1))==0){ok=true;break;}}if (ok) System.out.println("Twin snowflakes found.");else System.out.println("No two snowflakes are alike.");}/** 1 2 3 4 5 6 1 2 3 4 5 6* 6 5 4 3 2 1 6 5 4 3 2 1* */private static int[] getmin(int[] a) {int p[] = new int[12];int tmp[] = new int[6];int res[] = new int[6];for(int i =0;i<12;i++)p[i]=a[i%6];for ( int i = 0 ; i < 6; i++){for ( int k = 0 ;k<6;k++){tmp[k] = p[i+k];}if (i == 0 || cmp(res,tmp)==2) res = tmp.clone();}return res;}private static int cmp (int[] a ,int[] b){for(int i =0;i<6;i++){if(a[i]<b[i])return 1;else if (a[i]>b[i])return 2;}return 0;}}

雪花雪花雪花

问题

输入格式

输出格式

数据范围

输入样例：

输出样例：

Solve

相关问题

公告