2024“钉耙编程”中国大学生算法设计超级联赛(7)

Problems AC
1001. 纠缠点对
1002. 生产机器
1003. 自动人偶 KMP 自动机,弃疗
1004. 战争游戏
1005. Hold’em Shark 大模拟,弃疗
1006. 怯战蜥蜴 II 多项式,弃疗
1007. 创作乐曲
1008. 循环图
1009. 关于 agKc 实在不喜欢自动化于是啥都自己合成这件事
1010. 故障机器人想活下去
1011. 蛋糕上的草莓是蛋糕的灵魂
1012. 华丽牧场

1002. 生产机器

某型号的作业机器人可以生产蓝色和黄色两种充能球。根据接下来 $n$ 小时的工作计划, 该机器人在第 $i$ 小时可以生产至多 $l_i$ 个黄色充能球和 $f_i$ 个蓝色充能球, 也可以不生产任何一个充能球。

在接下来 $n$ 个小时的工作结束之后, 该机器人生产的充能球将按其被生产的顺序依次装入集装箱。具体而言, 每小时内生产的充能球的顺序可以由机器人任意确定, 而前一小时生产的所有充能球都排在后一小时生产的充能球之前。

现在, 请你计算, 最终集装箱中装入的充能球所构成的序列共有多少种可能。两个序列不同当且仅当其包含的充能球总数不同, 或者存在一个 $i$, 使得两个序列中生产的第 $i$ 个充能球颜色不同。由于答案可能很大, 你只需要输出答案对 $10^9+7$ 取模的结果。

思维 + 组合数学

如何避免重复?在组合数学中一个常见的思想:钦定!

假如我们现在想要一个序列。我们这样操作:从前往后,每个时段需要尽可能多出球,直到需要的颜色这个时段没有为止,再换下一个时段 or 在这个时段结束。

这样的话能保证序列是不重的。

于是我们基于此设计 dp(i, j) 表示到第 i 个时段,这一个时段生产的第一个小球颜色为 j,对应的合法方案数。

我们需要枚举下一个时段的 dp(i + 1, k) 进行更新。根据前面的设计,k 这个颜色需要在 i 时段全部用完;另一种颜色则随意。

假如第 i 个时段,填上第一个球以后,两种球分别还剩 x 和 y 个。假如这个时段这 x 个球是要全部被用完的话,方案数我们有:

$$
\sum_{i=0}^y\binom{i+x}{x}=\binom{x+y+1}{x+1}
$$

这个式子是怎么从左边到右边的?x + y + 1 个物品,选其中的 x + 1 个,相当于,钦定在 x + i + 1 个位置选到了 x + 1 个,然后在前 x + i 个里面选 x 个

假如在当前时段结束选球,那么就是:

$$
\sum_{i=0}^x \sum_{j=0}^y\binom{i+j}{i}
=\sum_{i=0}^x \binom{i+y+1}{i+1}
=\sum_{i=1}^{x+1} \binom{i+y}{i}
=\binom{x+y+2}{x+1} - 1
$$

复杂度 $O(n + w)$

1007. 创作乐曲

通过发现性质,减少决策点!

1008. 循环图

坎格鲁斯普雷被困在了一张循环图里,这张循环图有无数个节点,初始时坎格鲁斯普雷在 1 号节点。

循环图是边存在着一定循环关系的图,循环图里面的边可以用循环周期 $n$ 和 $m$ 对三元组 $\left(u_i, v_i, w_i\right)\left(1 \leq u_i \leq n, u_i+1 \leq v_i \leq 2 \times n, 1 \leq w_i \leq 10^9\right)$ 表示。每对三元组 $\left(u_i, v_i, w_i\right)$ 表示,对于循环图内所有的满足 $s=u_i+k \times n, t=v_i+k \times n(k \in N)$ 的点对 $(s, t)$ ,都存在有 $w_i$ 条从点 $s$ 通往点 $t$ 的边。

现在,坎格鲁斯普雷知道了这张循环图的第 $L$ 个节点到第 $R$ 个节点各存在着一个出口,坎格鲁斯普雷需要到达这些节点中的任意一个才能逃出循环图(到达有出口存在的节点后不一定要立刻逃出)。坎格鲁斯普雷想请你帮他算算,他有多少种逃出这张循环图的方式。由于答案可能很大,你需要输出答案对 $10^9+7$ 取模后的结果。

设 calc(i) 为走到 [1, i] 节点的方案数只和,ans = calc(R) - calc(L - 1)

设 f(i) 为走到 i 节点的方案数之和,这个东西是很好 dp 的。那我们直接先求出 f(1), f(2) … f(n)

然后搞出我们的转移矩阵。这里有一个技巧是,我们直接搞出一个大转移矩阵,这个转移矩阵相当于步长是 n,这样我们 pow 的指数就变成了 x / n,最后边角 O(x % n) 扫一下即可。

1011. 蛋糕上的草莓是蛋糕的灵魂

2024“钉耙编程”中国大学生算法设计超级联赛(7)

https://tosakaucw.github.io/2024“钉耙编程”中国大学生算法设计超级联赛(7)/

Author

TosakaUCW

Posted on

2024-08-09

Updated on

2024-08-12

Licensed under

Comments