Menci

眉眼如初,岁月如故

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


  1. 「SDOI2016」储能表 - 二进制

    有一个 n n m m 列的表格,行从 0 0 n1 n - 1 编号,列从 0 0 m1 m - 1 编号。
    每个格子都储存着能量。最初,第 i i 行第 j j 列的格子储存着 点能量。所以,整个表格储存的总能量是,

    随着时间的推移,格子中的能量会渐渐减少。一个时间单位,每个格子中的能量都会减少 1 1 。显然,一个格子的能量减少到 0 0 之后就不会再减少了。
    也就是说,k k 个时间单位后,整个表格储存的总能量是,

    给出一个表格,求 k k 个时间单位后它储存的总能量。
    由于总能量可能较大,输出时对 p p 取模。

    于  BZOJ, COGS, SDOI, 二进制, 位运算, 异或 继续阅读

  2. 「NOI2014」起床困难综合征 - 位运算 + 贪心

    drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n n 扇防御门组成。每扇防御门包括一个运算 和一个参数 t t ,其中运算一定是 中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为 x x ,则其通过这扇防御门后攻击力将变为 。最终 drd 受到的伤害为对方初始攻击力 x x 依次经过所有 n n 扇防御门后转变得到的攻击力。 由于 atm 水平有限,他的初始攻击力只能为 0 0 m m 之间的一个整数(即他的初始攻击力只能在 0 0 1 1 m m 中任选,但在通过防御门之后的攻击力不受 m m 的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害。

    于  BZOJ, NOI, 位运算, 贪心 继续阅读

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

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

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