HDU 2609 How many（最小表示法）

太过爱你忘了你带给我的痛 2022-06-09 00:54 168阅读 0赞

Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me  
How many kinds of necklaces total have.(if two necklaces can equal by rotating ,we say the two necklaces are some).  
For example 0110 express a necklace, you can rotate it. 0110 -> 1100 -> 1001 -> 0011->0110.

Input

The input contains multiple test cases.  
Each test case include: first one integers n. (2<=n<=10000)  
Next n lines follow. Each line has a equal length character string. (string only include '0','1').

Output

For each test case output a integer , how many different necklaces.

Sample Input

4
    0110
    1100
    1001
    0011
    4
    1010
    0101
    1000
    0001

Sample Output

1
    2

题解：

题意：

给一堆字符串，题目如果一位位整体循环移动可以相同就算同一种串，问你有多少种串

思路：

用最小表示法把该串表示出来存起来，最后排一下序，如果和前面的串相同就跳过，不同就计数

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct node
    {
        char s[105];
    }a[10005];
    int cmp(node x,node y)//按照字典序排好
    {
        return strcmp(x.s,y.s)<0;
    }
    int getminmax(char word[])//最小表示法模板
    {
        int i=0,j=1,k=0;
        int wlen=strlen(word);
        while(i<wlen&&j<wlen&&k<wlen)
        {
            int t=word[(i+k)%wlen]-word[(j+k)%wlen];
            if(!t) k++;
            else
            {
                if(t>0)
                    i=i+k+1;
                else
                    j=j+k+1;
                if(i==j)
                    j++;
                k=0;
            }
        }
        return i<j?i:j;
    }
    int main()
    {
        char p[105];
        int i,j,ans,n,k,d;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<n;i++)
            {
                scanf("%s",p);
                d=getminmax(p);
                for(j=d,k=0;j<strlen(p);j++,k++)//储存该串
                    a[i].s[k]=p[j];
                for(j=0;j<d;j++,k++)
                    a[i].s[k]=p[j];
                a[i].s[k]='\0';
            }
            sort(a,a+n,cmp);
            ans=1;
            for(i=1;i<n;i++)
            {
                if(strcmp(a[i].s,a[i-1].s)==0)//排序后对比
                    continue;
                ans++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }