Menci

眉眼如初,岁月如故

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


  1. 「POI2000」病毒 - AC 自动机 + 拓扑排序

    二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。

    于  AC 自动机, BZOJ, POI, 字符串, 拓扑排序 继续阅读

  2. 「POI2008」BLO - 割点

    Byteotia 城市有 n n 个 towns,m m 条双向 roads。每条 road 连接两个不同的 towns,没有重复的 road。所有 towns 连通。

    求当把每个点封锁时,会有多少有序点对 (u,v) (u, v) 不连通。

    于  BZOJ, POI, Tarjan, 割点, 图论 继续阅读

  3. 「POI2005」Kos-Dicing - 二分答案 + 网络流

    Dicing 是一个两人玩的游戏,人们专门成立了这个游戏的一个俱乐部,俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人。有一个人想知道比赛以后赢的最多的那个家伙最少会赢多少场。

    于  BZOJ, Dinic, POI, 二分答案, 网络流 继续阅读

  4. 「POI2006」Szk-Schools - 费用流

    有一个长度为 n n 的序列 ai a_i ,每个数都在 [1, n] [1,\ n] 之间,要求把这些数变成一个 n n 的排列:

    1. ai a_i 可以被改成 [li, ri] [l_i,\ r_i] 之间的数;
    2. ai a_i 改变为 x x 的花费为 k×aix k \times | a_i - x |

    求是否可行及最小花费。

    于  BZOJ, Edmonds-Karp, POI, 网络流, 费用流 继续阅读