做网站的主要任务,东莞网站建设培训学校,合肥市芜湖官网设计,建筑网片钢筋网片文章目录 题目【深基16.例1】淘汰赛题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路#xff1a;代码 【深基16.例3】二叉树深度题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路#xff1a;代码 [USACO3.4] 美国血统 American Heritage题目描… 文章目录 题目【深基16.例1】淘汰赛题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路代码 【深基16.例3】二叉树深度题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1基本思路代码 [USACO3.4] 美国血统 American Heritage题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示基本思路 题目
【深基16.例1】淘汰赛
题目描述
有 2 n 2^n 2n n ≤ 7 n\le7 n≤7个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛胜者晋级。3 号国家和 4 号国家也踢一场胜者晋级……晋级后的国家用相同的方法继续完成赛程直到决出冠军。给出各个国家的能力值请问亚军是哪个国家
输入格式
第一行一个整数 n n n表示一共 2 n 2^n 2n 个国家参赛。
第二行 2 n 2^n 2n 个整数第 i i i 个整数表示编号为 i i i 的国家的能力值 1 ≤ i ≤ 2 n 1\leq i \leq 2^n 1≤i≤2n。
数据保证不存在平局。
输出格式
仅一个整数表示亚军国家的编号。
样例 #1
样例输入 #1
3
4 2 3 1 10 5 9 7样例输出 #1
1基本思路
这道题数据量比较小(n7)我是暴力模拟过的从第n层开始选拔每次选拔人数会减少一半到第一层即v[0]只剩下1人这个人就是冠军第二层较小的即为亚军。
代码
#includebits/stdc.h
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i a; i n; i)
#define rep(i,a,n) for(int i a; i n; i)
typedef pairint,int PII;
int n;
vectorpairint,int v[10];//分别保存能力值和编号void solve(){cinn;int lenpow(2,n);for(int i1;ilen;i){int x; cinx;v[n].push_back({x,i});//第n层一共n人}for(int in;i0;i--){int lenpow(2,i);for(int j0;jlen;j2){//两两比较找到胜者晋级到上一层if(v[i][j].fiv[i][j1].fi)v[i-1].push_back({v[i][j].fi,v[i][j].se});elsev[i-1].push_back({v[i][j1].fi,v[i][j1].se});}}/*for(int in;i0;i--){int lenpow(2,n);for(int j0;jv[i].size();j){coutv[i][j].fi ;}coutendl;}*/if(v[1][0].fiv[1][1].fi)//这层存的是冠军和亚军找到较小者为亚军coutv[1][1].seendl;elsecoutv[1][0].seendl;
}signed main(){IOS;int T1;while(T--){solve();}return 0;
}【深基16.例3】二叉树深度
题目描述
有一个 n ( n ≤ 1 0 6 ) n(n \le 10^6) n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 n n n建立一棵二叉树根节点的编号为 1 1 1如果是叶子结点则输入 0 0。
建好这棵二叉树之后请求出它的深度。二叉树的深度是指从根节点到叶子结点时最多经过了几层。
输入格式
第一行一个整数 n n n表示结点数。
之后 n n n 行第 i i i 行两个整数 l l l、 r r r分别表示结点 i i i 的左右子结点编号。若 l 0 l0 l0 则表示无左子结点 r 0 r0 r0 同理。
输出格式
一个整数表示最大结点深度。
样例 #1
样例输入 #1
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0样例输出 #1
4基本思路
一道求二叉树深度的题可以用dfs或者bfs求每个节点的深度详细请看代码。
代码
#includebits/stdc.h
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i a; i n; i)
#define rep(i,a,n) for(int i a; i n; i)
typedef pairint,int PII;
const int N 1000010;
struct Node{int l,r;int depth;
}tree[N];
int n,maxdepth;//dfs求深度
inline void dfs(int x){if(tree[x].l){tree[tree[x].l].depthtree[x].depth1;maxdepthmax(maxdepth,tree[tree[x].l].depth);dfs(tree[x].l);}if(tree[x].r){tree[tree[x].r].depthtree[x].depth1;maxdepthmax(maxdepth,tree[tree[x].r].depth);dfs(tree[x].r);}
}void solve(){cinn;for(int i1;in;i){int x,y; cinxy;if(x)tree[i].lx;if(y)tree[i].ry;}//一 dfs求深度//tree[1].depth1;//dfs(1);//二 或者bfs求深度queueNode q;tree[1].depth1;q.push(tree[1]);while(!q.empty()){auto tq.front();q.pop();if(t.l){//左子树存在tree[t.l].deptht.depth1;//左儿子的深度等于当前节点深度1maxdepthmax(maxdepth,tree[t.l].depth);//找到深度的最大值q.push(tree[t.l]);} if(t.r){//右子树存在tree[t.r].deptht.depth1;maxdepthmax(maxdepth,tree[t.r].depth);q.push(tree[t.r]);}}
// for(int i1;i7;i)
// couttree[i].depth ;coutmaxdepthendl;
}signed main(){IOS;int T1;while(T--){solve();}return 0;
}[USACO3.4] 美国血统 American Heritage
题目描述
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。显然这里的树不会有多于 26 26 26 个的顶点。
这是在样例输入和样例输出中的树的图形表达方式 C/ \/ \B G/ \ /A D H/ \E F
附注
树的中序遍历是按照左子树根右子树的顺序访问节点树的前序遍历是按照根左子树右子树的顺序访问节点树的后序遍历是按照左子树右子树根的顺序访问节点。
输入格式
第一行一个字符串表示该树的中序遍历。
第二行一个字符串表示该树的前序遍历。
输出格式
单独的一行表示该树的后序遍历。
样例 #1
样例输入 #1
ABEDFCHG
CBADEFGH样例输出 #1
AEFDBHGC提示
题目翻译来自NOCOW。
USACO Training Section 3.4
基本思路
给出先序遍历和中序遍历求后序遍历1我们知道先序遍历最后一个节点为根节点找到这个根节点在中序遍历中的位置i。2i的左边即为该根节点的左子树右边即为右子树。此时通过分析中序遍历找到左子树的大小再次确定左子树中根节点的位置右子树同理。3继续重复步骤1、2不断递归即可。 题目中要求后序遍历在建树中输出即可求得。求后序遍历的话画图分析就清晰多了ヾ(≧▽≦*)o #includebits/stdc.h
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i a; i n; i)
#define rep(i,a,n) for(int i a; i n; i)
typedef pairint,int PII;
const int N 27;
string pre,mid;//存放前序遍历和中序遍历
int n;//二叉树节点个数 void build_tree(int lp,int rp,int lm,int rm){//前序左边界右边界、中序左边界有边界 if(lprp) return;//越界了 char rootpre[lp];//找到根节点前序根左右 //需要找到根节点root在中序的位置 //通过根节点找到左子树和右子树int ilm;//i即为分界线 while(mid[i]!rootirm)i;build_tree(lp1,lp(i-lm),lm,i-1); //左子树build_tree(lp(i-lm)1,rp,i1,rm);//右子树..coutroot;//左右根此时不断输出即为后序遍历
}void solve(){cinmidpre;//中序、前序 nmid.size();//字符串长度 mid mid,pre pre; build_tree(1,n,1,n);//前序1-n,中序1-n
}signed main(){IOS;int T1;while(T--){solve();}return 0;
}
