Menci

眉眼如初,岁月如故

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


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

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

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

  2. 「SCOI2009」生日快乐 - 搜索

    windy 的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X X Y Y 的矩形蛋糕。现在包括 windy,一共有 N N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy 主刀,每一切只能平行于一块蛋糕的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N N 块蛋糕,windy 必须切 N1 N - 1 次。为了使得每块蛋糕看起来漂亮,我们要求 N N 块蛋糕的长边与短边的比值的最大值最小。你能帮助 windy 求出这个比值么?

    于  BZOJ, DFS, SCOI, 搜索 继续阅读

  3. 用 std::stack 实现非递归 DFS

    众所周知,在有些省份(比如山东、河南),省选时使用 Windows 垃圾系统评测,而 Windows 下默认的系统栈非常小(只有 1M),这造成了有些 DFS 相关算法无法通过极端数据,而是发生『栈溢出』的错误。一种解决方法是使用非递归的 DFS。

    于  DFS, STL, Tarjan, 强连通分量, 树链剖分, 算法模板 继续阅读