首页 > 其他分享 >洛谷P4715 【深基16.例1】淘汰赛

洛谷P4715 【深基16.例1】淘汰赛

时间:2023-07-10 22:55:57浏览次数:42  
标签:P4715 国家 No int 题解 深基 淘汰赛 二叉树 编号

写在前面

这是本蒟蒻的第三篇题解。由于作者水平不高,本题解存在有数量庞大的错误。对于题解中的错误、可优化部分,欢迎各位大佬批评指正!不合适的部分,还请多多包涵!
本题目来源于洛谷。网址https://www.luogu.com.cn/problem/P4715。
本博客非营利性,如遇侵权,请联系作者删除,谢谢!

题面

【深基16.例1】淘汰赛

题目描述

有 \(2^n\)(\(n\le7\))个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值,且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛,胜者晋级。3 号国家和 4 号国家也踢一场,胜者晋级……晋级后的国家用相同的方法继续完成赛程,直到决出冠军。给出各个国家的能力值,请问亚军是哪个国家?

输入格式

第一行一个整数 \(n\),表示一共 \(2^n\) 个国家参赛。

第二行 \(2^n\) 个整数,第 \(i\) 个整数表示编号为 \(i\) 的国家的能力值(\(1\leq i \leq 2^n\))。

数据保证不存在平局。

输出格式

仅一个整数,表示亚军国家的编号。

样例 #1

样例输入 #1

3
4 2 3 1 10 5 9 7

样例输出 #1

1

题目解释

这道题无非就是用找最终晋级决赛的两队中能力较弱的一支,纯纯的模拟题……
但是!
他挖了个坑……
你以为排序完找第二大的就完事了?远没有你想的那么简单!
事实上,如果排名第二的队伍很不幸与第一(最后的冠军)在决赛前相遇,根据题意,第一会打败第二,第二也无法晋级决赛。因此,亚军不一定就是能力第二名。这句话有点费脑子,还请消化理解一下……
只要意识到这一点,整道题立马就迎刃而解了:我们用两个二叉树分别存储国家编号和能力,然后输出第二层能力较小者的编号,完毕。
等等,为什么是两个二叉树,找一个存储编号?一般编号不是直接用下标的吗?
由于一开始是初赛,因此两个二叉树只有叶子结点能存入初始数据……有点麻烦,要不,再理解理解?
理解完了?好,咱们进入下一步!

代码实现

前期准备

(不用解释了吧)

int a[260],No[260];//分别存储能力和编号 
int n;

搜索进行时

void dfs(int x)//x作下标 
{
	if(x>=1<<n)//"1<<n"表示2^n 
	{
		return;//遍历完全部,结束 
	}
	dfs(2*x);//遍历左子树 
	dfs(2*x+1);//遍历右子树 
	if(a[2*x]>a[2*x+1])//如果左侧胜利 
	{
		a[x]=a[2*x];//胜利方编号、能力为左侧 
		No[x]=No[2*x];
	}
	else//右侧胜利亦然 
	{
		a[x]=a[2*x+1];
		No[x]=No[2*x+1];
	}
}

被迫工作的主函数

int main()
{
	cin>>n;
	for(int i=0;i<1<<n;i++)
	{
		cin>>a[i+(1<<n)];//输入能力值 
		No[i+(1<<n)]=i+1; //由于i由0启用,而题目编号由1启用,故需+1 
	}
	dfs(1);
	if(a[2]>a[3])//左侧为冠军 
		cout<<No[3];//输出右侧的亚军 
	else//反之亦然 
		cout<<No[2];
	return 0;
}     

完整代码

#include<bits/stdc++.h>
using namespace std;
int a[260],No[260];
int n;
void dfs(int x)
{
	if(x>=1<<n)
	{
		return;
	}
	dfs(2*x); 
	dfs(2*x+1);
	if(a[2*x]>a[2*x+1])
	{
		a[x]=a[2*x];
		No[x]=No[2*x];
	}
	else
	{
		a[x]=a[2*x+1];
		No[x]=No[2*x+1];
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<1<<n;i++)
	{
		cin>>a[i+(1<<n)]; 
		No[i+(1<<n)]=i+1;  
	}
	dfs(1);
	if(a[2]>a[3])
		cout<<No[3];
	else
		cout<<No[2];
	return 0;
}                                         

请注意

  • 题目数据最大值就到\(2^8\),因此数组到260就绝对没有问题
  • 用不惯左移,用pow(2,n)也是可以的,只是效率会明显比作为位运算的左移低
  • 二叉树中的公式:第x个结点,其左结点为2x,右结点为2x+1 (话说这个都不知道大概也用不了二叉树)
  • 主函数内存编号的i+1在“代码实现”中已经讲了,可以再看一下

时间复杂度

题目最大n值为\(8\),在此值下,总循环次数估计值为\(512\)(\(2^9\))。很明显,通过绝对没有问题。
以下为洛谷运行结果:

写在最后

