自动搬运

查看原文

来自洛谷，原作者为

	zpy12345 普普通通

搬运于2025-08-24 22:05:39，当前版本为作者最后更新于2025-08-08 13:46:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[COCI 2017/2018 #6] Alkemija

蒟蒻的第一篇题解，不喜勿喷。

思路

这里介绍一个比较简单的模拟做法。可以按照题目要求模拟，先求出用初始物质可以发生的反应，把反应得到的新物质加入集合。执行上述操作，直到无法得到新物质，时间复杂度 $O(N\sum (L_{i}+R_{i}))$。考虑优化，我们发现这个算法慢在每一轮遍历了许多不必要的反应。容易发现，下一轮发生的每一个反应一定满足：其需要的物质至少有一个是这一轮的新产生物质（如果不是，那么该反应应该在更靠前的轮数就执行）。开个数组记录需要当前物质的反应编号即可。时间复杂度 $O(N+K+\sum (L_{i}+R_{i}))$。 ::::::warning[警告]{open} 该优化为必要条件，并非充分条件，需要别的 $O(1)$ 判断来辅助。可以记录每个反应的需要物质中没有得到的数量，新得到这个反应的某个需要物质就 $-1$。 :::::: ::::info[时间复杂度证明] 显然每个物质只会新出现一次，每个物质包含的反应数量总和 $=$ 每个反应包含的物质数量总和 $=$ $\sum L_{i}$。 ::::