Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题难道不是dp+线段树吗。。

Posted by Flowersea at 2017-05-05 23:42:56 on Problem 1207
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator