Menci

眉眼如初,岁月如故

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


  1. 「SHOI2008」仙人掌图 - 仙人掌 DP

    求仙人掌图的直径。

    于  BZOJ, DP, SHOI, Tarjan, 仙人掌 继续阅读

  2. 「IOI2008」岛屿 - 基环树 DP

    给一个由多个基环树构成的图,求所有基环树最长链之和。

    于  BZOJ, DP, SHOI, Tarjan, 基环树 继续阅读

  3. 「SHOI2008」小约翰的游戏 - 博弈论

    桌子上有 n n 堆石子,轮流取石子,每个人取的时候,可以随意选择一堆石子,在这堆石子中取走任意多的石子,但不能一粒石子也不取,我们规定取到最后一粒石子的人算。求先手是否必胜。

    于  BZOJ, SHOI, 博弈论, 数学 继续阅读

  4. 「SHOI2008」循环的债务 - DP

    A、B、C 三个人之间互相有一些债务,每个人有每种面值 1,5,10,20,50,100 1, 5, 10, 20, 50, 100 的钞票若干,求使他们把债务还清的最少交换的现金数量。

    于  BZOJ, DP, SHOI 继续阅读

  5. 「SHOI2008」汉诺塔 - DP

    在任何操作执行之前,我们以任意的次序为六种操作(AB、AC、BA、BC、CA 和 CB)赋予不同的优先级,然后,我们总是选择符合以下两个条件的操作来移动盘子,直到所有的盘子都从柱子 A 移动到另一根柱子:

    1. 这种操作是所有合法操作中优先级最高的;
    2. 这种操作所要移动的盘子不是上一次操作所移动的那个盘子。

    可以证明,上述策略一定能完成汉诺塔游戏。
    现在你的任务就是假设给定了每种操作的优先级,计算按照上述策略操作汉诺塔移动所需要的步骤数。

    于  BZOJ, DP, SHOI 继续阅读

  6. 「SHOI2008」堵塞的交通 - 线段树

    整个国家的交通系统可以被看成是一个 2 2 C C 列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路,所以总共有 2C 2C 个城市和 3C2 3C - 2 条道路。

    交通信息可以分为以下几种格式:

    1. Close r1 c1 r2 c2,相邻的两座城市 (r1,c1) (r_1, c_1) (r2,c2) (r_2, c_2) 之间的道路被堵塞了;
    2. Open r1 c1 r2 c2,相邻的两座城市 (r1,c1) (r_1, c_1) (r2,c2) (r_2, c_2) 之间的道路被疏通了;
    3. Ask r1 c1 r2 c2,询问城市 (r1,c1) (r_1, c_1) (r2,c2) (r_2, c_2) 是否连通。

    于  BZOJ, SHOI, 线段树 继续阅读

  7. 「SHOI2007」园丁的烦恼 - CDQ

    每一棵树可以用一个整数坐标来表示,每次询问你某一个矩阵内有多少树。

    于  BZOJ, CDQ, SHOI, 分治, 数据结构, 树状数组 继续阅读

  8. 「SHOI2007」善意的投票 - 最小割

    幼儿园里有 n n 个小朋友打算通过投票来决定睡不睡午觉。他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。每位小朋友应该怎样投票,才能使冲突数最小?

    于  BZOJ, Dinic, SHOI, 最小割, 网络流 继续阅读