2014
02-12

# How many

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.

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′).

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′).

4
0110
1100
1001
0011
4
1010
0101
1000
0001

1
2

/*

最小表示法果题。

2013-01-25
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define N 10011
#define M 111

int n,len;
struct A{
char str[M];
}E[N];

void get_min()
{
int i,l;
int p1,p2;
int k,len;
int flag;
char temp[2*M];
len=strlen(E[0].str);
for(i=0;i<n;i++)
{
strcpy(temp,E[i].str);
strcat(temp,E[i].str);
flag=-1;
p1=p2=0;
while(1)
{
//
if(p1==p2)
{
p1++;
if(p1>=len)	break;
continue;
}
//
k=0;
while(temp[p1+k]==temp[p2+k])
{
k++;
if(k>=len)	flag=p1;
}
if(flag!=-1)	break;
//
if(temp[p1+k]>temp[p2+k])	p1+=k+1;
else						p2+=k+1;
if(p1>=len || p2>=len)	break;
}
if(p1>=len)		flag=p2;
else if(p2>=len)flag=p1;
for(l=0;E[i].str[l];l++)	E[i].str[l]=temp[l+flag];
}
}
int cmp(const void *a,const void *b)
{
A *c,*d;
c=(A *)a;
d=(A *)b;
return strcmp(c->str,d->str);
}
int main()
{
int i;
int ans;
while(scanf("%d",&n)!=-1)
{
for(i=0;i<n;i++)	scanf("%s",E[i].str);
get_min();
qsort(E,n,sizeof(E[0]),cmp);
ans=1;
for(i=1;i<n;i++)	if(strcmp(E[i].str,E[i-1].str))	ans++;
printf("%d\n",ans);
}
return 0;
}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}

3. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！