这次的题解花了1小时,越来越快了 <( ̄︶ ̄)> !不知质量有没有下降?
再次表示:
这是本蒟蒻的第二篇题解。由于作者水平不高,本题解存在有数量庞大的错误。对于题解中的错误、可优化部分,欢迎各位大佬批评指正!不合适的部分,还请多多包涵!
本题目来源于洛谷。网址https://www.luogu.com.cn/problem/P4715。
本博客非营利性,如遇侵权,请联系作者删除,谢谢!
最后,都看到这里了,不推荐一个再走吗?

THE END~

标签:P4715,国家,No,int,题解,深基,淘汰赛,二叉树,编号
From: https://www.cnblogs.com/httony/p/17542590.html

相关文章

  • 【深基13.例1】查找
    【深基13.例1】查找题目描述输入\(n\)个不超过\(10^9\)的单调不减的(就是后面的数字不小于前面的数字)非负整数\(a_1,a_2,\dots,a_{n}\),然后进行\(m\)次询问。对于每次询问,给出一个整数\(q\),要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出\(-1\)。输入......
  • P5717 【深基3.习8】三角形分类
    【深基3.习8】三角形分类题目描述给出三条线段$a,b,c$的长度,均是不大于$10000$的正整数。打算把这三条线段拼成一个三角形,它可以是什么三角形呢?如果三条线段不能组成一个三角形,输出Nottriangle;如果是直角三角形,输出Righttriangle;如果是锐角三角形,输出Acutetriangle;......
  • P5716 【深基3.例9】月份天数
    【深基3.例9】月份天数题目描述输入年份和月份,输出这一年的这一月有多少天。需要考虑闰年。输入格式输入两个正整数,分别表示年份$y$和月数$m$,以空格隔开。输出格式输出一行一个正整数,表示这个月有多少天。样例#1样例输入#119268样例输出#131样例#2样例输入......
  • P2433 【深基1-2】小学数学 N 合一
    【深基1-2】小学数学N合一题目描述问题1请输出IloveLuogu!问题2这里有$10$个苹果,小A拿走了$2$个,Uim拿走了$4$个,八尾勇拿走剩下的所有的苹果。我们想知道:小A和Uim两个人一共拿走多少苹果?八尾勇能拿走多少苹果?现在需要编写一个程序,输出两个数字作为答......
  • P5709 【深基2.习6】Apples Prologue / 苹果和虫子
    【深基2.习6】ApplesPrologue/苹果和虫子题目描述八尾勇喜欢吃苹果。她现在有$m$($1\lem\le100$)个苹果,吃完一个苹果需要花费$t$($0\let\le100$)分钟,吃完一个后立刻开始吃下一个。现在时间过去了$s$($1\les\le10000$)分钟,请问她还有几个完整的苹果?输入格式输入三......
  • P5710 【深基3.例2】数的性质
    【深基3.例2】数的性质题目描述一些整数可能拥有以下的性质:性质1:是偶数;性质2:大于$4$且不大于$12$。小A喜欢这两个性质同时成立的整数;Uim喜欢这至少符合其中一种性质的整数;八尾勇喜欢刚好有符合其中一个性质的整数;正妹喜欢不符合这两个性质的整数。现在给出一个整数......
  • P5706 【深基2.例8】再分肥宅水
    【深基2.例8】再分肥宅水题目描述现在有$t$毫升肥宅快乐水,要均分给$n$名同学。每名同学需要$2$个杯子。现在想知道每名同学可以获得多少毫升饮料(严格精确到小数点后$3$位),以及一共需要多少个杯子。输入格式输入一个实数$t$和一个正整数$n$,使用空格隔开。输出格式......
  • P5708 【深基2.习2】三角形面积
    【深基2.习2】三角形面积题目描述一个三角形的三边长分别是$a$、$b$、$c$,那么它的面积为$\sqrt{p(p-a)(p-b)(p-c)}$,其中$p=\frac{1}{2}(a+b+c)$。输入这三个数字,计算三角形的面积,四舍五入精确到$1$位小数。输入格式第一行输入三个实数$a,b,c$,以空格隔开。输出格式输出......
  • P5707 【深基2.例12】上学迟到
    【深基2.例12】上学迟到题目描述学校和yyy的家之间的距离为$s$米,而yyy以$v$米每分钟的速度匀速走向学校。在上学的路上,yyy还要额外花费$10$分钟的时间进行垃圾分类。学校要求必须在上午$\textrm{8:00}$到达,请计算在不迟到的前提下,yyy最晚能什么时候出门。由于......
  • P5703 【深基2.例5】苹果采购
    题目描述输入两个整数$a,b$,输出它们的和($|a|,|b|\le{10}^9$)。注意Pascal使用integer会爆掉哦!有负数哦!C/C++的main函数必须是int类型,而且C最后要return0。这不仅对洛谷其他题目有效,而且也是NOIP/CSP/NOI比赛的要求!好吧,同志们,我们就从这一题开始,向着大牛......