Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这题难道不是dp+线段树吗。。#include <map> #include <set> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define rep(i,a,n) for (ll i=a;i<n;i++) #define per(i,a,n) for (ll i=n-1;i>=a;i--) #define all(x) (x).begin(),(x).end() #define pb push_back #define mp make_pair #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; typedef vector<int> VI; typedef pair<int, int> PII; const ll MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const int MAXN = 1e8 + 7; // head ll dp[MAXN]; ll dfs(ll x) { if (dp[x]) return dp[x]; if (x & 1) dp[x] = dfs(x * 3 + 1) + 1; else dp[x] = dfs(x / 2) + 1; return dp[x]; } ll tree[MAXN]; void pushup(int rt) { tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]); } void build(int l, int r, int rt) { if (l == r) { tree[rt] = dp[l]; return; } int m = (l + r) >> 1; build(lson); build(rson); pushup(rt); } int query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) return tree[rt]; int m = (l + r) >> 1; int res = 0; if (L <= m) res = max(res, query(L, R, lson)); if (R > m) res = max(res, query(L, R, rson)); return res; } int main() { ios::sync_with_stdio(false), cin.tie(0); dp[1] = 1; rep(i, 2, 10001) if (!dp[i]) dfs(i); build(1, 10000, 1); int l, r; while (cin >> l >> r) { cout << l << ' ' << r << ' '; if (l > r) swap(l, r); cout << query(l, r, 1, 10000, 1) << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator