Menci

眉眼如初,岁月如故

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


  1. 「HAOI2008」硬币购物 - 背包 DP + 容斥原理

    一共有 4 4 种硬币。面值分别为 c1,c2,c3,c4 c_1, c_2, c_3, c_4 。某人去商店买东西,去了 n n 次。每次带 di d_i ci c_i 硬币,买 si s_i 的价格的东西。请问每次有多少种付款方法?

    于  BZOJ, DP, HAOI, 容斥原理, 数学, 背包 DP 继续阅读

  2. 「HAOI2008」圆上的整点 - 数学

    求一个给定的圆 x2+y2=r2 x ^ 2 + y ^ 2 = r ^ 2 ,在圆周上有多少个点的坐标是整数。

    于  BZOJ, HAOI, 数学 继续阅读

  3. 「HAOI2008」玩具取名 - 区间 DP

    某人有一套玩具,并想法给玩具命名。首先他选择 WING 四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好,将名字中任意一个字母用 WING 中任意两个字母代替,使得自己的名字能够扩充得很长。

    现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。

    于  BZOJ, DP, HAOI, 区间 DP 继续阅读

  4. 「HAOI2016」食物链 - 拓扑排序 + DP

    n n 个物种和 m m 条能量流动关系,求其中的食物链条数。

    于  BZOJ, COGS, DP, HAOI, 拓扑排序 继续阅读

  5. 「HAOI2011」Problem b - 莫比乌斯反演

    对于给出的 n n 个询问,每次求有多少个数对 (x,y) (x, y) ,满足 axb a \leq x \leq b cyd c \leq y \leq d ,且 gcd(x,y)=k \gcd(x, y) = k gcd(x,y) \gcd(x, y) 函数为 x x y y 的最大公约数。

    于  BZOJ, COGS, HAOI, 数学, 数论, 线性筛, 莫比乌斯反演 继续阅读

  6. 「HAOI2015」树上操作 - 树链剖分 + DFS序

    有一棵点数为 N N 的树,以点 1 1 为根,且树点有边权。然后有 M M 个操作,分为三种:

    1. 把某个节点 x x 的点权增加 a a
    2. 把某个节点 x x 为根的子树中所有点的点权都增加 a a
    3. 询问某个节点 x x 到根的路径中所有点的点权和。

    于  BZOJ, DFS 序, HAOI, 树链剖分, 线段树 继续阅读

  7. 「HAOI2006」受欢迎的牛 - 强连通分量

    每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N N 头牛,给你 M M 对整数 (A,B) (A,B) ,表示牛 A A 认为牛 B B 受欢迎。 这种关系是具有传递性的,如果 A A 认为 B B 受欢迎,B B 认为 C C 受欢迎,那么牛 A A 也认为牛 C C 受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

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