Menci

眉眼如初,岁月如故

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


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

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

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

  2. 「ZJOI2008」生日聚会 - DP

    对于任意连续的一段,男孩与女孩的数目之差不超过 k k 。假设参加 party 的人中共有 n n 个男孩与 m m 个女孩,求方案总数。

    于  BZOJ, DP, ZJOI 继续阅读

  3. 「ZJOI2008」泡泡堂 - 贪心

    两队分别 n n 个选手对战,已知每个选手的实力,实力强的选手一定获胜。每一场胜、平、败的得分分别为 2,1,0 2, 1, 0 。求一个队能获得的最高得分和最低得分。

    于  BZOJ, ZJOI, 贪心 继续阅读

  4. 「ZJOI2004」沼泽鳄鱼 - 矩阵乘法

    给一个图,有一些鳄鱼在两个、三个或四个点之间周期性移动,求从 s s 点到 t t 点,恰好走 k k 步,任意时刻都不与鳄鱼同时到达同一个点的方案数。

    于  BZOJ, COGS, DP, ZJOI, 矩阵乘法 继续阅读

  5. 「ZJOI2007」最大半连通子图 - 强连通分量

    一个有向图 G=(V,E) G = (V, E) 称为半连通的(Semi-Connected),如果满足:

    u,vV \forall u, v \in V ,满足 uv u \rightarrow v vu v \rightarrow u ,即对于图中任意两点 u u v v ,存在一条 u u v v 的有向路径或者从 v v u u 的有向路径。

    G=(V,E) G' = (V', E') 满足 VV V' \subseteq V E E' E E 中所有跟 V V' 有关的边,则称 G G' G G 的一个导出子图。
    G G' G G 的导出子图,且 G G' 半连通,则称 G G' G G 的半连通子图。
    G G' G G 所有半连通子图中包含节点数最多的,则称 G G' G G 的最大半连通子图。

    给定一个有向图 G G ,请求出 G G 的最大半连通子图拥有的节点数 K K ,以及不同的最大半连通子图的数目 C C 。由于 C C 可能比较大,仅要求输出 C C X X 的余数。

    于  BZOJ, DP, Tarjan, ZJOI, 强连通分量, 缩点 继续阅读

  6. 「ZJOI2009」狼和羊的故事 - 最小割

    Orez 的羊狼圈可以看作一个 n×m n \times m 个矩阵格子,这个矩阵的边缘已经装上了篱笆。他决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez 发现狼和羊都有属于自己领地,Orez 想要添加篱笆的尽可能的短。篱笆不能改变狼羊的所属领地,篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。

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

  7. 「ZJOI2010」网络扩容 - 网络流 + 费用流

    给定一张有向图,每条边都有一个容量 C C 和一个扩容费用 W W 。这里扩容费用是指将容量扩大 1 1 所需的费用,求

    1. 在不扩容的情况下,1 1 N N 的最大流;
    2. 1 1 N N 的最大流增加 K K 所需的最小扩容费用。

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

  8. 「ZJOI2014」力 - FFT

    已知

    Ei=Fiqi E_i = \frac{F_i}{q_i} Fj=i<jqiqj(ij)2i>jqiqj(ij)2 F_j = \sum\limits_{i < j} \frac{q_i q_j}{(i - j) ^ 2} - \sum\limits_{i > j} \frac{q_i q_j}{(i - j) ^ 2}

    求数列 E E

    于  BZOJ, FFT, ZJOI, 数学 继续阅读

  9. 「ZJOI2006」物流运输 - 最短路 + DP

    物流公司要把一批货物从码头 A A 运到码头 B B 。由于货物量比较大,需要 n n 天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个 n n 天的运输计划,使得总成本尽可能地小。

    于  BZOJ, COGS, DP, ZJOI, 最短路 继续阅读

  10. 「ZJOI2008」杀蚂蚁 - 模拟 + 几何

    题面见杀蚂蚁的可读版本

    于  BZOJ, COGS, ZJOI, 几何, 数学, 模拟 继续阅读