Menci

眉眼如初,岁月如故

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


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

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

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

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

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

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

  3. 「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, 搜索, 数学 继续阅读

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

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

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

  5. 「HAOI2006」数字序列 - DP

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

    于  BZOJ, DP, HAOI 继续阅读

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

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

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

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

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

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

  8. 「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, 贪心 继续阅读

  9. 「HAOI2008」糖果传递 - 数学

    n n 个小朋友坐成一圈,每人有 ai a_i 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 1 1 。求使所有人获得均等糖果的最小代价。

    于  BZOJ, HAOI, 数学 继续阅读

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

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

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