首页 > 代码库 > hdu 2609 How many(最小表示法)

hdu 2609 How many(最小表示法)

题目链接:hdu 2609 How many

题意:

给你一些01串,a能通过循环到b的算一个种类,问有多少种串。

题解:

最小表示法板子题。

技术分享
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 //s从0开始,返回最小表示的开始位置
 5 int find_min(char *s,int len){
 6     int i=0,j=1,k=0,t;
 7     while(i<len&&j<len&&k<len){
 8         t=s[(i+k)>=len?i+k-len:i+k]-s[(j+k)>=len?j+k-len:j+k];
 9         if(!t)k++;
10         else{
11             if(t>0)i+=k+1;else j+=k+1;
12             j+=i==j,k=0;
13         }
14     }
15     return (i<j?i:j);
16 }
17 
18 int n,len;
19 char s[10001],tmp[10001];
20 set<string>cnt;
21 
22 int main()
23 {
24     while(~scanf("%d",&n))
25     {
26         cnt.clear();
27         F(i,1,n)
28         {
29             scanf("%s",s);
30             len=strlen(s);
31             int mi=find_min(s,len);
32             for(int i=0,ed=mi;i<len;i++,ed=(ed+1)%len)tmp[i]=s[ed];
33             cnt.insert(tmp);
34         }
35         printf("%d\n",cnt.size());
36     }
37     return 0;
38 }
View Code

 

hdu 2609 How many(最小表示法)