【P2236】彩票（搜索+剪枝）

想说这个题要是想做出来就必须不干一件事情，那就是不要点开标签。。点开标签看到那些平衡树什么的。。。。

首先，我们要理解这个题的题意。买彩票是什么大家都应该知道吧，一般来说，就是从很多数里面选出来几个，然后系统，额……就是那个有一堆球的机器，弹出来几个球球上的数字就是中奖数字。

对于这个题，我们要是选择的n个数的倒数的和等于一开始的X/Y，不妨设它为t，然后我们进行搜索，这里事先说一下，在进行了常数优化后，AC代码最慢的点要650+。怎么搜索呢，对于这个题，很明显就有了两种思路，一种是朴素的一个个枚举情况，这个应该也是能过，但是剪枝的时候不是很好处理。然后就是从前到后暴力搜索，不是枚举情况，而是根据当前的情况，对搜到的数进行选或不选的抉择。

然后程序应该很容易打出来，而且，很短。。。。但是显而易见，前面说了，常数优化后还要650+，这么一个剪枝没有肯定会T，然后，我们加入一个很常见的可行性剪枝，如果最终减选的数字的最大值还是要大于，额，那个误差。就return，同理，如果减得最小要小于那个误差，也要return。这样以后可以减掉部分搜索。

P.S.误差是因为浮点数计算会有一个非常微小的误差。。。所以必须计算在内，而且，必须非常小。。10e-9与10e-10差了40分。。。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define re register

#define wc 0.0000000001

using namespace std;

int n,m;

double x,y,s[],ans,f[],t;

inline void dfs(int st,int to,double tot)

{

    double maxx=tot+s[to+n-st]-s[to];

    double minn=tot+s[m]-s[m-n+st];

    if(t-maxx>wc||t-minn<-wc)

    return;

    if(st>=n)

    {

        ans++;

        return;

    }

    dfs(st,to+,tot);

    dfs(st+,to+,tot+1.0/(to+));

    return;

}

int main()

{

    cin>>n>>m>>x>>y;

    t=x/y;

    for(re int i=;i<=m;i++) s[i]=s[i-]+1.0/i;

    dfs(,,);

    cout<<ans;

}

巴特西

【P2236】彩票（搜索+剪枝）

最新文章

热门文章