题解归档 - cf104077E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104077E
• 本地来源：problems/cf104077E/idea.md
• 题目链接：https://codeforces.com/gym/104077/problem/E
• 原始标题：E - Find Maximum

思路

E - Find Maximum

The recurrence reduces x to zero by repeatedly subtracting the current ternary digit until it
becomes divisible by 3, then dividing by 3.

Therefore

f(x) = (sum of ternary digits of x) + (number of ternary digits of x).

For each query [l,r], maximize this value with a ternary digit DP bounded by l and r.
There are only about 40 ternary digits for 1e18.

Checked against direct simulation for small ranges.

代码

来源：problems/cf104077E/solution.cpp

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

int solve_one(ll l, ll r) {
    vector<int> lo, hi;
    while (r) {
        hi.push_back(r % 3);
        r /= 3;
    }
    if (hi.empty()) hi.push_back(0);
    int L = (int)hi.size();
    lo.assign(L, 0);
    for (int i = 0; i < L; i++) {
        lo[i] = l % 3;
        l /= 3;
    }
    reverse(lo.begin(), lo.end());
    reverse(hi.begin(), hi.end());

    const int NEG = -1e9;
    int dp[2][2][2];
    for (auto &a : dp) for (auto &b : a) for (int &x : b) x = NEG;
    dp[1][1][0] = 0;
    for (int pos = 0; pos < L; pos++) {
        int ndp[2][2][2];
        for (auto &a : ndp) for (auto &b : a) for (int &x : b) x = NEG;
        for (int tl = 0; tl < 2; tl++) for (int th = 0; th < 2; th++) for (int st = 0; st < 2; st++) {
            int cur = dp[tl][th][st];
            if (cur < 0) continue;
            int from = tl ? lo[pos] : 0;
            int to = th ? hi[pos] : 2;
            for (int d = from; d <= to; d++) {
                int ns = st || d != 0;
                int add = ns ? d + 1 : 0;
                int nl = tl && d == lo[pos];
                int nh = th && d == hi[pos];
                ndp[nl][nh][ns] = max(ndp[nl][nh][ns], cur + add);
            }
        }
        memcpy(dp, ndp, sizeof(dp));
    }
    int ans = 0;
    for (int tl = 0; tl < 2; tl++) for (int th = 0; th < 2; th++) ans = max(ans, dp[tl][th][1]);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll l, r;
        cin >> l >> r;
        cout << solve_one(l, r) << '\n';
    }
    return 0;
}