嘘~ 正在从服务器偷取页面 . . .

洛谷P1748 H数题解

发布日期: 2024-02-20

更新日期: 2024-02-20

文章字数: 491

洛谷P1748 H数题解

题目链接：P1748 H数

题意：

所谓 $H$ 数，是指只含有 $2,3,5,7$ 这些质因数的数，如 $630$ 是 $H$ 数，而 $22$ 不是。

现在要求输出第 $n$ 个 $H$ 数，即 $H_n$ （为了方便起见将 $H_1$ 定为 $1$ ）。

已知 $n$ 不超过 $10000$，最后数据在 int64 范围之内。

输入格式：

一行， $n$ 。

输出格式：

一行，输出 $H_n$ 。

虽说是普及/提高− 的题，但是它的思路还是挺有意思的。

考虑dp，或者说考察 $H_n$ 的递推方式。

$H_i=\min\{H_a\times 2,~H_b\times 3,~H_c \times 5,~H_d\times 7\}$

其中 $a,b,c,d$ 均满足特定形式，例如 $H_{a-1}\times 2 \le H_i < H_a \times 2$ 。

一种暴力的转移方式是，枚举 $j$ ，并钦定：例如当 $j$ 满足 $a$ 的条件时尝试用 $H_a$ 更新 $H_i$ 。

这样只需扫一遍 $[1,~i-1]$ 即可。注意到 $a,b,c,d$ 均随着 $i$ 的增长而不减。

因此我们可以直接维护四个指针 $a,b,c,d$ ，每次算出 $H_i$ 后，更新 $a,b,c,d$ 使他们重新满足条件。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))

int a,b,c,d,x[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; x[1] = a = b = c = d = 1;
    for(int i = 2; i <= n; i++)
    {
        x[i] = x[a] * 2;
        if(x[i] > x[b] * 3) x[i] = x[b] * 3;
        if(x[i] > x[c] * 5) x[i] = x[c] * 5;
        if(x[i] > x[d] * 7) x[i] = x[d] * 7;
        if(x[i] == x[a] * 2) ++a;
        if(x[i] == x[b] * 3) ++b;
        if(x[i] == x[c] * 5) ++c;
        if(x[i] == x[d] * 7) ++d;
    }
    cout << x[n] << '\n';
    return 0;
}