发布于2024-04-12
信息学竞赛模板（十八）——最近公共祖先
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
发布于2022-05-26
2018年第九届蓝桥杯国赛-D. 调手表
小明买了块高端大气上档次的电子手表，他正准备调时间呢。 在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 n 分钟。 有+1和+k两种操作，问从0开始最少操作多少次，能经过所有的[0,n-1]的点
发布于2022-03-23
2019年第十届蓝桥杯省赛-E.迷宫
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。 迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按 `DRRURRDDDR` 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于更复杂的迷宫，请找出字典序最小的一个最短路径为答案。
发布于2021-12-23
2016年第七届蓝桥杯省赛-G. 剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。 现在你要从中剪下 5 张来，要求必须是连着的。（仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。 请你计算，一共有多少种不同的剪取方法。
发布于2021-03-24
AcWing-177-噩梦
给定一张地图，地图中有 1 个男孩，1 个女孩和 2 个鬼。男孩每秒可以移动 3 个单位距离，女孩每秒可以移动 1 个单位距离，男孩和女孩只能朝上下左右四个方向移动。每个鬼占据的区域每秒可以向四周扩张 2 个单位距离，并且无视墙的阻挡。给定鬼和男孩女孩的初始位置，求男孩和女孩的相遇的最小时间。
发布于2021-03-24
AcWing-176-装满的油箱
有 N 个城市（编号 0、1…N−1）和 M 条道路，构成一张无向图。 在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。 现在你需要回答不超过 100 个问题，在每个问题中，请计算出一架油箱容量为 C 的车子，从起点城市 S 开到终点城市 E 至少要花多少油钱？
发布于2021-03-24
AcWing-175-电路维修
电路板的整体结构是一个 R 行 C 列的网格（R,C≤500），每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
发布于2021-03-24
AcWing-174-推箱子
给定一张 N 行 M 列的地图，用字符 `.` 表示空地，字符 `#` 表示墙，字符 `S` 表示人的起始位置，字符 `B` 表示箱子的起始位置，字符 `T` 表示箱子的目标位置。求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。
发布于2021-03-24
AcWing-172-立体推箱子
游戏地图是一个 N 行 M 列的矩阵，每个位置可能是硬地（用 `.` 表示）、易碎地面（用 `E` 表示）、禁地（用 `#` 表示）、起点（用 `X` 表示）或终点（用 `O` 表示）。你的任务是操作一个 1×1×2 的长方体。长方体在地面上有两种放置形式，“立”在地面上或者“躺”在地面上。