P6921 [ICPC2016 WF]Forever Young - 题解

· · 题解

0. 题意简述

给定 y,l，求最大的 b 使 (y)_b 仅含有数字 0-9，且将 (y)_b 看作十进制数字时 (y)_b >= l。(10\le l\le y\le 10^{18})

1. 做法详解

这里是一种基于二分和预处理的做法。

首先很容易想到，对于下限 l，可以二分答案。

具体就是把 l 当作 b 进制数，然后把 l 转回 10 进制，看一下是否大于 y，若大于则代表此时的 b 不符合条件，然后枚举 b 的上限。对于“只包含十进制数字”这条要求，我们暴力从上限往下枚举即可。时间复杂度 \mathcal{O}(\log y+b_{max}-b_{ans})。

如果满足“只包含十进制数字”的答案很稀疏的话，这个时间复杂度显然是过不去的，而事实就是这样。

我们仔细想想，会发现：如果过不去，说明 b 的上限与实际值的差很大。这说明实际值一定大不到哪去。

考虑预处理出从 10 开始的一定范围内中的最大答案，然后再加入卡时，如果枚举到某个时间点时还没有出答案，就直接输出预处理得到的结果。

这显然会牺牲一部分的正确性，但已经足以让我们通过 48 个测试点。

再考虑观察答案可能的分布位置。

我们试着打个暴力，可以发现，当 n 足够大时，答案集中分布在 \frac{\sqrt n}{2} 附近。

于是我们又多通过了两个测试点。

再考虑答案的集中趋势是不行了，于是我们试试看极限情况 y=10^{18} 时的数据。

我们会发现，在 y 足够大，l 略小的时候，答案即为 \lfloor\frac{y}{k}\rfloor，其中 k 是一个较小的常数。

加上上述三个预处理即可通过本题。

2. 代码

#include<bits/stdc++.h>
template<typename T1, typename T2>
constexpr auto max (T1 a, T2 b) -> decltype(a + b) {
    if (a > b)return a;
    return b;
}
using namespace std;
using ll = long long;
constexpr ll maxn1 = 999999, maxn2 = 1000, maxms = 114.514;
//分别为：从 10 开始枚举时的上限；sqrt(y) 附近的波动范围；暴力枚举的时间上限
ll change (ll l, ll b, ll y) {//把 l 当作 b 进制数，然后把 l 转回 10 进制
    if (l < 10)return l;
    auto a = change (l / 10, b, y);
    if (a >= y / b + 1 || !~a)return -1;//细节：如果直接返回 10 进制的值会溢出，所以判断是否大于 y，若是则直接返回 -1
    return a * b + l % 10;
}
bool check (ll l, ll b) {//判断是否满足“只包含十进制数字”
    if (l < b)return l < 10;
    return check (l / b, b) && l % b < 10;
}
inline auto gettime ( ) {//获取时间（精确到毫秒）
    return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now ( ).time_since_epoch ( )).count ( );
}
int main ( ) {
    ll y, l, ans = -1, L = 10, R = 1e18, m, beg = gettime ( );
    //分别为：题目中的 y 与 l；预处理的答案；二分答案的上下界；二分答案的中值；程序开始运行的时间
    cin >> y >> l;R = y;
    while (L < R) {//二分答案上界
        m = L + R + 1 >> 1;
        if (change (l, m, y) != -1 && change (l, m, y) <= y)L = m;
        else R = m - 1;
    }
    for (ll i = 10;i <= maxn1 && i <= L;i++)//预处理1
        if (check (y, i))ans = max (ans, i);
    if (sqrt (y) > maxn2)//细节：若 sqrt(y) 小于 maxn2，则二分答案已经可以出结果，预处理反而会 RE
        for (ll i = max (sqrt (y) / 2 - maxn2 / 3, 0);i <= sqrt (y) / 2 + maxn2 / 3 && i <= L;i++)//预处理2
            if (check (y, i))ans = max (ans, i);
    if (y > maxn1)
        for (ll i = maxn1;y / i < L && i>1 && y / i > 10;i--)
            if (check (y, y / i))ans = max (ans, y / i);//预处理3
    while (gettime ( ) - beg < maxms) {//带卡时的暴力枚举
        if (check (y, L)) {
            cout << L << endl;
            return 0;
        }
        L--;
    }
    cout << ans << endl;
    return false;
}

3.总结

二分答案是一个很好用的方法，并且如果能看出一些答案的分布规律的话可以结合使用。

4.UPD

[2022-10-13 22:44] 优化了代码的可读性。