luogu1160:队列安排:双向链表/树的中序遍历_liusu201601的博客-程序员宅基地

技术标签: 递归  中序遍历  深搜  题解  luogu1160  双向链表  luogu  队列安排  大礼包  

题目连接

  • 该题是luogu试炼场的2-13:T4

题目大意

  1. n个数字组成的队列,多次的插入;
  2. 再删除其中m个元素;
  3. 要求输出最后的队列状态

题目分析


解题思路1:双向链表

  1. 最开始的时候队伍里只有1号同学;
  2. 接下来的n-1个同学,插入到k同学的左边或者右边;
  3. 所以每次 i 插入的时候,更新 i 左右的元素的链接。
  4. 需要记录队头,因为最后要输出。

代码:

只要搞清楚前驱和后继就好

//luogu1160:队列安排 
//双向链表 
 
#include<bits/stdc++.h>
using namespace std;
 
int n,m,x,k,p;
int f[100005],s[100005];
  
int main()
{
	scanf("%d",&n);
	memset(f,0,sizeof(f));
	memset(s,0,sizeof(s));
	
	int t=1;//队头 
	for(int i=2;i<=n;i++)//i号同学进队 
	{
		scanf("%d %d",&k,&p);
		if(p==0)//k站在 i 的左边 
		{
			f[i]=f[k]; s[i]=k;
			s[f[k]]=i; f[k]=i;
			if(k==t) t=i;//更新队头 
		}
		if(p==1)//i站在 k 的左边
		{
			f[i]=k; s[i]=s[k];
			f[s[k]]=i; s[k]=i;
		}
		
		
	}

	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&x);
		if(f[x]==0&&s[x]==0) continue;//x已经不在队列中
		
		if(t==x) t=s[x];//更新队头 
		
		s[f[x]]=s[x];//父亲的儿子更新 
		f[s[x]]=f[x];//儿子的父亲更新 
		s[x]=f[x]=0;//x出队 
	}
	
	//输出 
	for(int j=t;s[j]!=t;j=s[j])
	{
		printf("%d ",j);
	}

	return 0;
}




思路2:用树来存储,中序遍历输出

  • 将前驱放在左儿子;
  • 将后继放在有儿子;
  • 用 v 来纪录当前点是否被删除;
  • 中序便利输出答案。

代码2:

  • 结构体的使用,树的存储,中序遍历
//luogu1160:队列安排 
//树的存储与中序遍历 
 
#include<bits/stdc++.h>
using namespace std;
 
int n,m,k,p;
struct nod{int s1,s2,v;nod(){ s1=s2=v=0;} }a[100005];
//s1表示前驱,s2表示后继,v表示是否在队列内 

void dfs(int x)//中序:按 左->中->右 的顺序遍历整棵树 
{
	if(!x) return ;//空点:边界 
	
	dfs(a[x].s1);//搜前驱(左儿子) 
	
	if(a[x].v==0) printf("%d ",x);//如果自己不为空,输出
	
	dfs(a[x].s2);//搜后继(右儿子) 
	
}

int main()
{
	scanf("%d",&n);
	
	//建立树 
	for(int i=2;i<=n;i++)
	{
		scanf("%d %d",&k,&p);
		
		if(p==0)
		{
			if(a[k].s1)//k有前驱,更改 
			{
				a[i].s1=a[k].s1; 
				a[k].s1=i;
			}
			else a[k].s1=i;//k没有前驱,直接赋值 
		}
		if(p==1)
		{
			if(a[k].s2)
			{
				a[i].s2=a[k].s2;
				a[k].s2=i;
			}
			else a[k].s2=i;
		}
	}
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&k); a[k].v=1;//删除 k 点 
	} 
	
	dfs(1);//中序遍历,输出 
	
	return 0;
}



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liusu201601/article/details/89944984

智能推荐

《Unity3D网络游戏实战》第2章_yxqq378287007的博客-程序员宅基地

