最小表示法

有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.

最小表示法

#include <bits/stdc++.h>
#pragma GCC optimize(3 , "Ofast" , "inline")
using namespace std ;
const int N = 1e5 + 10 ;
int id[N] , snows[N][10] , n ; 
bool cmp_carry(int a[] , int b[])
{
    for(int i = 0 ;i < 6 ;i ++) 
     if(a[i] > b[i]) 
      return false ;
     else if(a[i] < b[i])
      return true ;
    return false ;
}
bool cmp(int a  , int b)
{
    return cmp_carry(snows[a] , snows[b]) ; 
}
int getmin(int *a)
{
    static int b[12] ;
    for(int i = 0 ;i < 12 ;i ++) b[i] = a[i % 6] ;
    int i = 0 , j = 1 , k ;
    while(i < 6 && j < 6) 
     {
         for(k = 0 ;k < 6 && b[j + k] == b[i + k] ; k ++)  ;
         if(k == 6) break ;
         if(b[i + k] > b[j + k]) 
           {
               i += k + 1 ;
               if(i == j) i ++ ;
           }
         if(b[i + k] < b[j + k])
          {
              j += k + 1 ;
              if(i == j) j ++ ;
          }
     }
     k = min(i , j) ;
     for(int i = 0 ; i < 6 ;i ++) 
      a[i] = b[i + k] ;
     return 0 ;
}
int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(!isdigit(ch)) { if(ch == '-') f = -1 ; ch = getchar() ;} 
    while(isdigit(ch)) x = x * 10 + ch - 48 , ch = getchar() ;
    return x * f ;
}
int main()
{
    scanf("%d" , &n) ;
    int isnow[6] , snow[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] ;
         getmin(snow) ;
         getmin(isnow) ;
         if(cmp_carry(snow , isnow)) memcpy(snows[i] , snow , sizeof snow) ;
         else memcpy(snows[i] , isnow , sizeof isnow) ;
         id[i] = i ;
     }
    sort(id , id + n , cmp) ;
    int flag = 0 ;
    for(int i = 1; i < n ; i ++) 
      if(!cmp(id[i] , id[i - 1]) && !cmp(id[i - 1] , id[i])) 
       {
           flag = 1; 
           break ;
       }
     if(flag) puts("Twin snowflakes found.") ;
     else puts("No two snowflakes are alike.") ;
    return 0 ;
}
/*


*/

最小表示法

推荐阅读