题目描述

有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片雪花中是否存在两片形状相同的雪花。

样例

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

算法1

(正反最小表示+排序) $O(nlogn)$

y神思路，改了一点，求出每个序列的正反最小表示，如 4 5 6 1 2 3 最小表示为 1 2 3 4 5 6 逆序为 3 2 1 6 5 4
最小表示为 1 6 5 4 3 2 可以容易证明正反的最小表示都是唯一的。
然后正反的最小表示都能够对应唯一的雪花，同样的雪花具有相同的正反最小表示

C++ 代码

typedef unsigned long long ull;
const int M=100010;
int snows[M*2+10][6];
ull mod=(1<<64)-1;
int p=13331;
/*
 *得到哈希值
 */
ull get_hash(int a[]){
  //用字符串哈希
  ull res=1;
  for(int i=0;i<6;i++){
    res=(res*p+a[i])%mod;
  }
  return res;
}
/*
 * 得到最小表示  依然有问题
 */
void to_min(int a[]){
    for(int i=0;i<6;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
  int b[12]; //展开环
 for(int i=0;i<12;i++){
     b[i]=a[i%6];
 }
 //技巧 复杂度降到O(n)
 int i=0,j=1;
 for(;i<6&&j<6;){  //i和j都小于6 超过6之后必有重复
   if(b[i]>b[j]){ //i开头不能成为最小表示
      i++;
      if(i==j)i++;
   }else if(b[i]<b[j]){//j开头不能成为最小表示
      j++;
      if(i==j)j++;
   }else {
       int k=0;
       while(b[i+k]==b[j+k]&&k<6) k++;
       if(k<6){
       if(b[i+k]>b[j+k]){
         i+=(k+1);
       }else{
         j+=(k+1);
       }
       }else{ //整个序列都是相同的 所以随便从哪开始
         break;
       }
   }
 }
 if(i>j){ //j为最小
    memcpy(a,b+j,6*4);
 }else{
   memcpy(a,b+i,6*4);
 }
  cout<<"更新后"<<endl;
   for(int i=0;i<6;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
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 true;
}
int idx[M*2+10];
void solution2(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
         for(int j=0;j<6;j++){
         cin>>snows[i][j];
         snows[i+n][5-j]=snows[i][j];
       }
        to_min(snows[i]);
         to_min(snows[i+n]);
         idx[i]=i;
         idx[i+n]=i+n;
    }
    sort(idx,idx+2*n,cmp);
    for(int i=0;i<2*n-1;i++){
      if(cmp(idx[i],idx[i+1])&&cmp(idx[i+1],idx[i])){
        cout<<"Twin snowflakes found."<<endl;
        return ;
      }
    }
    cout<<"No two snowflakes are alike."<<endl;
}

算法2

(正反表示加哈希) $O(n)$

这个挺简单的 自己看吧 hash函数用的字符串哈希，然后注意就是正反表示可能哈希值相同需要判断一下

C++ 代码

void solution1(){
   unordered_set<ull> s; //查询O(1) 储存哈希值 如果有两个哈希一样的说明重复
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
         int tmp[6];
         for(int j=0;j<6;j++){
         cin>>snows[i][j];
         tmp[5-j]=snows[i][j];
        }
        // 正反最小表示
         to_min(snows[i]);
         to_min(tmp);
        // 储存哈希
          ull k1=get_hash(snows[i]),k2=get_hash(tmp);
          cout<<k1<<" "<<k2<<endl;
         if(s.find(k1)!=s.end()){
            cout<<"Twin snowflakes found."<<endl;
            return ;
         }else{
            s.insert(k1);
         }
         if(k1!=k2){
         if(s.find(k2)!=s.end()){
            cout<<"Twin snowflakes found."<<endl;
            return ;
         }else{
           s.insert(k2);
         }
         }
    }
         cout<<"No two snowflakes are alike."<<endl;
    return ;
}