UVa11350 Stern-Brocot Tree
問題
http://uva.onlinejudge.org/external/113/11350.html
概要
走査の方向 'L' または 'R' が書かれるので、Stern-Brocot Tree を親ノードから辿れ。
解法
左と右の数字の和を取って木を走査していく。二分探索木である。
図を見ながらコードで確認した方が分かりやすい。
Cite from Wikipedia
#include <bits/stdc++.h> using namespace std; typedef long long ll; void TraverseSternBrocotTree(string &traverser, int depth, int limit, ll pl = 0, ll ql = 1, ll pr = 1, ll qr = 0) { ll pm = pl + pr, qm = ql + qr; if(depth == limit) { cout << pm << "/" << qm << endl; return ; } if(traverser[depth] == 'L') TraverseSternBrocotTree(traverser, depth+1, limit, pl, ql, pm, qm); else TraverseSternBrocotTree(traverser, depth+1, limit, pm, qm, pr, qr); } int main() { int Tc; cin >> Tc; while(Tc--) { string s; cin >> s; TraverseSternBrocotTree(s, 0, s.size()); } return 0; }