Menci

眉眼如初,岁月如故

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


  1. 「APIO2013」TOLL - 搜索 + 最小生成树

    幸福国度可以用 NN 个城镇(用 11NN 编号)构成的集合来描述,这些城镇最开始由 MM 条双向道路(用 11MM 编号)连接。城镇 11 是中央城镇。保证一个人从城镇 11 出发,经过这些道路,可以到达其他的任何一个城市。这些道路都是收费道路,道路 ii 的使用者必须向道路的主人支付 cic_i 分钱的费用。已知所有的这些 cic_i 是互不相等的。最近有 KK 条新道路建成,这些道路都属于亿万富豪 Mr. Greedy。

    Mr. Greedy 可以决定每条新道路的费用(费用可以相同),并且他必须在明天宣布这些费用。

    两周以后,幸福国度将举办一个盛况空前的嘉年华!大量的参与者将沿着这些道路游行并前往中央城镇。共计 pjp_j 个参与者将从城镇 jj 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行,并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗,这些道路将由幸福国度中最有钱的人选出,也就是 Mr. Greedy。同样根据这个习俗,Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小,并且仍要保证任何人可以从城镇 jj 前往城镇 11 (因此,这些选出的道路来自将费用作为相应边边权的 “最小生成树”)。如果有多个这样的道路集合,Mr. Greedy 可以选其中的任何一个,只要满足费用和是最小的。

    Mr. Greedy 很明确地知道,他从 KK 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲,如果 pp 个人经过道路 ii,道路 ii 产生的收入为乘积 cipc_i \cdot p。注意 Mr. Greedy 只能从新道路收取费用,因为原来的道路都不属于他。

    Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用(将在明天公布),并且选择嘉年华用的道路(将在嘉年华的前一天公布),使得他在 KK 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

    你是一个记者,你想揭露他的计划。为了做成这件事,你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

    于  APIO, BZOJ, UOJ, 搜索, 最小生成树 继续阅读

  2. 「HAOI2007」反素数 - 搜索

    对于任何正整数 x x ,其约数的个数记作 g(x) g(x) ,例如 g(1)=1 g(1) = 1 g(6)=4 g(6) = 4 。如果某个正整数 x x 对于任何 i(0,x) i \in (0, x) 都满足 g(x)>g(i) g(x) > g(i) ,则称 x x 为反质数。

    给定一个数 N N ,求最大的不超过 N N 的反质数。

    于  BZOJ, HAOI, 搜索, 数学 继续阅读

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

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

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

  4. 「NOIP2016」愤怒的小鸟 - 状态压缩 + BFS

    Kiana 最近沉迷于一款神奇的游戏无法自拔。

    简单来说,这款游戏是在一个平面上进行的。

    有一架弹弓位于 (0,0) (0, 0) 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 y=ax2+bx y = ax ^ 2 + bx 的曲线,其中 a a b b 是 Kiana 指定的参数,且必须满足 a<0 a < 0

    当小鸟落回地面(即 x x 轴)时,它就会瞬间消失。

    在游戏的某个关卡里,平面的第一象限中有 n n 只绿色的小猪,其中第 i i 只小猪所在的坐标为 (xi,yi) (x_i, y_i)

    如果某只小鸟的飞行轨迹经过了(xi,yi) (x_i, y_i) ,那么第 i i 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

    如果一只小鸟的飞行轨迹没有经过(xi,yi) (x_i, y_i) ,那么这只小鸟飞行的全过程就不会对第 i i 只小猪产生任何影响。

    例如,若两只小猪分别位于 (1,3) (1, 3) (3,3) (3, 3) ,Kiana 可以选择发射一只飞行轨迹为 y=x2+4x y = -x ^ 2 + 4x 的小鸟,这样两只小猪就会被这只小鸟一起消灭。

    而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

    这款神奇游戏的每个关卡对 Kiana 来说都很难,所以 Kiana 还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在「输入格式」中详述。

    假设这款游戏一共有 T T 个关卡,现在 Kiana 想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

    于  BFS, NOIP, 搜索, 状态压缩 继续阅读

  5. 「NOIP2013」华容道 - BFS + SPFA

    1. 在一个 n×m n \times m 棋盘上有 n×m n\times m 个格子,其中有且只有一个格子是空白的,其余 n×m1 n \times m - 1 个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 1 \times 1 的;
    2. 有些棋子是固定的,有些棋子则是可以移动的;
    3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

    给定一个棋盘,游戏可以玩 q q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i i 次玩的时候,空白的格子在第 EXi EX_i 行第 EYi EY_i 列,指定的可移动棋子的初始位置为第 SXi SX_i 行第 SYi SY_i 列,目标位置为第 TXi TX_i 行第 TYi TY_i 列。

    假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

    于  BFS, CodeVS, NOIP, SPFA, 搜索, 最短路 继续阅读

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

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

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

  7. 「NOIP2015」斗地主 - 搜索

    给一组扑克牌,按照斗地主的规则出牌,求最少多少次出完。

    于  BZOJ, CodeVS, NOIP, 搜索 继续阅读

  8. 「JSOI2008」最小生成树计数 - 搜索

    求一个图的不同的最小生成树的数量,保证相同权值的边数量 10 \leq 10

    于  BZOJ, JSOI, 搜索, 最小生成树 继续阅读

  9. 「COGS 439」软件补丁 - 记忆化搜索 + 位运算

    现在有一个软件,共有 n 个 BUG,开发人员开发了 m 个补丁,每个补丁有一个应用条件,要求某些 BUG 比如存在,某些 BUG 可以不存在,某些 BUG 存在或不存在都可以;每个补丁有一个影响,会使某些 BUG 消失,会使某些 BUG 产生;每个 BUG 有一个应用时间。问修复所有 BUG 需要的最短时间为多少。

    于  COGS, map, 位运算, 搜索, 网络流 24 题, 记忆化搜索 继续阅读