Menci

眉眼如初,岁月如故

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


  1. 「NOI2015」小园丁与老司机 - DP + 上下界网络流

    在坐标系的第一象限内有 n n 个点。

    1. 从原点开始,每次向左、右、上、左上 45 45 ^ \circ 、右上 45 45 ^ \circ 任意一个方向走到第一个未到过的点,重复这个过程,求最多能经过多少点;
    2. 求 (1) 中的一个最优方案;
    3. 对于 (1) 中的所有最优方案,其所有上、左上 45 45 ^ \circ 、右上 45 45 ^ \circ 的边组成了一个 DAG,求该 DAG 的可重叠最小路径覆盖。

    于  BZOJ, DP, Dinic, NOI, 上下界网络流, 网络流 继续阅读

  2. 「NOI2015」品酒大会 - 后缀数组 + 并查集

    给定字符串 S S 和序列 f(i) f(i) ,对于 r[0, n1] r \in [0,\ n - 1] ,求:

    1. 满足 LCP(suffix(i), suffix(j))r \mathrm {LCP}(\mathrm{suffix}(i),\ \mathrm{suffix}(j)) \geq r 的无序二元组 (i, j) (i,\ j) 数量;
    2. 上述二元组 (i,j) (i, j) 使 f(i)×f(j) f(i) \times f(j) 取得的最大值。

    于  BZOJ, NOI, 后缀数组, 字符串, 并查集 继续阅读

  3. 「NOI2014」起床困难综合征 - 位运算 + 贪心

    drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n n 扇防御门组成。每扇防御门包括一个运算 和一个参数 t t ,其中运算一定是 中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为 x x ,则其通过这扇防御门后攻击力将变为 。最终 drd 受到的伤害为对方初始攻击力 x x 依次经过所有 n n 扇防御门后转变得到的攻击力。 由于 atm 水平有限,他的初始攻击力只能为 0 0 m m 之间的一个整数(即他的初始攻击力只能在 0 0 1 1 m m 中任选,但在通过防御门之后的攻击力不受 m m 的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害。

    于  BZOJ, NOI, 位运算, 贪心 继续阅读

  4. 「NOI2006」最大获利 - 最大权闭合图

    在前期市场调查和站址勘测之后,公司得到了一共 N N 个可以作为通讯信号中转站的地址,建立第 i i 个通讯中转站需要的成本为 Pi Pi )。另外公司调查得出了所有期望中的用户群,一共 M M 个。关于第 i i 个用户群的信息概括为 Ai Ai , Bi Bi Ci Ci :这些用户会使用中转站 Ai Ai 和中转站 Bi Bi 进行通讯,公司可以获益 Ci Ci 。( )公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?

    于  BZOJ, CodeVS, Dinic, NOI, 图论, 最大权闭合图, 最小割, 网络流 继续阅读

  5. 「NOI2003」文本编辑器 - Splay

    操作名称 输入文件中的格式 功能
    Move k 将光标移动到第 k k 个字符之后,如果 k=0 k=0 ,将光标移到文本第一个字符之前
    Insert n S 在光标后插入长度为 n n 的字符串 s s ,光标位置不变,
    Delete n 删除光标后的 n n 个字符,光标位置不变,
    Get n 输出光标后的 n n 个字符,光标位置不变,
    Prev 光标前移一个字符
    Next 光标后移一个字符

    于  BZOJ, NOI, Splay, 数据结构, 高级数据结构 继续阅读

  6. 「NOI2004」郁闷的出纳员 - Splay

    工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。老板经常到我这边来询问工资情况,现在工资第 k 多的员工拿多少工资。

    于  BZOJ, CodeVS, NOI, Splay, 数据结构, 高级数据结构 继续阅读

  7. 「NOI2015」软件包管理器 - 树链剖分

    你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包 A 依赖软件包 B,那么安装软件包 A 以前,必须先安装软件包 B。同时,如果想要卸载软件包 B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除 0 号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而 0 号软件包不依赖任何一个软件包。依赖关系不存在环,当然也不会有一个软件包依赖自己。用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态。

    于  BZOJ, CodeVS, NOI, 数据结构, 树链剖分, 高级数据结构 继续阅读

  8. 「NOI2015」程序自动分析 - 离散化 + 并查集

    给定 n 个形如xi=xjx_i=x_j 的变量相等 / 不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。

    于  BZOJ, CodeVS, NOI, map, 哈希, 并查集, 离散化 继续阅读

  9. 「NOI2002」银河英雄传说 - 并查集

    有 30000 个元素,初始时每个元素以单独的队列形式存在,支持一下两种操作:

    1.动态合并两条队列,将 x 元素所在队列首合并在 y 元素所在队列尾;
    2.查询 xy 是否在同一条队列中,若是,查询 xy 间隔元素数量。

    共 500,000 次操作。

    于  CodeVS, NOI, 并查集 继续阅读