CodeForces Triple Operations (1999E) 题解

wongdzoendzi / 2024-08-07 / 原文

CodeForces Triple Operations (1999E) 题解

题意

把闭区间$[l, r]$的数字都写出来。每步操作中，要选择两个数$a$、$b$，使其变为$3a$和$\lfloor \frac{b}{3} \rfloor$。求出使所有数都等于$0$，所需的操作数。已证明解总是存在。

思路

发现１

在样例中可见，当有数字已为$0$时，可以直接令$0$增大3倍，也就是不改变它，而同时减小其他任意的数。

发现２

观察每步操作分别对两个数的改变：当两数都不为$0$时，$a$增大$3$倍，$b$除以$3$，但之后肯定无法“逃避”将$a$增大的$3$倍除回$a$。又因为对任意$3^ka(k>0)$来说，总要进行$k$次操作才能使其变回$a$。这说明如果我们不用$0$来配合减小其他数的话，我们并没有使操作变少，且要将$a, b$变为$a, 0$，我们至少要操作$2$倍$b$变为$0$需要的次数。

发现３

一个数要除$3$除至为$0$，需要的操作次数为$\lfloor\log_{3}Num\rfloor + 1$。又因为指数函数的单调性，所需操作次数越少，数字一定越小。

推论１

当有$0$时，只能通过$0$来“真正地”减小不为$0$的数。当没有$0$时，我们必须要对某数$k$，执行$2\times \left (\lfloor\log_{3}k\rfloor + 1 \right )$次操作，使之变成$0$。

结论

答案就是最小数操作数的两倍，加上其他所有数所需的操作数，即$ans = 2 \times op(l) + \sum_{i = l+1}^{r}op(i)$，其中$op(x) = \lfloor\log_{3}x\rfloor + 1$。

优化

但仅仅由上面的结论，直接写代码，恐怕会超时。关键在于题目最差的情况下，可以给出$10^4$个样例全是$\left[1,2\cdot10^5\right]$，这样就要运行$2\times10^9$次，超时。

显然，优化的关键在于不能一个个计算，我们需要更快的方法。观查操作次数的式子其中的$3$与下取整符号，不难发现在连续的区间内，只有遇到$3$的某次方数时，操作次数才会改变。

那么我们就只需要先预处理出足够多的$3$的$n$次幂，再一段一段地从$l$处理到$r$即可。

通过计算器不难算出，$3$的$20$次幂已经可以满足题目所需。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 在main中预处理出20个3的次方
ll pow3[21];

void solve()
{
    ll l, r;
    cin >> l >> r;

    int pos = 0;
    while (pos < 20 && pow3[pos] <= l) ++pos;
    // 第一次特殊，因为要先找到最小数的op，并加上，以满足2倍最小值操作数的要求
    ll ans = pos;
    while (l <= r) {
        // 找到恰好大于的地方，因为恰好大于，所以pos即是前面这些数所需的操作数
        while (pos < 20 && pow3[pos] <= l) ++pos;
        // 因为恰好大于，所以无法保证该数不超过r
        ans += (min(r, pow3[pos] - 1) - l + 1) * (ll)pos;
        l = pow3[pos];
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 预处理到3的20次幂
    pow3[0] = 1;
    ll tmp = 3;
    for (int i = 1; i <= 20; ++i) {
        pow3[i] = tmp;
        tmp *= 3;
    }

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}