幂集 | ||||||
| ||||||
Description | ||||||
所谓幂集,就是原集合中所有子集构成的集合,例如集合{1,2,3}的幂集为{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3},{空集}}。现有一个元素个数为n的集合A={a1,a2,a3,a4......an},请求出集合A的幂集中有多少个 子集的和等于整数x。 | ||||||
Input | ||||||
有多组测试数据处理到文件结束,每组数据第一行包含两个整数n(n<=30)和x(x>0); 第二行有n个整数,0<ai<300,代表集合A中的元素。 | ||||||
Output | ||||||
输出集合A的幂集中子集和为x的子集的个数。 | ||||||
Sample Input | ||||||
5 6 1 2 2 4 5 3 7 1 2 3 | ||||||
Sample Output | ||||||
3 0 | ||||||
Hint | ||||||
第一组样例中{1,5},{2,4},{2,4}这三个子集的和都等于6,所以答案为3. | ||||||
Source | ||||||
2014 Winter Holiday Contest 3 |
简述筛法过程:
例如样例1:
遍历一遍整租数据,
使用两个数组,vis【300*30】,vis2【300*30】动态更新数据。
我们先让vis【0】=1,vis2【0】=1,遍历的时候,如果vis【j】!=0,那么vis2【j+a【i】】+=vis【j】,然后让vis==vis2即可
对应代码:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int vis[300*30];
int vis2[300*30];
int a[300*30];
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
memset(vis2,0,sizeof(vis2));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
vis[0]=1;
vis2[0]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<300*30;j++)
{
if(vis[j])
{
vis2[j+a[i]]+=vis[j];
}
}
for(int j=0;j<300*30;j++)
{
vis[j]=vis2[j];
}
/*
for(int i=0;i<30;i++)
{
printf("%d ",vis[i]);
}
printf("\n");
*/
}
printf("%d\n",vis[k]);
}
}