hdu 2609 How many（最小表示法）-白红宇

hdu 2609 How many（最小表示法）

阅读量：5221 次

发布时间：2019-06-14

本文共 1810 字，大约阅读时间需要 6 分钟。

Problem Description

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

0110

1100

1001

0011

1010

0101

1000

0001

Sample Output

题意：给你n个字符串每个字符串从任意一个位置组成循环串都是同一个串问到底有多少个不一样的字符串

思路：只要最小表示一样就表示是一样的字符串所以用map判断一下即可

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     #define ll long long intusing namespace std;inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}inline ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}int moth[13]={ 0,31,28,31,30,31,30,31,31,30,31,30,31};int dir[4][2]={ 1,0 ,0,1 ,-1,0 ,0,-1};int dirs[8][2]={ 1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};const int inf=0x3f3f3f3f;const ll mod=1e9+7;int get_min(string s){ int len=s.length(); int i=0; int j=1; int k=0; while(i
                     
                      
                       
                        0) i+=(k+1); else j+=(k+1); if(i==j) j++; k=0; } } return i>j?j:i;}int main(){ ios::sync_with_stdio(false); int n; while(cin>>n){ int ans=0; map
                        
                          mm; for(int i=1;i<=n;i++){ string s; cin>>s; int pos=get_min(s); int len=s.length(); string temp=s.substr(pos)+s.substr(0,pos); if(!mm[temp]) mm[temp]=1,ans++; } cout<
                         
                          <