2022icpc西安站部分题解-E-Toy模板网

这篇具有很好参考价值的文章主要介绍了2022icpc西安站部分题解-E。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

E. Find Maximum

题意：给定边界L和R，算满足的所有的的最大值，

其中满足: $e. find maximum,c++,算法,图论$ 。

题解：

打表发现发现了f(x)与x的三进制有关系，即f(x)等于x三进制的每个数相加，再加上三进制数的有效位数。下图从左向右依次是x，x的三进制，f(x)。

e. find maximum,c++,算法,图论

于是便是将问题转变为在区间中找到三进制的每个数相加再加上三进制数的有效位数最大的值。

首先分类讨论：

1.如果L的三进制长度小于R的三进制长度，那么答案可能是22...2(R的三进制长度减一个2)，或者在100...0(R的三进制长度减一个0)-R之间选择最大值；

2.如果L的三进制长度等于R的三进制长度，那么答案在L-R之间选择最大值。

代码如下：文章来源地址https://www.toymoban.com/news/detail-714288.html

#pragma GCC optimize(2)
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <unordered_map>
#include <set>
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define endl "\n"
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 200010, mod = 1000000007, INF = 1e9;
typedef long long LL;
typedef pair<int, int> PII;

int n, T;
int x;
LL l, r;
int res;

LL f(LL x)
{
    if (x == 0) return 1;
    else if (x % 3 == 0) return f(x / 3) + 1;
    else return f(x - 1) + 1;
}

vector<int> get_third(LL x)
{
    vector<int> q;
    if (x == 0) q.pb(0);
    while (x)
    {
        q.pb(x % 3);
        x /= 3;
    }
    reverse(q.begin(), q.end());
    return q;
}

void text(LL x)
{
    cout << x << " :\t";
    LL t = x;
    vector<int> S = get_third(t);
    
    for (int i : S) cout << i;
    cout << "\t" << f(x) << endl;
}

void cal(vector<int> l, vector<int> r, int pos, int sum, int limitr)
{
    if (limitr)
    {
        int ans = sum + (r.size() - pos) * 2 + r.size();
        res = max(res, ans);
        return ;
    }
    if (pos == r.size())
    {
        int ans = sum + r.size();
        res = max(res, ans);
        return ;
    }
    
    int limit = r[pos];
    cal(l, r, pos + 1, sum + limit, 0);
    if (limit - 1 >= l[pos]) cal(l, r, pos + 1, sum + limit - 1, 1);
}

void solve()
{
//    for (int i = 0; i <= 10; i ++ ) text(i);
    res = 0;
    cin >> l >> r;
    vector<int> L, R;
    L = get_third(l), R = get_third(r);
    if (L.size() < R.size())
    {
        res = (R.size() - 1) * 2 + R.size() - 1;
        
        vector<int> backup;
        backup.pb(1);
        for (int i = 1; i < R.size(); i ++ ) backup.pb(0);
//        reverse(backup.begin(), backup.end());
//        for (int i : backup) cout << i << " ";
        cal(backup, R, 0, 0, 0);
    }
    else
    {
        cal(L, R, 0, 0, 0);
    }
    cout << res << endl;
}

int main()
{
    quick_cin();
    cin >> T;
//    T = 1;
    while (T -- )
    {
        solve();
    }
    return 0;
}

到了这里，关于2022icpc西安站部分题解-E的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！