題意：

給出一棵樹的描述，這棵樹構(gòu)造出來，滿足從右到左數(shù)值遞增，根在最下面，然后有一些詢問x，我們要輸出從根走到x的路徑，w：向左、e：向右。

思路：

建樹的時候，首先第一個點一定是根，然后比根小的建在根的右邊，反之建在左邊，就可以了。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <map> using namespace std;const int maxn = 1005 * 2 + 10; int a[maxn]; int aa[maxn];int le[maxn], ri[maxn]; int fa[maxn]; int ha[maxn];int main() {int t, n;scanf("%d",&t);while(t--) {scanf("%d",&n);memset(aa, 0, sizeof(aa));for(int i = 1; i <= n; i++) {scanf("%d",&a[i]);}for(int i = 1; i <= n; i++) {fa[i] = i;}int tot = 1;aa[tot++] = a[1];memset(le, 0, sizeof(le));memset(ri, 0, sizeof(ri));memset(ha, 0, sizeof(ha));for(int i = 2; i <= n; i++) {int rt = 1;while(1) {if(a[i] > aa[rt]) {if(le[rt] == 0) {le[rt] = tot++;aa[le[rt]] = a[i];fa[le[rt]] = rt;ha[le[rt]] = 1;break;} else {rt = le[rt];}} else {if(ri[rt] == 0) {ri[rt] = tot++;aa[ri[rt]] = a[i];fa[ri[rt]] = rt;break;} else {rt = ri[rt];}}}}int m;int x;scanf("%d",&m);while(m--) {scanf("%d",&x);int hh = 1;int x_1 = n * 2 + 10;for(int i = 1; i <= x_1; i++) {if(aa[i] == x) {hh = i;}}string s = "";while(hh != 1) {if(ha[hh] == 0) {s += 'E';} else {s += 'W';}hh = fa[hh];}int l = s.length();if(l == 0) {puts("");continue;}for(int i = l - 1; i >= 0; i--) {printf("%c",s[i]);} puts("");}} }

總結(jié)

以上是生活随笔為你收集整理的hdu5444(2015长春网络赛H题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。