洛谷-数据结构1-2-二叉树1

P4715 【深基16.例1】淘汰赛题目描述有 2nn≤7个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛胜者晋级。3 号国家和 4 号国家也踢一场胜者晋级……晋级后的国家用相同的方法继续完成赛程直到决出冠军。给出各个国家的能力值请问亚军是哪个国家输入格式第一行一个整数 n表示一共 2n 个国家参赛。第二行 2n 个整数第 i 个整数表示编号为 i 的国家的能力值1≤i≤2n能力值在 int 范围内。数据保证不存在平局。输出格式仅一个整数表示亚军国家的编号。输入输出样例输入 #1复制3 4 2 3 1 10 5 9 7输出 #1复制1实现代码#includeiostream #includequeue #includemap using namespace std; int main(){ int n; queuepairint,int q; cinn; n1n; for(int i1;in;i){ int x; cinx; q.push(make_pair(i,x)); } while(q.size()2){ pairint,int x,y; xq.front(); q.pop(); yq.front(); q.pop(); if(x.secondy.second){ q.push(x); }else{ q.push(y); } } pairint,int x,y; xq.front(); q.pop(); yq.front(); q.pop(); if(x.secondy.second){ couty.firstendl; }else{ coutx.firstendl; } return 0; }P1827 [USACO3.4] 美国血统 American Heritage题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记账员。他把他的奶牛们的家谱作成二叉树并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后创建奶牛家谱的“树的后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。你可能已经知道你可以在知道树的两种遍历以后可以经常地重建这棵树。显然这里的树不会有多于 26 个的顶点。这是在样例输入和样例输出中的树的图形表达方式C / \ / \ B G / \ / A D H / \ E F附注树的中序遍历是按照左子树根右子树的顺序访问节点树的前序遍历是按照根左子树右子树的顺序访问节点树的后序遍历是按照左子树右子树根的顺序访问节点。输入格式第一行一个字符串表示该树的中序遍历。第二行一个字符串表示该树的前序遍历。输出格式单独的一行表示该树的后序遍历。输入输出样例输入 #1复制ABEDFCHG CBADEFGH输出 #1复制AEFDBHGC说明/提示题目翻译来自NOCOW。USACO Training Section 3.4实现代码#includestring #includecstring #includeiostream #includecstdio using namespace std; string pre,inor; void work(string pre,string inor){ if(pre.empty())return; char rootpre[0]; int kinor.find(root); pre.erase(pre.begin()); string leftprepre.substr(0,k); string rightprepre.substr(k); string leftinorinor.substr(0,k); string rightinorinor.substr(k1); work(leftpre,leftinor); work(rightpre,rightinor); printf(%c,root); } int main(){ cininorpre; work(pre,inor); putchar(\n); return 0; }P5076 【深基16.例7】普通二叉树简化版题目描述您需要写一种数据结构来维护一些数都是绝对值 109 以内的数的集合最开始时集合是空的。其中需要提供以下操作操作次数 q 不超过 104定义数 x 的排名为集合中小于 x 的数的个数 1。查询数 x 的排名。注意 x 不一定在集合里。查询排名为 x(x≥1) 的数。保证集合里至少有 x 个数。求 x 的前驱前驱定义为小于 x且最大的数。若不存在则输出 −2147483647。求 x 的后继后继定义为大于 x且最小的数。若不存在则输出 2147483647。插入一个数 x本题的数据保证插入前 x 不在集合中。保证执行 1,3,4 操作时集合中有至少一个元素。输入格式第一行是一个整数 q表示操作次数。接下来 q 行每行两个整数 op,x分别表示操作序号以及操作的参数 x。输出格式输出有若干行。对于操作 1,2,3,4输出一个整数表示该操作的结果。输入输出样例输入 #1复制7 5 1 5 3 5 5 1 3 2 2 3 3 4 3输出 #1复制2 3 1 5实现代码#includeiostream #includecstdio #define re register using namespace std; const int INF0x7fffffff; int cont; struct node{ int val,siz,cnt,ls,rs; }tree[1000010]; int n,opt,xx; inline void add(int x,int v) { tree[x].siz; if(tree[x].valv){ tree[x].cnt; return ; } if(tree[x].valv){ if(tree[x].ls!0) add(tree[x].ls,v); else{ cont; tree[cont].valv; tree[cont].siztree[cont].cnt1; tree[x].lscont; } } else{ if(tree[x].rs!0) add(tree[x].rs,v); else{ cont; tree[cont].valv; tree[cont].siztree[cont].cnt1; tree[x].rscont; } } } int queryfr(int x, int val, int ans) { if (tree[x].valval) { if (tree[x].ls0) return ans; else return queryfr(tree[x].ls,val,ans); } else { if (tree[x].rs0) return tree[x].val; return queryfr(tree[x].rs,val,tree[x].val); } } int queryne(int x, int val, int ans) { if (tree[x].valval) { if (tree[x].rs0) return ans; else return queryne(tree[x].rs,val,ans); } else { if (tree[x].ls0) return tree[x].val; return queryne(tree[x].ls,val,tree[x].val); } } int queryrk(int x,int rk) { if(x0) return INF; if(tree[tree[x].ls].sizrk) return queryrk(tree[x].ls,rk); if(tree[tree[x].ls].siztree[x].cntrk) return tree[x].val; return queryrk(tree[x].rs,rk-tree[tree[x].ls].siz-tree[x].cnt); } int queryval(int x,int val) { if(x0) return 0; if(valtree[x].val) return tree[tree[x].ls].siz; if(valtree[x].val) return queryval(tree[x].ls,val); return queryval(tree[x].rs,val)tree[tree[x].ls].siztree[x].cnt; } inline int read() { re int r0; re char chgetchar(); while(ch0||ch9) chgetchar(); while(ch0ch9){ r(r3)(r1)(ch^48); chgetchar(); } return r; } signed main() { nread(); while(n--){ optread();xxread(); if(opt1) printf(%d\n,queryval(1,xx)1); else if(opt2) printf(%d\n,queryrk(1,xx)); else if(opt3) printf(%d\n,queryfr(1,xx,-INF)); else if(opt4) printf(%d\n,queryne(1,xx,INF)); else{ if(cont0){ cont; tree[cont].cnttree[cont].siz1; tree[cont].valxx; } else add(1,xx); } } return 0; }P1364 医院设置题目描述设有一棵二叉树如图其中圈中的数字表示结点中居民的人口。圈边上数字表示结点编号现在要求在某个结点上建立一个医院使所有居民所走的路程之和为最小同时约定相邻接点之间的距离为 1。如上图中若医院建在 1 处则距离和 4122×202×40136若医院建在 3 处则距离和 4×213204081。输入格式第一行一个整数 n表示树的结点数。接下来的 n 行每行描述了一个结点的状况包含三个整数 w,u,v其中 w 为居民人口数u 为左链接为 0 表示无链接v 为右链接为 0 表示无链接。输出格式一个整数表示最小距离和。输入输出样例输入 #1复制5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0输出 #1复制81说明/提示数据规模与约定对于 100% 的数据保证 1≤n≤1000≤u,v≤n1≤w≤105。实现代码#includecstdio using namespace std; int a[101],g[101][101]; int main() { int n,l,r,min,total; scanf(%d,n); for(int i1;in;i) { for(int j1;jn;j) { g[i][j]1000000; } } for(int i1;in;i) { g[i][i]0; scanf(%d%d%d,a[i],l,r); if(l0)g[i][l]g[l][i]1; if(r0)g[i][r]g[r][i]1; } for(int k1;kn;k) { for(int i1;in;i) { if(i!k) { for(int j1;jn;j) { if(i!jk!jg[i][k]g[k][j]g[i][j]) g[i][j]g[i][k]g[k][j]; } } } } min0x7fffffff; for(int i1;in;i){ total0; for(int j1;jn;j) totalg[i][j]*a[j]; if(totalmin)mintotal; } printf(%d,min); return 0; }P4913 【深基16.例3】二叉树深度题目描述有一个 n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 n建立一棵二叉树根节点的编号为 1如果是叶子结点则输入0 0。建好这棵二叉树之后请求出它的深度。二叉树的深度是指从根节点到叶子结点时最多经过了几层。输入格式第一行一个整数 n表示结点数。之后 n 行第 i 行两个整数 l、r分别表示结点 i 的左右子结点编号。若 l0 则表示无左子结点r0 同理。输出格式一个整数表示最大结点深度。输入输出样例输入 #1复制7 2 7 3 6 4 5 0 0 0 0 0 0 0 0输出 #1复制4实现代码#include iostream #define _for(i, a, b) for (int i(a); i(b); i) using namespace std; const int MAXN 1e6 10; struct node { int left, right; }; node tree[MAXN]; int n, ans; void dfs(int id, int deep) { if (id 0) return ; ans max(ans, deep); dfs(tree[id].left, deep1); dfs(tree[id].right, deep1); } int main() { cin n; _for (i, 1, n) cin tree[i].left tree[i].right; dfs(1, 1); cout ans endl; return 0; }