跳至正文

USACO 3.4.2 American Heritage 解题报告

  • OI路程

算法本质:树的遍历性质和深搜 算  法:先从中序遍历找出哪一个是根,即在先序遍历中下标最小的那个节点,这个节点向左就是左子树,向右就是右子树。 复杂度:空间&时间O(n) / LANG:C ID: yylgoo1 PROG: heritage / #include #include #include #define INF 0x7FFFFFFF char a[27], b[27]; int or[26]; void srch(int start, int end) { int i; int mid = -1, min = INF; if(start < end){ return; } for(i = start; i or[a[i] - 'A']){ min = or[a[i] - 'A']; mid = i; } } srch(start, mid - 1); srch(mid + 1, end); printf("%c", a[mid]); } int main(void) { int i, len; freopen("heritage.in", "r", stdin); freopen("heritage.out", "w", stdout); scanf("%s%s", a, b); len = strlen(a); for(i = 0; i <len i orbi - A="i;" srch len - printfn return code>

发表评论

您的电子邮箱地址不会被公开。