题解 P1036 选数

· · 题解

本人大概是最弱的橙名了吧...一条咸鱼看着周围的大佬们瑟瑟发抖....

进入正题.这道题暴搜居然没有TLE,心情大好,来发篇题解,希望能帮上有需要的人的忙.

既然放在了过程函数和递归中,首先想到的就是用递归解决.首先考虑得到了一个和,如何判断它是不是质数?朴素方法,设这个数为n,从2至n-1,依此判断是否能整除n,如果发现存在某个整数能够整除n,那么n不是质数,否则是.显然循环次数规模与n相同.

简单优化,显然一个整数n若可以用两个整数的乘积表示,那么其中小一点的约数不会超过√n.我们以60为例 (试图隐藏我不打算证明的事实) :

60=1*60=2*30=3*20=4*15=5*12=6*10=10*6=..

显然,当超过√60=7时开始前面的数就是较大的约数了.因此,可以将枚举范围缩小到[2,√n],时间复杂度降低到O(√n).简要代码如下:

bool isp(int a)//返回a是否为质数
{
  int sq=sqrt(a);//调用函数求a的算术平方根.注意sqrt()函数在cmath中.提前算出可以避免每次循环都计算一次a的算术平方根,可以减小常数
  for(int i=2;i<=sq;i++) if(a%i==0) return false;
  return true;
}

考虑可能需要进行多次判断,即使如此优化仍可能超时,考虑一个更优的方法:注意到相加得到的和最大不超过10<sup>7</sup>,可以构造一个质数表,每次检查n是否为质数只需要查表即可.如何构造一个这样的质数表呢?显然由质数的定义可以得到,一个质数的任意整倍数(除其自身外)都不是质数,任意一个整数都可以被表示为某(几)个质数的乘积,也就是说任意的整数都是某(几)个质数的整倍数.因此只需将任意一个质数的二倍及以上的整倍数标记为"非质数",就可以获得这样的一张质数表了.简要代码如下:

const int MAX=10000010;
bool notp[MAX];//质数表,当notp[i]==0时i为质数.注意开够空间

void calp(void)//开始构造质数表
{
    for(int i=2;i<MAX;i++) if(!notp[i]) for(int j=i+i;j<MAX;j+=i) notp[j]=1;//当前的i是质数,因此将其所有二倍及以上的整倍数都设为非质数.注意不要越界
    return;
}

这样一来就更优了.简单 (胡乱) 分析一波:外层循环将重复约10<sup>7</sup>次,若i不是质数则内层将仅进行1次判断,否则在判断后还将进行约(10<sup>7</sup>-i)/i次赋值操作.实验证明 (再次尝试隐藏自己不打算推式子的事实) ,该函数的循环仅会运行3.95x10<sup>7</sup>次,反复改变MAX的值可以发现运行次数与MAX的一次方成正比,即该方法可以在线性时间内构造质数表.为了确认自己已经理解了这一部分,建议先前去完成P3383 [模板]线性筛素数.

到目前为止,我们获得了初始化时间复杂度为O(n),查询时间复杂度为O(1)的质数表.下面,我们尝试回到原来的问题,看看我们还缺些什么.

我们需要从n个数中选出k个并计算它们的和.为了暴搜,我们需要寻找一种方法唯一地定义当前状态.很容易想到需要一个集合E表示已选择的数.可以用一个数组visited,标记所有已选的数的visited为1.像是这样:

//假设选了i
visited[i]=1;
cal();//递归调用
visited[i]=0;//还原确保之后不会漏选某种情况

可以很容易的利用visited统计已选的数的个数和和.看起来不错.但是不要容易确保不会选重的同时不选漏.比如

a[1]+a[2]+a[5],a[5]+a[2]+a[1]

而且每次查找visited也不够优美,应该还有更简单的解决办法.

很容易注意到,每次只向后看是不会漏选的.举例,如当前选到的数中下标最大的是low,那么选下一个数的时候只从下标为[low+1,n]的数中选不会导致缺失情况也不会导致重复 (依然不证明) ,因此可以重新定义当前状态:还须选i个数,当前的和为sum,当前已经看完了下标为k及以前的数.这样就确保了每次不需要检查重复的情况,也不需要管具体选择了哪些书,只要一一枚举k以后的数并递归调用就可以了,极大的简化了问题.

递归边界也不难得出:当还须选0个数的时候,已经选够了,判断当前的和是否为质数,如果是返回1,否则返回0.而非边界的时候则进行枚举,计算所有情况得到的返回值的和并返回,我们的函数返回值即使在当前限定条件下(从下标大于k的数中选i个数,在sum的基础上加上选的数的和结果是质数)的情况数.显然在主函数中调用cal(k,0,0)得到的返回值即为结果(注意,这里的k与函数中的k含义不同,此处于题目描述一致,请仔细确认不同k的含义).

最后还有一个小小的可行性剪枝:若cal函数中发现n-k<i则返回0.为了确认理解了k的含义,请自行思考理由.

附上AC代码(上面解释过的部分此处不再加注释):

#include<cstdio>//虽然使用的是c++,但由于c的输入输出更快,倾向于使用c的输入输出
using namespace std;
const int MAX=10000010;
bool notp[MAX];
int a[25];//保存数据
int n;//函数中需要使用,为了方便设为全局变量

void calp(void)
{
    for(int i=2;i<MAX;i++) if(!notp[i]) for(int j=i+i;j<MAX;j+=i) notp[j]=1;
    return;
}

int cal(int i,int sum,int k)    //再选i个,当前和为sum,看完了a[k]
{
    if(i==0)
    {
        if(notp[sum]) return 0;
        else return 1;
    }

    if(n-k<i) return 0;

    int ans=0;
    for(int j=k+1;j<=n;j++) ans+=cal(i-1,sum+a[j],j);
    return ans;
}

int main()
{
    calp();
    int k;
    //关于输入输出的问题请自行查找资料/请教他人解决
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    printf("%d",cal(k,0,0));
    return 0;
}

至此,虽然并没有使用更高效率的方法,我们依然以尚可以接受的时间通过了这道题.强烈建议再去完成P1706 全排列问题,使用类似的方法完成一道题可以加深理解.

最后,本人蒟蒻一棵 (棵?),有不准确的地方请…用力喷!我会回来改正的.