Triple Operations 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求计算将区间 $[l, r]$ ~[l, r]~ 内所有整数通过指定操作变为 $0$ ~0~ 所需的最少操作次数。核心解法利用三进制表示，将操作视为给一个数末尾添零、给另一个数删去末位，最终答案等于 $f(l) + \sum_{i=l}^{r} f(i)$ ~f(l) + \sum_{i=l}^{r} f(i)~，其中 $f(x)$ ~f(x)~ 为 $x$ ~x~ 的三进制位数。

分析

核心观察

一次操作将 $x$ ~x~ 变为 $3x$ ~3x~（三进制末尾补 $0$ ~0~），将 $y$ ~y~ 变为 $\lfloor y/3 \rfloor$ ~\lfloor y/3 \rfloor~（三进制删去末位）。只有当 $x=0$ ~x=0~ 时， $3x$ ~3x~ 仍为 $0$ ~0~，不会增加位数，此时总位数减少 $1$ ~1~。

思路

将每个数写成三进制形式。操作不改变所有数的总位数，除非选择 $x=0$ ~x=0~，此时总位数减少 $1$ ~1~。最终所有数变为 $0$ ~0~（位数为 $0$ ~0~），因此必须通过若干次“零操作”来消耗掉所有初始位数。
要构造最少操作，应尽快得到一个 $0$ ~0~。对某个数 $v$ ~v~，使其变为 $0$ ~0~ 需要连续除以 $3$ ~3~ 直到为 $0$ ~0~，即 $f(v)$ ~f(v)~ 次操作（每次选它为 $y$ ~y~，且另一个数任意非零？但还需考虑同时给另一个数补零，但补零不会消耗位数，只要另一个数非零，总位数不变；若另一个数为零则消耗位数，但这个过程本身会使目标数逐步减少）。为减少总操作，第一步应选择区间内最小的数 $l$ ~l~，因为它位数最少， $f(l)$ ~f(l)~ 最小，将其变为 $0$ ~0~ 需 $f(l)$ ~f(l)~ 次。
一旦获得 $0$ ~0~，之后每次操作选择 $x=0$ ~x=0~， $y$ ~y~ 为某个未归零的数，即可消耗 $y$ ~y~ 的一位，同时 $x$ ~x~ 保持 $0$ ~0~。要消除所有数的全部位数，总共需要消除 $\sum_{i=l}^{r} f(i)$ ~\sum_{i=l}^{r} f(i)~ 位（因为每个数初始有 $f(i)$ ~f(i)~ 位，最终都要变为 $0$ ~0~）。因此总操作次数为第一步的 $f(l)$ ~f(l)~ 加上所有数的位数总和，即：

$\displaystyle f(l) + \sum_{i=l}^{r} f(i)$

其中 $f(x)=\lfloor \log_3 x \rfloor + 1$ ~f(x)=\lfloor \log_3 x \rfloor + 1~，且 $f(0)=0$ ~f(0)=0~（但 $l \ge 1$ ~l \ge 1~）。
预计算 $f(i)$ ~f(i)~ 的前缀和 $\text{psum}(n)=\sum_{i=1}^{n} f(i)$ ~\text{psum}(n)=\sum_{i=1}^{n} f(i)~，则每个测试用例的答案为：

$\displaystyle f(l) + \text{psum}(r) - \text{psum}(l-1)$

具体示例

以样例第一组 $l=1, r=3$ ~l=1, r=3~ 为例：
$f(1)=1$ ~f(1)=1~， $f(2)=1$ ~f(2)=1~（三进制 2 一位）， $f(3)=2$ ~f(3)=2~（三进制 10 两位）。
总和 $1+1+2=4$ ~1+1+2=4~，再加 $f(l)=1$ ~f(l)=1~，得 $5$ ~5~，与输出一致。
第二组 $2,4$ ~2,4~： $f(2)=1, f(3)=2, f(4)=2$ ~f(2)=1, f(3)=2, f(4)=2~，总和 $5$ ~5~，加 $f(2)=1$ ~f(2)=1~ 得 $6$ ~6~。

算法步骤

预处理 $f(i)$ ~f(i)~（ $i$ ~i~ 从 $1$ ~1~ 到最大可能的 $r$ ~r~，即 $2 \times 10^5$ ~2 \times 10^5~）。
计算前缀和数组 psum，其中 psum[i] = psum[i-1] + f(i)。
对每个测试用例，读入 $l, r$ ~l, r~。
计算答案 ans = f(l) + psum[r] - psum[l-1]。
输出 ans。

复杂度分析

时间：预计算 $O(M)$ ~O(M)~，其中 $M=2\times 10^5$ ~M=2\times 10^5~；每个测试用例 $O(1)$ ~O(1)~。
空间： $O(M)$ ~O(M)~ 用于存储 $f$ ~f~ 和前缀和数组。

实现注意事项

最大 $r$ ~r~ 为 $2\cdot 10^5$ ~2\cdot 10^5~，预计算范围可设为 $200000$ ~200000~ 或稍大（如 $200005$ ~200005~）。
$f(x)$ ~f(x)~ 可通过循环整除 $3$ ~3~ 得到，注意当 $x=0$ ~x=0~ 时返回 $0$ ~0~，但输入 $l \ge 1$ ~l \ge 1~，计算时只用正数。
前缀和数组需使用 64 位整数（如 long long）存储，因为 $\sum f(i)$ ~\sum f(i)~ 约 $O(r \log_3 r)$ ~O(r \log_3 r)~，对 $2e5$ ~2e5~ 约 $2e5 \times 12 = 2.4e6$ ~2e5 \times 12 = 2.4e6~，还在 int 范围内（ $2.4e6 < 2^31$ ~2.4e6 < 2^31~），但为安全仍用 long long。
多组测试数据，使用快速输入输出。

源代码

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

const int MAXN = 200000 + 5;
long long fval[MAXN], pref[MAXN];

int f(int x) {
    int cnt = 0;
    while (x > 0) {
        x /= 3;
        ++cnt;
    }
    return cnt;
}

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

    for (int i = 1; i < MAXN; ++i) {
        fval[i] = f(i);
        pref[i] = pref[i - 1] + fval[i];
    }

    int T;
    cin >> T;
    while (T--) {
        int l, r;
        cin >> l >> r;
        long long ans = fval[l] + (pref[r] - pref[l - 1]);
        cout << ans << '\n';
    }
    return 0;
}

import sys

MAXN = 200000 + 5
fval = [0] * MAXN
pref = [0] * MAXN

def f(x):
    cnt = 0
    while x > 0:
        x //= 3
        cnt += 1
    return cnt

for i in range(1, MAXN):
    fval[i] = f(i)
    pref[i] = pref[i-1] + fval[i]

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    out = []
    idx = 1
    for _ in range(t):
        l = int(data[idx]); r = int(data[idx+1]); idx += 2
        ans = fval[l] + (pref[r] - pref[l-1])
        out.append(str(ans))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

目前没有评论。