| ||||||||||
| 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