题解：UVA11350 Stern-Brocot Tree

一道很简单的题，按照题意模拟就可以了。

设 \(la = 0, lb = 1, ra = 1, rb = 0\)，代表 \(L = \frac{la}{lb},R = \frac{ra}{rb}\)。每次移动设 \(MID = \frac{mida}{midb}=\frac{la+ra}{lb+rb}\)。若向左边儿子节点移动，让 \(R=MID\)（也就是 \(ra=mida,rb=midb\)）；，若向右边儿子节点移动，让 \(L=MID\)（也就是 \(la=mida,lb=midb\)）。之后输出新的 \(MID\)（也就是 \(\frac{la+ra}{lb+rb}\)）。

注意：切记不要手欠约分，不然会错。

#include <bits/stdc++.h>
using namespace std;
int T;
int main () {cin >> T;while (T--) {string s;int la = 0, lb = 1, ra = 1, rb = 0;  // a/bcin >> s;for (int i = 0; i <= s.length() - 1; i++) {int mida = (la + ra);int midb = (lb + rb);if (s[i] == 'L') {ra = mida;rb = midb;}else {la = mida;lb = midb;}}cout << (la + ra) << "/" << (lb + rb) << endl;}return 0;
}