BZOJ1085 | SCOI2005 骑士精神

这题很经典也很简单就不放思路了QAQ

留个代码防我健忘

 

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但我就是想写你打我啊!!!!

#洛谷 P1120 小木棍

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。

现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

先写一个暴力……

暴力最好写了,然后再考虑剪枝

这是暴力:记录一下当前那根大木棍已经接了多长,已经接了多少根大木棍和一根大木棍应该有多长。

当然暴力也可以加一个简单的剪枝:记录一下总长度,如果当前枚举的一根大木棍的应有长度不能整除总长度那就不搜。

然后剪枝:

1.我们按长度排序,如果当前正在拼一根新的木棍,而且最大的一根小木棍加上当前的长度(应该是0)都不能满足枚举到的当前大木棍长度那就剪掉。

2.还是上述操作,不过是剪掉:整整一根小木棍都比当前枚举到的大木棍的长度长的情况(那样显然无解)

3.还是排序之后,记录一下上次尝试了哪一根小木棍(也就是长度)如果这次枚举到的小木棍的长度和上次相等那么也剪掉。

4.如果搜的目标是拼最后一根大木棍了,而且最后还无解,回溯回来了,那这组直接放弃。

就这些?

对,一共就这么六个剪枝 (排序&暴力的剪枝&1234)

试试刚刚才意识到的高亮操作

#洛谷P1312 Mayan游戏

大模拟+搜索

写了一个下午 这么弱也是没谁了。

题目描述

Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个 7 行5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:

1 、每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图6 到图7 );如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图1 和图2);

2 、任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参见图1 到图3)。

注意:

a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图4 ,三个颜色为1 的方块和三个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块)。

b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除(例如下面图5 所示的情形,5 个方块会同时被消除)。

3 、方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。

上面图1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0, 0 ),将位于(3, 3 )的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态,此时在一竖列上有连续三块颜色为4 的方块,满足消除条件,消除连续3 块颜色为4 的方块后,上方的颜色为3 的方块掉落,形成图 3 所示的局面。

说明

【输入输出样例说明】

按箭头方向的顺序分别为图6 到图11

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是:(2 ,1 )处的方格向右移动,(3,1 )处的方格向右移动,(3 ,0)处的方格向右移动,最后可以将棋盘上所有方块消除。

【数据范围】

对于30% 的数据,初始棋盘上的方块都在棋盘的最下面一行;

对于100%的数据,0 < n≤5 。

注意剪枝:

1.向左面换的话只有左面是空才换(要不然等价于左面那块向右,而且解不比那样优)

2.剩下不足三个剪掉

3.走了n+1步没搞完剪掉

4.同样色块没必要换

注意处理消除:

1.超过三个都能消掉

2.注意共用一块,最好解决方案是复制下来判断

3.注意消完之后要处理下落,还有可能能继续消,开一个flag判断。

Codeforces Round#124B Infinite Maze

题目描述

We’ve got a rectangular n × m-cell maze. Each cell is either passable, or is a wall (impassable). A little boy found the maze and cyclically tiled a plane with it so that the plane became an infinite maze. Now on this plane cell (x, y) is a wall if and only if cell  is a wall.

In this problem  is a remainder of dividing number a by number b.

The little boy stood at some cell on the plane and he wondered whether he can walk infinitely far away from his starting position. From cell (x, y) he can go to one of the following cells: (x, y - 1)(x, y + 1)(x - 1, y) and (x + 1, y), provided that the cell he goes to is not a wall.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1500) — the height and the width of the maze that the boy used to cyclically tile the plane.

Each of the next n lines contains m characters — the description of the labyrinth. Each character is either a “#“, that marks a wall, a “.“, that marks a passable cell, or an “S“, that marks the little boy’s starting point.

The starting point is a passable cell. It is guaranteed that character “S” occurs exactly once in the input.

Output

Print “Yes” (without the quotes), if the little boy can walk infinitely far from the starting point. Otherwise, print “No” (without the quotes).

什么玩意……还是看看翻译

幻象迷宫可以认为是无限大的,不过它由若干个N*M的矩阵重复组成。矩阵中有的地方是道路,用’.’表示;有的地方是墙,用’#’表示。LHX和WD所在的位置用’S’表示。也就是对于迷宫中的一个点(x,y),如果(x mod n,y mod m)是’.’或者’S’,那么这个地方是道路;如果(x mod n,y mod m)是’#’,那么这个地方是墙。The Little Boy可以向上下左右四个方向移动,当然不能移动到墙上。

请你告诉他能否走出幻象迷宫,如果他能走到距离起点无限远处,就认为能走出去。

也是好久之前做的题了,一开始被题意卡了好久,果然语文不好毁一生啊……

大概就是说给出一个01迷宫类的地图,按照这个地图来扩展新地图,类似这样

然后问你是不是可以走无限远。

那么,我们可以很清晰的意识到,如果可以从点(x,y)出发,达到比如(-x,y)或者(x,-y) , (-x,-y) , (x+m,y+n) [假设宽m高n]  , 就可以从这个点再次达到相同的点(即可以从(x,y)出发,达到(i,j)且|i|%n=x , |j|%m=y。),一直这么走下去。

那就搜好了。开一个三维vis数组第一维记录有无被访问,第二维记录被访问时横坐标,第三维纵坐标。

判断重复到达且横纵坐标不同即可。应该注意先判什么后判什么。如果是同一个分矩阵走过去的话自然tx==vis[x][y][0]此处x为|tx|%n,y为|ty|%m,即映射到中心矩阵的位置),就会被判掉。

而且注意tx!=vis[x][y][0]ty!=vis[x][y][1]满足一个即可。

没啥好说的了。。。数据很大注意搜索优化。