sdream

用户名：1662420902

访问量：351

签　名：

等　　级
排　　名	60355
经　　验	222
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	青岛理工大学
专　　业

　　自我简介：

TA的其他文章

The 3n + 1 problem -题解（C++代码）
浏览：138

你可能喜欢

The 3n + 1 problem -题解（C++代码）

　　作者: sdream　　　　发表时间：2020-10-15 09:14:55 浏览：138　|　评论：0　

原题链接：The 3n + 1 problem

是数据水了 还是我理解错了QAQ 以为会有$1-10^6$这种数据

思路是求出$1-10^6$所有数的循环长度 再用线段树查询 
开1e6会爆空间 淦 果然是我想麻烦了
```
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 30, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define int long long
#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
 //ios::sync_with_stdio(false);
int gcd(int a,int b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m, a, b;
int cnt[N];

struct node{
    int l, r, v;
}tr[N * 4];

int get(int x)
{
    if (x >= 1 && x < N && cnt[x]) return cnt[x]; 
    if (x & 1) 
    {
        int k = get(x * 3 + 1) + 1;
        if (x < N) cnt[x] = k;
        return k;
    }
    else 
    {
        int k = get(x / 2) + 1;
        if (x < N) cnt[x] = k;
        return k;
    }
}

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u,int l,int r)
{
    tr[u] = {l, r};
    if (l == r) 
    {
        tr[u].v = cnt[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

int query(int u,int l,int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res = max(res, query(u << 1 | 1, l, r));
    return res;
}

void solve()
{
    cout << a << ' ' << b << ' ';
    if (a > b) swap(a, b);
    cout << query(1, a, b) << endl;
}

signed main()
{
    cnt[1] = 1;
    for (int i = 1; i < N; i ++ ) if (!cnt[i]) get(i);
    build(1, 1, N - 1);
    while (cin >> a >> b) solve();
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

sdream

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

a+b

The 3n + 1 problem -题解（C++代码）

评论区

精彩推荐

文科生的悲哀（C语言代码）

1050题解（结构体数组与结构体指针的使用）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

1218题求大神帮忙看看怎么不能过

P1002 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

WU-蛇行矩阵（C++代码）

Manchester- A+B for Input-Output Practice (VI)

Manchester-蛇行矩阵，不需要数组，四个变量，解决问题

sdream

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

汽水瓶 （C语言代码）怎么答案错误？？？？？

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

a+b

The 3n + 1 problem -题解（C++代码）

评论区

精彩推荐

文科生的悲哀 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

1218题求大神帮忙看看怎么不能过

P1002 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

WU-蛇行矩阵 （C++代码）

Manchester- A+B for Input-Output Practice (VI)

Manchester-蛇行矩阵，不需要数组，四个变量，解决问题

C二级辅导-进制转换（C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C二级辅导-等差数列（C语言代码）

　　评论区

文科生的悲哀（C语言代码）

Tom数（C语言代码）

WU-蛇行矩阵（C++代码）