Menci

眉眼如初,岁月如故

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


  1. 「NOIP2016」组合数问题 - 递推 + 前缀和

    组合数表示的是从 n n 个物品中选出 m m 个物品的方案数。举个例子,从 (1,2,3) (1, 2, 3) 三个物品中选择两个物品可以有 (1,2) (1, 2) (1,3) (1, 3) (2,3) (2, 3) 这三种选择方法。

    根据组合数的定义,我们可以给出计算组合数的一般公式:

    Cnm=n!m!(nm)! C_n ^ m = \frac{n!}{m!(n - m)!}

    其中 n!=1×2××n n! = 1 \times 2 \times \cdots \times n

    小葱想知道如果给定 n n m m k k ,对于所有的 0in 0 \leq i \leq n 0jmin(i,m) 0 \leq j \leq \min(i, m) 有多少对 (i,j) (i, j) 满足是 k k 的倍数。

    于  NOIP, 前缀和, 数学, 组合数 继续阅读

  2. 「NOIP2016」天天爱跑步 - 树链剖分 + 前缀和

    小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

    这个游戏的地图可以看作一棵包含 n n 个结点和 n1 n - 1 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 1 1 n n 的连续正整数。

    现在有 m m 个玩家,第 i i 个玩家的起点为 Si S_i ,终点为 Ti T_i 。每天打卡任务开始时,所有玩家在第 0 0 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

    小 C 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 j j 的观察员会选择在第 Wj W_j 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj W_j 秒也理到达了结点 j j 。小 C 想知道每个观察员会观察到多少人?

    注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点 j j 作为终点的玩家:若他在第 Wj W_j 秒前到达终点,则在结点 j j 的观察员不能观察到该玩家;若他正好在第 Wj W_j 秒到达终点,则在结点 j j 的观察员可以观察到这个玩家。

    于  NOIP, 前缀和, 树链剖分 继续阅读