Menci

眉眼如初,岁月如故

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


  1. 「NOIP2014」飞扬的小鸟 - 背包 DP

    • 游戏界面是一个长为 n n ,高为 m m 的二维平面,其中有 k k 个管道(忽略管道的宽度)。
    • 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
    • 小鸟每个单位时间沿横坐标方向右移的距离为 1 1 ,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度 X X ,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 Y Y 。小鸟位于横坐标方向不同位置时,上升的高度 X X 和下降的高度 Y Y 可能互不相同。
    • 小鸟高度等于 0 0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m m 时,无法再上升。

    现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

    于  COGS, CodeVS, DP, NOIP, 背包 DP 继续阅读

  2. 「NOIP2012」借教室 - 二分 / 线段树

    我们需要处理接下来 n n 天的借教室信息,其中第 i i 天学校有 ri r_i 个教室可供租借。共有 m m 份订单,每份订单用三个正整数描述,分别为 dj,sj,tj d_j, s_j, t_j ,表示某租借者需要从第 sj s_j 天到第 tj t_j 天租借教室(包括第 sj s_j 天和第 tj t_j 天),每天需要租借 dj d_j 个教室。

    现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

    于  COGS, CodeVS, NOIP, 二分, 差分, 线段树 继续阅读

  3. 「NOI2012」随机数生成器 - 矩阵乘法

    已知

    给定 m,a,c,x0,n,g m, a, c, x_0, n, g ,求

    于  BZOJ, COGS, NOI, 矩阵乘法 继续阅读

  4. 「BZOJ 1706」乳牛接力跑 - 矩阵乘法

    给一个图,求从 s s 点到 t t 点恰好经过 k k 步的最短路。

    于  BZOJ, COGS, USACO, 矩阵乘法 继续阅读

  5. 「ZJOI2004」沼泽鳄鱼 - 矩阵乘法

    给一个图,有一些鳄鱼在两个、三个或四个点之间周期性移动,求从 s s 点到 t t 点,恰好走 k k 步,任意时刻都不与鳄鱼同时到达同一个点的方案数。

    于  BZOJ, COGS, DP, ZJOI, 矩阵乘法 继续阅读

  6. 「UVa 11021」Tribles - 概率与期望

    k k 个 Tribles,每个 Trible 只能存活一天,但在死亡之前,每个 Trible 有 pi p_i 的概率繁衍出 i i 个 Tribles。求 m m 天之后所有 Tribles 全部死亡的概率。

    于  COGS, DP, UVa, 数学, 概率与期望 继续阅读

  7. 「ZJOI2006」物流运输 - 最短路 + DP

    物流公司要把一批货物从码头 A A 运到码头 B B 。由于货物量比较大,需要 n n 天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个 n n 天的运输计划,使得总成本尽可能地小。

    于  BZOJ, COGS, DP, ZJOI, 最短路 继续阅读

  8. 「ZJOI2008」杀蚂蚁 - 模拟 + 几何

    题面见杀蚂蚁的可读版本

    于  BZOJ, COGS, ZJOI, 几何, 数学, 模拟 继续阅读

  9. 「CEOI2004」锯木厂选址 - 斜率优化 DP

    从山顶上到山底下沿着一条直线种植了 n n 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材,树被砍倒后要运送到锯木厂。 木材只能按照一个方向运输:朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂,使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。

    于  CEOI, COGS, DP, 单调队列, 斜率优化 继续阅读

  10. 「ZJOI2007」仓库建设 - 斜率优化 DP

    i i 个工厂目前已有成品 Pi P_i 件,在第 i i 个位置建立仓库的费用是 Ci C_i 。对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于公司产品的对外销售处设置在山脚的工厂 N N ,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送 1 1 个单位距离的费用是 1 1 。假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:

    1. 工厂 i i 距离工厂 1 1 的距离 xi x_i (其中 x1=0 x_1 = 0 );
    2. 工厂 i i 目前已有成品数量 pi p_i
    3. 在工厂 i i 建立仓库的费用 ci c_i

    请你帮助公司寻找一个仓库建设的方案,使得总的费用(建造费用 + 运输费用)最小。

    于  BZOJ, COGS, DP, ZJOI, 单调队列, 斜率优化 继续阅读