Menci

眉眼如初,岁月如故

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


  1. 「CTSC2012」Cheat - SAM + 二分 + 单调队列 DP

    给出 m m 个串组成的「标准作文库」。对于任意一个串,如果它的长度不少于 L L 且在标准作文库中出现过,则它是「熟悉」的。对于任意一个串,如果能将它划分为若干个串,使「熟悉」的串的长度超过总长度的 90% 90\% ,则称这个串是「熟悉的文章」,定义 L0 L_0 为使这个串成为「熟悉的文章」的最大的 L L 。给出若干个串,求每个串的 L L 值。

    于  BZOJ, CTSC, DP, SAM, 二分, 单调队列, 字符串 继续阅读

  2. 「HNOI2004」高精度开根 - 高精度 + 二分

    m m 和一个高精度数 n n ,求 nm \lfloor \sqrt[m]n \rfloor

    于  BZOJ, HNOI, 二分, 高精度 继续阅读

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

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

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

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

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

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

  4. 「HAOI2008」木棍分割 - 二分 + DP

    n n 根木棍,第 i i 根木棍的长度为 Li L_i n n 根木棍依次连结了一起,总共有 n1 n - 1 个连接处。现在允许你最多砍断 m m 个连接处,砍完后 n n 根木棍被分成了很多段,要求满足总长度最大的一段长度最小,和有多少种砍的方法使得总长度最大的一段长度最小。

    于  BZOJ, DP, HAOI, 二分 继续阅读

  5. 「NOIP2012」借教室 - 二分 / 线段树

    我们需要处理接下来 n n 天的借教室信息,其中第 i i 天学校有 ri r_i 个教室可供租借。共有 m m 份订单,每份订单用三个正整数描述,分别为 dj,sj,tj d_j, s_j, t_j ,表示某租借者需要从第 sj s_j 天到第 tj t_j 天租借教室(包括第 sj s_j 天和第 tj t_j 天),每天需要租借 dj d_j 个教室。

    现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

    于  COGS, CodeVS, NOIP, 二分, 差分, 线段树 继续阅读