自动搬运

查看原文

来自洛谷，原作者为

	Ryo_Yamada **

搬运于2025-08-24 21:35:28，当前版本为作者最后更新于2020-09-13 21:30:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题数据好像加强了，看到题解区里的都是远古题解了，（看上去）都是 $60pts \sim 80pts$ 的，来写一篇题解。

首先，这题卡精度，需要加上 const double eps = 1e-10; 感觉都会，就不多说了。

$10pts$ 做法

直接爆搜+一个最常见的剪枝，如果比 $\dfrac{x}{y}$ 大就返回。

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-10;

int n, m;
int ans;
double need;

void dfs(int st, double now, int last) {
    if(now - need > eps) return ;
    if(st == n) {
        if(fabs(now - need) < eps) ++ans;
        return ;
    }
    for(int i = last + 1; i <= m; i++) {
        dfs(st + 1, now + 1.0 / i, i);
    }
}

int main() {
    int x, y;
    cin >> n >> m >> x >> y;
    need = 1.0 * x / y;
    dfs(0, 0.0, 0);
    cout << ans << endl;
    return 0;
}

至此就能得到 $10pts$ 的好成绩。若是没时间了，写这样一个爆搜骗分是很不错的选择。

$60 pts$ 做法

其实也很容易想，在上面代码的基础上加一个上下界剪枝就可以了。这个做法开 $O2$ 是可以过的，还跑的飞快，但是考试上是没有 $O2$ 选项的，所以我们需要思考更优的解法。

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-10;

int n, m;
int ans;
double need;

void dfs(int st, double now, int last) {
    if(st == n) {
        if(fabs(now - need) < eps) ++ans;
        return ;
    }
    if(now > need + eps) return ;
    if(now + 1.0 * (n - st) / m > need + eps) return ;
    if(now + 1.0 * (n - st) / (last + 1) < need - eps) return ;
    for(int i = last + 1; i <= m; i++) {
        dfs(st + 1, now + 1.0 / i, i);
    }
}

int main() {
    int x, y;
    cin >> n >> m >> x >> y;
    need = 1.0 * x / y;
    dfs(0, 0.0, 0);
    cout << ans << endl;
    return 0;
}

$80 pts \sim 100pts$ 做法

我们知道，除法（特别是浮点数除法）是非常慢的，在搜索中我们有很多多余的除法操作，如果把除法变成减法就会快很多。所以我们使用前缀和优化，使用 $pre_i$ 记录 $\dfrac{1}{1} + \dfrac{1}{2} + \dots + \dfrac{1}{i}$。同时或许还能剪掉很少的冗余状态，就拿下界剪枝来说，原来的下界是 $now + \dfrac{n - st}{m}$，而现在的是 $now + \dfrac{1}{m - n + st + 1} + \dots + \dfrac{1}{m}$。当然，这点优化可以忽略不计。可以看到，$\texttt{TLE}$ 的点最慢的是 $1.03s$，在这个基础上卡卡常是能过的。

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-10;

int n, m;
int ans;
double need;
bool vis[55];
double pre[55];

void dfs(int st, double now, int last) {
    if(st == n) {
        if(fabs(now - need) < eps) ++ans;
        return ;
    }
    if(now > need + eps) return ;
    if(now + pre[m] - pre[m - n + st] > need + eps) return ;
    if(now + pre[last + n - st] - pre[last] < need - eps) return ;
    for(int i = last + 1; i <= m; i++) {
        if(!vis[i]) {
            vis[i] = true;
            dfs(st + 1, now + 1.0 / i, i); 
            vis[i] = false;
        }
    }
}

int main() {
    int x, y;
    cin >> n >> m >> x >> y;
    need = 1.0 * x / y;
    for(int i = 1; i <= m; i++) pre[i] = pre[i - 1] + 1.0 / i;
    dfs(0, 0.0, 0);
    cout << ans << endl;
    return 0;
}

$100pts$ 做法

在前面的代码中，每次搜索都是循环向后选择下一个增加的倒数，这就造成了很多多余的状态，不论后来有没有被剪掉，都或多或少会造成影响。（例如，后面剩下的数全部选择也不够 $n$ 个）

我们换个方式搜索，对于 $i$，我们搜索 选 或 不选。同时在前面加上对于个数的剪枝。此时，不开 $O2$ 最慢的点也只有 $790ms$ 了。

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-10;

int n, m;
int ans;
double need;
bool vis[55];
double pre[55];

void dfs(int st, double now, int cnt) {
    if(m - st + 1 < n - cnt) return ;
    if(now + pre[m] - pre[m + cnt - n] > need + eps) return ;
    if(now + pre[st + n - cnt - 1] - pre[st - 1] < need - eps) return ;
    if(cnt == n) {
        ++ans;  
        return ;
    }
    dfs(st + 1, now, cnt);
    dfs(st + 1, now + 1.0 / st, cnt + 1);
}

int main() {
    int x, y;
    scanf("%d%d%d%d", &n, &m, &x, &y);
    need = 1.0 * x / y;
    for(int i = 1; i <= m; i++) pre[i] = pre[i - 1] + 1.0 / i;
    dfs(1, 0.0, 0);
    printf("%d\n", ans);
    return 0;
}