首页 > ACM题库 > HDU-杭电 > hdu 2609 How many[解题报告]C++
2014
02-12

hdu 2609 How many[解题报告]C++

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;
}

解题转自:http://blog.csdn.net/ice_crazy/article/details/8542046


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