题解 P2236 [HNOI2002]彩票

· · 题解

这题数据好像加强了，看到题解区里的都是远古题解了，（看上去）都是 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;
}