Menci

眉眼如初,岁月如故

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


  1. 「CQOI2009」跳舞 - 网络流

    一次舞会有 n n 个男孩和 n n 个女孩。每首曲子开始时,所有男孩和女孩恰好配成 n n 对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会「单向喜欢」)。每个男孩最多只愿意和 k k 个不喜欢的女孩跳舞,而每个女孩也最多只愿意和 k k 个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?

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

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

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

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

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

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

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

  4. 「SDOI2016」数字配对 - 费用流

    n n 种数字,第 i i 种数字是 ai a_i 、有 bi b_i 个,权值是 ci c_i

    若两个数字 ai a_i aj a_j 满足,ai a_i aj a_j 的倍数,且 aiaj \frac{a_i}{a_j} 是一个质数,那么这两个数字可以配对,并获得 ci×cj c_i \times c_j 的价值。

    一个数字只能参与一次配对,可以不参与配对。
    在获得的价值总和不小于 0 0 的前提下,求最多进行多少次配对。

    于  BZOJ, COGS, Edmonds-Karp, SDOI, 二分答案, 数论, 素数判定, 线性筛, 网络流, 费用流 继续阅读

  5. 「SCOI2015」小凸玩矩阵 - 二分图匹配

    小方给小凸一个 NM N * M NM N \leq M )的矩阵 A A ,要求小秃从其中选出 N N 个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的 N N 个数中第 K K 大的数字的最小值是多少。

    于  BZOJ, Dinic, SCOI, 二分图匹配, 二分答案, 安徽集训, 网络流 继续阅读

  6. 「POJ 2728」Desert King - 01 分数规划

    一个王国有 N N 个城市,每个城市有坐标 (x,y) (x, y) 和海拔 z z ,在 N N 个城市之间修水渠,要保证每个城市有水,水渠是水平的,每个城市的海拔不同,现在要求修单位长度的水渠的海拔高度差最小。

    于  POJ, Prim, 二分答案, 分数规划, 实数二分, 生成树 继续阅读

  7. 「SDOI2015」星际战争 - 网络流

    Y 军团一共派遣了 N N 个巨型机器人进攻 X 军团的阵地,其中第 i i 个巨型机器人的装甲值为 Ai A_i 。当一个巨型机器人的装甲值减少到 0 或者以下时,这个巨型机器人就被摧毁了。X 军团有 M M 个激光武器,其中第 i i 个激光武器每秒可以削减一个巨型机器人 Bi B_i 的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人。Y 军团需要知道 X 军团最少需要用多长时间才能将 Y 军团的所有巨型机器人摧毁。

    于  BZOJ, Dinic, SDOI, 二分答案, 图论, 实数二分, 网络流 继续阅读

  8. 「NOIP2010」关押罪犯 - 二分图染色

    S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为 1 ~ N,我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。每年每一对有仇恨的罪犯会发生一次冲突。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力。那么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小,求这个最小值是多少?

    于  CodeVS, NOIP, Vijos, 二分图染色, 二分答案, 图论, 洛谷 继续阅读

  9. 「CodeVS 3168 / 3162」抄书问题 - 划分 DP / 二分答案

    M 本有顺序的书分给 K 个人抄写,每一个人的抄写速度都一样,一本书不允许给两个(或以上)的人抄写,分给每一个人的书,必须是连续的(比如不能把第一、第三、第四本数给同一个人抄写)。现在请你设计一种方案,使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

    于  CodeVS, DP, 二分答案, 划分 DP, 贪心 继续阅读