JLOI2009 二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为:

深度:4 宽度:4(同一层最多结点个数)

结点间距离: ⑧→⑥为8 (3×2+2=8)

⑥→⑦为3 (1×2+1=3)

注:结点间距离的定义:由结点向根方向(上行方向)时的边数×2,

与由根向叶结点方向(下行方向)时的边数之和。

 

输入输出格式

输入格式:

输入文件第一行为一个整数n(1≤n≤100),表示二叉树结点个数。接下来的n-1行,表示从结点x到结点y(约定根结点为1),最后一行两个整数u、v,表示求从结点u到结点v的距离。

输出格式:

三个数,每个数占一行,依次表示给定二叉树的深度、宽度及结点u到结点v间距离。

无耻的借用洛谷的图片

这题就是个智障

首先dfs一下然后bfs一下然后lca一波就行了

一开始忘记讨论深度了然后使劲在那WA。。

//我知道不用写LCA和BFS但我就是想写你打我啊!!!!

IOI1998 Starry Night 夜空繁星

BFS,超级麻烦

推荐A这道模拟方块转换

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图所示。(图片搬运自Luogu Online Judge)

 

 

懒癌了,我就贴上来吧……我用了一个特殊的表来判断是不是相似

详见代码

 

 

 

 

USACO 玉米田迷宫 Corn Maze

这题是一个大坑。

首先我们想到了BFS,这个题就是一个简单到不能再简单的Maze加上传送门就是了。

但是有一点是传送门不费时啊!!什么鬼。所以我们要先判传送门

为什么呢?我记得有一组测试数据包括了这种情况

 

这不清真

另外,好像还有一个点是全都是传送门的情况。

 

 

这也不清真

 

判传送门(并不是判队首元素位于传送门,而是队首坐标移动之后),传送过去之后耗时不加,队列保存传送后的位置,这样就不会产生无限传送死循环的问题。

但是关于情况2怎么办?我们利用BFS的性质,把传送门(传过去之后)打上标记,然后就不用他了。(每一次用都是最早用他)

传送门I hate you

 

读入的时候记录传送门的相对坐标,像这样:

 

之后碰到传送门直接查表。,顺便记下起点sxsy和重点exey

 

 

其实这个题处理好了传送门,你会发现,其实不难……(输出调试大法好)

记得用checked数组标记已经访问的点和传送门,要不无限使用传送门

 

[USACO07OCT] 障碍路线Obstacle Course

这道题可以用一个特殊的BFS来求解。每次把队首元素四个方向上的点扩展到队尾,用桶来记录转弯次数。

1.初始状态

A(起点)的转弯次数为-1。

2.产生结点的规则

现在,起点位于队首。

从队首的点向四周逐“层”扩展,每一“层”扩展到的新点入队列,这些新点显然不需要转弯就可以达到(起点任意方向),所以他们的转弯次数记录为0 (也就是起点+1,你的疑问马上就会得到解答)

这就是产生新结点的策略。

3.记录每个点的转弯次数

扩展到的新点的转弯次数=队首点的转弯次数+1。(由于BFS的特点,新点未被访问过才可以被加入队尾)

下面是证明。

如果扩展到的新点是不转90°(直走)就可以到的,那该点一定被扩展了队首点的点(队首点的父结点,不知道这么说对不对)访问过,此时该点不会被当作新点处理。同理,转弯180°的点也一定被扩展了队首点的点访问过。

所以,扩展到的新点一定是转弯90°(左或右)才能走到的。

此时,到新点的转弯次数=队首点的转弯次数+1。

证明完毕。