Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「HAOI2008」移动玩具 - 状态压缩 + BFS

    在一个 4×4 4 \times 4 的方框内摆放了若干个相同的玩具,要将这些玩具重新摆放成为理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动到的位置不能有玩具,求最小移动次数。

    于  BFS, BZOJ, HAOI, 状态压缩 继续阅读

  2. 「NOIP2016」愤怒的小鸟 - 状态压缩 + BFS

    Kiana 最近沉迷于一款神奇的游戏无法自拔。

    简单来说,这款游戏是在一个平面上进行的。

    有一架弹弓位于 (0,0) (0, 0) 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 y=ax2+bx y = ax ^ 2 + bx 的曲线,其中 a a b b 是 Kiana 指定的参数,且必须满足 a<0 a < 0

    当小鸟落回地面(即 x x 轴)时,它就会瞬间消失。

    在游戏的某个关卡里,平面的第一象限中有 n n 只绿色的小猪,其中第 i i 只小猪所在的坐标为 (xi,yi) (x_i, y_i)

    如果某只小鸟的飞行轨迹经过了(xi,yi) (x_i, y_i) ,那么第 i i 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

    如果一只小鸟的飞行轨迹没有经过(xi,yi) (x_i, y_i) ,那么这只小鸟飞行的全过程就不会对第 i i 只小猪产生任何影响。

    例如,若两只小猪分别位于 (1,3) (1, 3) (3,3) (3, 3) ,Kiana 可以选择发射一只飞行轨迹为 y=x2+4x y = -x ^ 2 + 4x 的小鸟,这样两只小猪就会被这只小鸟一起消灭。

    而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

    这款神奇游戏的每个关卡对 Kiana 来说都很难,所以 Kiana 还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在「输入格式」中详述。

    假设这款游戏一共有 T T 个关卡,现在 Kiana 想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

    于  BFS, NOIP, 搜索, 状态压缩 继续阅读

  3. 「NOIP2010」引水入城 - BFS + DP

    在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个 N N M M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。

    为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此,只有与湖泊毗邻的第 1 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。

    由于第 N N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

    于  BFS, CodeVS, DP, NOIP, 线性 DP 继续阅读

  4. 「NOIP2013」华容道 - BFS + SPFA

    1. 在一个 n×m n \times m 棋盘上有 n×m n\times m 个格子,其中有且只有一个格子是空白的,其余 n×m1 n \times m - 1 个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 1 \times 1 的;
    2. 有些棋子是固定的,有些棋子则是可以移动的;
    3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

    给定一个棋盘,游戏可以玩 q q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i i 次玩的时候,空白的格子在第 EXi EX_i 行第 EYi EY_i 列,指定的可移动棋子的初始位置为第 SXi SX_i 行第 SYi SY_i 列,目标位置为第 TXi TX_i 行第 TYi TY_i 列。

    假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

    于  BFS, CodeVS, NOIP, SPFA, 搜索, 最短路 继续阅读