CF2004D Colored Portals 题解

· · 题解

背景

memset 害死人。

分析

首先注意到字母种类只有四个，那么很显然任意两个城市至多只需要一个城市中转就能互相到达。

然后不就可以乱写了么。

先把可以直接到达的判断掉，设当前两个城市为 x 和 y，我们对 6 种字母组合分别存一下出现的位置，然后对 x 的两个字母分别去找到对应的字母组合，并在相应的数组里面二分找到第一个比 x 靠后的位置，最后计算即可。

需要注意的是，如果当前字母组合在 x 之后一次也没有出现过，我们就需要找到在 x 前面位置的再计算。

但是因为 x 可能从未出现过，这时候我们可以先对每一个数组先存上一个极小值防止卡死。

然后就做完了。

Code

提交记录