首页 > ACM题库 > HDU-杭电 > hdu 2189 悼念512汶川大地震遇难同胞――来生一起走-母函数-[解题报告]C++
2013
12-30

hdu 2189 悼念512汶川大地震遇难同胞――来生一起走-母函数-[解题报告]C++

悼念512汶川大地震遇难同胞――来生一起走

问题描述 :

妈妈
你别哭
泪光照亮不了
我们的路
让我们自己
慢慢的走

妈妈
我会记住你和爸爸的模样
记住我们的约定
来生一起走

上面这首诗节选自一位诗人纪念遇难同胞的作品,并没有华丽的语言,但是每位读者都应该能感受到作品传达的浓浓爱意,也许还有丝丝无奈。确实,太多的关于孩子不幸的报道冲击着我们每一颗柔弱的心。正如温家宝总理所说“多难兴邦”,这场灾难让我们很多80后的年轻人一下子成熟了起来,其中很多人以自愿者的身份走上了抗震救灾的第一线。
今天,灾区又来了n位志愿者,抗震救灾指挥部需要将他们分为若干个小组,小组的数量不限,但是要求每个小组的人数必须为素数,请问我们有几种分组的方法呢?

特别说明:
1、可以只有一个组;
2、分组的方法只和人数有关,而与具体的人员无关,即:你可以假设人是无区别的。

输入:

输入数据首先包含一个正整数C,表示有C组测试用例,然后是C行数据,每行包含一个正整数n(2<=n<=150),表示志愿者的总人数。

输出:

输入数据首先包含一个正整数C,表示有C组测试用例,然后是C行数据,每行包含一个正整数n(2<=n<=150),表示志愿者的总人数。

样例输入:

3
3
4
5

样例输出:

1
1
2

/*
分析:
    水题,很多种解法。很久没敲过母函数了,就用
母函数过了。

                                           2012-09-25
*/

#include"stdio.h"
#include"string.h"
int prime[100],k;
int num[151];
int main()
{
	int T;
	int n;
	int i,l,j;
	int c1[151],c2[151];

	k=0;
	memset(num,-1,sizeof(num));
	num[0]=num[1]=0;
	for(i=2;i<=150;i++)
	{
		if(num[i])
		{
			prime[k++]=i;
			for(j=2*i;j<=150;j+=i)
			{
				num[j]=0;
			}
		}
	}

	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(c1,0,sizeof(c1));
		memset(c2,0,sizeof(c2));
		for(i=0;i<=n;i+=prime[0])	c1[i]=1;
		for(i=1;i<k;i++)
		{
			if(prime[i]>n)	break;
			for(l=0;l<=n;l++)
			{
				if(c1[l]==0)	continue;
				for(j=0;j+l<=n;j+=prime[i])	c2[l+j]+=c1[l];
			}
			for(l=0;l<=n;l++)
			{
				c1[l]=c2[l];
				c2[l]=0;
			}
		}
		printf("%d\n",c1[n]);
	}
	return 0;
}

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


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count