P4957 [COCI 2017/2018 #6] Alkemija题解

· · 题解

[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}。 ::::