Snowflake Snow Snowflakes POJ - 3349(字符串的最小表示法)

题意:传送门
题解:这个题本来是用于hash的,吴书上讲的很好,本次附上另外一中解法,用字符串的最小表示法解答:周源论文,本题中加了一种翻转操作,那么可以把不翻转和翻转的两个最小表示法再取最小,最后通过排序查找即可。
code:code:code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=100000+5;
int n,snows[N][6],idx[N],snow[6],isnow[6];
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){
        for(k=0;k<6&&a[i+k]==b[j+k];k++);
        if(k==6)break;
        if(a[i+k]>b[j+k]){
            i+=k+1;
            if(i==j)i++;
        }else{
            j+=k+1;
            if(i==j)j++;
        }
    }
    k=min(i,j);
    for(i=0;i<6;i++)b[i]=a[k+i];
}
bool cmp(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 cmp2(int a,int b)
{
    if(cmp(snows[a],snows[b]))return true;
}
int main()
{
    n=read();
    for(int i=0;i<n;i++){
        for(int j=0,k=5;j<6;j++,k--){
            snow[j]=read();
            isnow[k]=snow[j];
        }
        get_min(snow);
        get_min(isnow);
        if(cmp(snow,isnow))memcpy(snows[i],snow,sizeof(snow));
        else memcpy(snows[i],isnow,sizeof(isnow));
        idx[i]=i;
    }
    sort(idx,idx+n,cmp2);
    bool flag=false;
    for(int i=1;i<n;i++){
        if(!cmp(snows[idx[i-1]],snows[idx[i]])&&!cmp(snows[idx[i]],snows[idx[i-1]])){
            flag=true;
            break;
        }
    }
    if(flag)puts("Twin snowflakes found.");
    else puts("No two snowflakes are alike.");
    return 0;
}

上一篇:Codeforces K. Ice Skating(求强连通分量)


下一篇:shader 积雪效果