/ Vijos / 讨论 / 选数 /

数据范围应该有错

n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=5000000
应为 n , k (1<=n<=20,k<n)
x1,x2,…,xn (1<=xi<=500000)
否则,题解中的这份代码是怎么AC的?

#include<cstring>
#include<cstdio>

using namespace std;

bool isPrime[10000001],visit[10000001];
int ans=0,a[21],N,K;

void DFS(int t,int pre,int sum)
{
        if (t==K)
        {
                if (isPrime[sum]&&!visit[sum])
                        ans++;
                return;
        }
        for(int i=pre+1;i<=N;i++)
                DFS(t+1,i,sum+a[i]);
}

int main()
{
        memset(isPrime,1,sizeof(isPrime));
        memset(visit,0,sizeof(visit));
        isPrime[1]=0;
        for(int i=2;i<=10000000;i++)
                if (isPrime[i])
                        for(int j=2;i*j<=10000000;j++)
                                        isPrime[i*j]=0;
        scanf("%d%d",&N,&K);
        for(int i=1;i<=N;i++)
                scanf("%d",a+i);
        DFS(0,0,0);
        printf("%d",ans);
        return 0;
}

hash最大值只有10000000(1e07)而题目中的数据范围,理论上最大的和是 19*5000000=95000000(9.5e07)

3 条评论

  • 1

信息

ID
1128
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
5603
已通过
2536
通过率
45%
上传者