Menci

眉眼如初,岁月如故

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


  1. 「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, 二维树状数组, 坐标变换, 树状数组 继续阅读

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

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

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

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

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

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

  4. 「HAOI2008」移动玩具 - 状态压缩 + BFS

    在一个 4×4 4 \times 4 的方框内摆放了若干个相同的玩具,要将这些玩具重新摆放成为理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动到的位置不能有玩具,求最小移动次数。

    于  BFS, BZOJ, HAOI, 状态压缩 继续阅读

  5. 「HAOI2007」反素数 - 搜索

    对于任何正整数 x x ,其约数的个数记作 g(x) g(x) ,例如 g(1)=1 g(1) = 1 g(6)=4 g(6) = 4 。如果某个正整数 x x 对于任何 i(0,x) i \in (0, x) 都满足 g(x)>g(i) g(x) > g(i) ,则称 x x 为反质数。

    给定一个数 N N ,求最大的不超过 N N 的反质数。

    于  BZOJ, HAOI, 搜索, 数学 继续阅读

  6. 「HAOI2007」覆盖问题 - 二分答案 + 枚举

    用三个 L×L L \times L 的正方形覆盖一些点,使最大正方形的边长最小。

    于  BZOJ, HAOI, 二分答案, 枚举 继续阅读

  7. 「HAOI2006」数字序列 - DP

    现在我们有一个长度为 n n 的整数序列 {ai} \{ a_i \} 。我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。

    于  BZOJ, DP, HAOI 继续阅读

  8. 「HAOI2007」分割矩阵 - 搜索

    将一个 n×m n \times m 的数字矩阵进行如下分割:将原矩阵沿某一条直线分割成两个矩阵,再将生成的两个矩阵继续如此分割(当然也可以只分割其中的一个),这样分割了 k1 k - 1 次后,原矩阵被分割成了 k k 个矩阵。(每次分割都只能沿着数字间的缝隙进行)原矩阵中每一位置上有一个分值,一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成 n n 个矩阵,并使各矩阵总分的均方差最小。请编程对给出的矩阵及 n n ,求出均方差的最小值。

    于  BZOJ, DFS, DP, HAOI, 搜索 继续阅读

  9. 「HAOI2007」理想的正方形 - 单调队列

    有一个 n×m n \times m 的整数组成的矩阵,现请你从中找出一个 k×k k \times k 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

    于  BZOJ, HAOI, 单调队列 继续阅读

  10. 「HAOI2007」上升序列 - DP + 贪心

    对于一个给定的 S={a1,a2,a3,,an} S = \{ a_1, a_2, a_3, \ldots , a_n \} ,若有 P={ax1,ax2,ax3,,axm} P = \{ a_{x_1},a_{x_2}, a_{x_3}, \ldots, a_{x_m} \} ,满足 x1<x2<<xm x_1 < x_2 < \ldots < x_m ax1<ax2<<axm a_{x_1} < a_{x_2} < \ldots < a_{x_m} ,那么就称 P P S S 的一个上升序列。如果有多个 P P 满足条件,那么我们想求字典序最小的那个。

    任务给出 S S 序列,给出若干询问。对于第 i i 个询问,求出长度为 Li L_i 的上升序列,如有多个,求出下标字典序最小的那个。

    于  BZOJ, DP, HAOI, 贪心 继续阅读