Menci

眉眼如初,岁月如故

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


  1. 「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, 搜索, 数学 继续阅读

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

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

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

  3. 「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, 搜索, 状态压缩 继续阅读

  4. 「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, 搜索, 最短路 继续阅读

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

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

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

  6. 「NOIP2015」斗地主 - 搜索

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

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

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

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

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

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

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

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