Menci

眉眼如初,岁月如故

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


  1. 「NOIP2012」疫情控制 - 二分 + 倍增 + 贪心

    H 国有 n n 个城市,这 n n 个城市用 n1 n - 1 条双向道路相互连通构成一棵树,1 1 号城市是首都,也是树中的根节点。

    H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

    现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

    请问最少需要多少个小时才能控制疫情。注意,不同的军队可以同时移动。

    于  CodeVS, NOIP, 二分, 倍增, 贪心 继续阅读

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

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

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

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

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

  3. 「NOIP2012」开车旅行 - 倍增

    小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 1 N N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i i 的海拔高度为 Hi H_i ,城市 i i 和城市 j j 之间的距离 d(i,j) d(i, j) 恰好是这两个城市海拔高度之差的绝对值,即

    旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 S S 作为起点,一直向东行驶,并且最多行驶 X X 公里就结束旅行。小 A 和小 B 的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 X X 公里,他们就会结束旅行。

    在启程之前,小 A 想知道两个问题:

    1. 对于一个给定的 X=X0 X = X_0 ,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 0 0 ,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
    2. 对任意给定的 X=Xi X = X_i 和出发城市 Si S_i ,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

    于  CodeVS, NOIP, 倍增 继续阅读

  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, 搜索, 最短路 继续阅读

  5. 「NOIP2015」运输计划 - 最近公共祖先 + 二分 + 树上路径交

    在一棵树上,每条边有边权,给定 m m 个路径 uivi u_i \leftrightarrow v_i ,求将其中一条边的边权置为 0 0 ,使得 m m 个路径的长度和最小。

    于  BZOJ, CodeVS, NOIP, 最近公共祖先 继续阅读

  6. 「NOIP2015」子串 - DP

    有两个仅包含小写英文字母的字符串 A A B B 。现在要从字符串 A A 中取出 k k 个互不重叠的非空子串,然后把这 k k 个子串按照其在字符串 A A 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 B B 相等?
    注意:子串取出的位置不同也认为是不同的方案。

    于  CodeVS, DP, NOIP 继续阅读

  7. 「NOIP2015」斗地主 - 搜索

    给一组扑克牌,按照斗地主的规则出牌,求最少多少次出完。

    于  BZOJ, CodeVS, NOIP, 搜索 继续阅读

  8. 「NOIP2014」解方程 - Hash

    已知多项式方程:

    a0+a1x+a2x2++anxn=0 a_0 + a_1 x + a_2 x ^ 2 + \cdots + a_n x ^ n = 0

    求这个方程在 [1,m] [1, m] 内的整数解。

    于  BZOJ, CodeVS, Hash, NOIP, 数学 继续阅读

  9. 「NOIP2013」花匠 - 贪心

    花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。

    具体而言,栋栋的花的高度可以看成一列整数 h1,h2,,hn h_1, h_2, \ldots, h_n 。设当一部分花被移走后,剩下的花的高度依次为 g1,g2,,gm g_1, g_2, \ldots, g_m ,则栋栋希望下面两个条件中至少有一个满足:

    条件 A:对于所有的 1<i<m2 1 < i < \frac{m}{2} g2i>g2i1 g_{2i} > g_{2i - 1} g2i>g2i+1 g_{2i} > g_{2i + 1}
    条件 B:对于所有的 1<i<m2 1 < i < \frac{m}{2} g2i<g2i1 g_{2i} < g_{2i - 1} g2i<g2i+1 g_{2i} < g_{2i + 1}

    注意上面两个条件在 m=1 m = 1 时同时满足,当 m>1 m > 1 时最多有一个能满足。
    请问,栋栋最多能将多少株花留在原地。

    于  CodeVS, NOIP, 贪心 继续阅读

  10. 「NOIP2013」火柴排队 - 逆序对

    涵涵有两盒火柴,每盒装有 n n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为

    i=1n(aibi)2 \sum\limits_{i = 1} ^ n (a_i - b_i) ^ 2

    其中 ai a_i 表示第一列火柴中第 i i 个火柴的高度,bi b_i 表示第二列火柴中第 i i 个火柴的高度。

    每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?

    于  CodeVS, NOIP, 树状数组, 逆序对 继续阅读