Menci

眉眼如初,岁月如故

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


  1. 「SCOI2005」王室联邦 - 树分块

    他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成员来管理。他的国家有 n n 个城市,编号为 1n 1 \ldots n 。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。

    每个省至少要有 B B 个城市,最多只有 3B 3B 个城市。

    每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。

    一个城市可以作为多个省的省会。

    于  BZOJ, SCOI, 分块, 数据结构, 树分块 继续阅读

  2. 「AHOI2013」作业 - 莫队

    给一个长度为 n n 的序列,每次查询一个区间 x[l,r] x \in [l, r] 内满足 aixbi a_i \leq x \leq b_i x x 的数量和不重复的 x x 的数量。

    于  AHOI, BZOJ, 数据结构, 莫队 继续阅读

  3. 「BZOJ 3289」Mato 的文件管理 - 莫队

    给一个长度为 n n 的序列,每次求一个区间 [l,r] [l, r] 的逆序对数。

    于  BZOJ, 数据结构, 莫队 继续阅读

  4. 「BZOJ 2120」数颜色 - 带修改莫队

    墨墨购买了一套 N N 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。
    墨墨会像你发布如下指令:

    1. Q L R 代表询问你从第 L L 支画笔到第 R R 支画笔中共有几种不同颜色的画笔。
    2. R P Col 把第 P P 支画笔替换为颜色 Col \text{Col}

    为了满足墨墨的要求,你知道你需要干什么了吗?

    于  BZOJ, 数据结构, 莫队 继续阅读

  5. RMQ 模板

    RMQ 稀疏表(Sparse Table)的模板。

    zyz 大佬的评价

    于  RMQ, 数据结构, 算法模板 继续阅读

  6. Splay 模板 + 详细注释

    普通平衡树的模板。

    插入、查询、删除、前趋、后继、排名、选择。

    zyz 大佬的评价

    于  Splay, 数据结构, 算法模板, 高级数据结构 继续阅读

  7. 「NOI2008」糖果雨 - 坐标变换 + 二维树状数组

    在一个长度为 len \mathrm{len} 的区间上,有以下操作:

    1. t t 时刻,出现一条线段 [l,r] [l, r] ,这条线段将要向左或向右移动;
    2. t t 时刻查询与线段 [l,r] [l, r] 有公共点的线段有多少;
    3. t t 时刻某条线段消失。

    每一时刻,每条线段都会移动,线段的左端点最小为 0 0 ,当一条向左移动的线段左端点碰到 0 0 时,下一时刻它会改为向右移动;当一条向右移动的线段左端点碰到 len \mathrm{len} 时,下一时刻它会改为向左移动。

    于  BZOJ, NOI, 二维树状数组, 坐标变换, 树状数组 继续阅读

  8. 基于 Docker 容器的沙盒化评测系统

    在线评测系统(Online Judge)允许用户提交代码,在评测机上运行,并返回运行结果。而用户提交的代码有时是不安全的,它可能会无限创建进程或文件消耗评测机资源,或者建立到远程服务器的连接,给攻击者提供后门。保证评测机安全的方法之一,是使用沙盒(Sandbox)。

    于  Docker, 评测系统 继续阅读

  9. 「ZJOI2007」棋盘制作 - 悬线法

    在一个 N×M N \times M 01 01 矩阵中,求面积最大的相邻位置数字不同的矩形和正方形。

    于  BZOJ, ZJOI, 悬线法 继续阅读

  10. 「HAOI2008」排名系统 - map + Splay

    排名系统通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回 10 10 条记录。对于得分相同的,上传时间早的排名高。

    于  BZOJ, HAOI, Splay, map, 数据结构 继续阅读