[HNOI2002]彩票 (搜索+剪枝)

题目描述

某地发行一套彩票。彩票上写有1到M这M个自然数。彩民可以在这M个数中任意选取N个不同的数打圈。每个彩民只能买一张彩票，不同的彩民的彩票上的选择不同。

每次抽奖将抽出两个自然数X和Y。如果某人拿到的彩票上，所选N个自然数的倒数和，恰好等于X/Y，则他将获得一个纪念品。

已知抽奖结果X和Y。现在的问题是，必须准备多少纪念品，才能保证支付所有获奖者的奖品。

输入输出格式

输入格式：

输入文件有且仅有一行，就是用空格分开的四个整数N，M，X，Y。

输出格式：

输出文件有且仅有一行，即所需准备的纪念品数量。

1≤X, Y≤100，1≤N≤10，1≤M≤50。

输入数据保证输出结果不超过10^5。

输入输出样例

输入样例#1：

2 4 3 4

输出样例#1：

Solution

这种卡精度的题是真的恶心... 让我想起了我的那个高斯消元模板...

好像标签里是 Splay ,但是数据范围还比较小,所以用 搜索+剪枝

然后的话,这道题的主要难度在于精度,真的...

#include<bits/stdc++.h>

using namespace std;

const double eps=1e-10;

int n,m,ans,v[60],now;

double x,y,tag;

void dfs(double sum,int last)

{

    now++;

    if(sum-tag>eps)return;

    if(sum+(double)(n-now+1)*1.0/(double)(last+1)+eps<tag)return;

    if((sum+(double)(n-now+1)*1.0/(double)m)>tag+eps)return;

    if(now==n+1)

    {

        if(fabs(sum-tag)<=eps)ans++;

        return;

    }

    for(int i=last+1;i<=m;i++)

    {

        if(!v[i])

        {

            v[i]=1;

            dfs(sum+1.0/(double)i,i);

            v[i]=0;

            now--;

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

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

    tag=(double)x/(double)y;

    dfs(0,0);

    cout<<ans<<endl;

    return 0;

}

巴特西

[HNOI2002]彩票 (搜索+剪枝)

题目描述

输入输出格式

输入输出样例

Solution

最新文章

热门文章