POJ 1207 解题报告

本文主要是介绍POJ 1207 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近用了好几次线段树，所以这道题还是用线段树做的。首先，用DFS（其实也算DP）算出来1~10000之间的所有数的“cycle length”，没到1之前前一个数的cycle length等于后一个数的cycle length加1。然后可以建立一个线段树。查询是一个在线段树上做范围查询的过程。

很喜欢线段树这个数据结构。

1207

Accepted

412K

0MS

C++

2028B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1207 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;const int MAXN = 10000;int DFS(int num, int length[])
{if (num <= MAXN && length[num] > 0){return length[num];}if (num == 1){length[num] = 1;return 1;}else{int next = num & 1 ? 3 * num + 1 : num / 2;int len = DFS(next, length) + 1;if (num < MAXN){length[num] = len;}return len;}
}int buildSegmentTree(std::vector<int> &segmentTree, int left, int right, int index, int length[])
{if (left == right){segmentTree[index] = length[left];return segmentTree[index];}int mid = left + ((right - left) >> 1);segmentTree[index] = max(buildSegmentTree(segmentTree, left, mid, 2 * index + 1, length), buildSegmentTree(segmentTree, mid + 1, right, 2 * index + 2, length));return segmentTree[index];
}int queryMax(std::vector<int> &segmentTree, int left, int right, int index, const int lindex, const int rindex)
{if (rindex < left || right < lindex){return 0;}if (lindex <= left && right <= rindex){return segmentTree[index];}int mid = left + ((right - left) >> 1);return max(queryMax(segmentTree, left, mid, 2 * index + 1, lindex, rindex), queryMax(segmentTree, mid + 1, right, 2 * index + 2, lindex, rindex));
}int main()
{int length[MAXN + 1] = {0};for (int i = 1; i <= MAXN; ++i){if (length[i] == 0){DFS(i, length);}}std::vector<int> segmentTree(4 * (MAXN + 1), 0);buildSegmentTree(segmentTree, 0, MAXN, 0, length);int i, j;while (cin >> i >> j){cout << i << " " << j << " " << queryMax(segmentTree, 0, MAXN, 0, min(i, j), max(i, j)) << endl;}return 0;  
}

这篇关于POJ 1207 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---