《Unity3D网络游戏实战》第2章异步代码异步客户端异步代码Async.csusing System;using System.Threading;namespace Async { class MainClass { public static void Main (string[] args) { Timer timer = new Timer(Timeout, null, 2000, 0); Thread.Sleep(2000*2); Console.WriteL

安装系统_iefanrui的博客-程序员宅基地

第一步、准备工作    安装系统前要做一些准备工作,首先是制作你要安装的系统的系统镜像。制作系统镜像要先下载一个UltraISO软件。然后右键点击选择“以管理员的身份运行”(注意:必须这样做)。打开后点击左上角的“文件”-—“打开”,找到存放系统镜像的目录,选中系统镜像,然后点击“打开”。然后点击 “启动”—“开始硬盘录入”,然后选择一个U盘作为系统启动盘(注意:这个U盘必须足够大,一般16G的就...

pv3d 的 Camera3D练习_suzhou_boy1的博客-程序员宅基地

 http://www.sandy1219.com/3d/test2/testflabcamera.html  package{ import flab3d.FlabCamera3D; import flash.display.Sprite; import flash.display.StageAlign; import flash.display.Stage

CAsyncSocket::Send()、OnSend()_hahahapeige的博客-程序员宅基地

virtual int Send( const void* lpBuf, int nBufLen, int nFlags = 0);Dialog中Socket设置AsyncSelect(FD_WRITE),触发虚函数OnSend(),之后调用Send()发送消息。参数lpBuf包含要传输的数据的缓冲区。nBufLen中的数据的长度lpBuf以字节为单位。nFlags...

怎么学python-新手如何自学python课程?_weixin_37988176的博客-程序员宅基地

为了Python的自学党们,传智播客真的是拼了,今天给大家讲讲新手如何自学python课程?传智播客不仅有“人工智能+Python学习路线图”,还根据以往的经验,总结出学习Python之前的各种问题,想详细了解,从此贴开始吧!!!想学Python就已经迈出了通向成功的第一步,想要通过自学成才的话,是需要很大的毅力和吃苦精神,切忌三天打鱼两天晒网。建议通过我们传智黑马论坛的python相关帖子来一步...

利用compositionstart/end事件监听输入法事件_青山院长白菜的博客-程序员宅基地_compositionstart

var flag = false;document.querySelector('input').oninput = function() { setTimeout(() =&amp;gt; { if (!flag) console.log(this.value); }, 0);};document.querySelector('input').onkeyup = function(...

随便推点

解决zabbix中文不能导入数据库和图形中文乱码的问题_运维饺子的博客-程序员宅基地

一.解决中文不能导入:先说以下没安装之前,正常的解决方法:设置数据库 :vim /etc/my.cnf在[mysqld]下添加:character_set_server=utf8并且在创建zabbix库的时候,设置utf8:create database zabbix character set utf8;以上。然后再说以下已经安装完了出现如下错误的解决方法:导出数据库:...

Django自定义模板标签与过滤器_mapyking的博客-程序员宅基地

常用内置标签:标签描述{% for %} {% endfor %}遍历输出上下文内容{% if %} {% endif %}对上下文条件进行判断{% csrf_token %}生成csrf_token标签,用于防护跨站请求伪造攻击{% url %}生成相应路由地址{% load %}加载导入django标签库{% static %}加载读取静态资源文件{% extends xxx %}使当前模板继承xxx模板

SpringBoot遗忘知识点整理_大忽悠爱忽悠的博客-程序员宅基地

SpringBoot遗忘知识点整理@[email protected]@PropertySourceSpring高级之注解@PropertySource详解(超详细)@PropertySource配置的用法@Value【Spring注解驱动开发】如何使用@Value注解为bean的属性赋值,我们一起吊打面试官!OncePerRequestFilterOncePerRequestFilter 过滤器Spring MVC应用 – 过滤器Spr

JAVA 方法重写_白帽菌的博客-程序员宅基地

子类通过重写可以隐藏已继承的方法(方法重写称为方法覆盖(method overriding))1、重写的语法规则:如果子类可以继承父类的某个方法,那么子类就有权利重写这个方法。所谓方法重写,是指子类中定义一个方法,这个方法的类型和父类的方法的类型一致或者是父类的方法的类型的子类型,并且这个方法的名字、参数个数、参数的类型和父类的方法完全相同。2、重写的目的:子类通过方法的重写可以隐藏继承的...

Android.mk 文件语法详解_一米阳光-ing的博客-程序员宅基地

转:http://blog.sina.com.cn/s/blog_602f8770010148ce.html=====================================================================================0. Android.mk简介:Android.mk文件用来告知NDK Build 系统关于Source的信息...

交换排序_hailushijie的博客-程序员宅基地

/** * 从0位置开始,依次和后面所有元素进行比较,并将小数交换到前面。 * o(N*N) * @author *冒泡排序,选择排序,插入排序,交换排序属于简单排序方法 */public class ExchangeSort { private static int[] array = new int[]{1,8,2,9,3,7,11,23,90,4,5}; public sta