3726.最短路
题解
一个比较显然的想法是:当前物品一定满足所有规则,那么只需要记录 mask∈[0,2m) 即可,直接建图,时间复杂度 O(n32m)。
怎么优化呢,正难则反,考虑反着的操作怎么维护:
- 左、右移动:没变化,找到两边第一个满足 mask 的即可。
- 删除操作:反向的添加操作,也就是 (i,mask)→(i,mask∪2k)。
- 添加操作:反向的删除操作,向右变成向左,如果要删除状态 j,则会转移到左侧所有 (v,mask\2j) 的位置,对照上面的做法,也就是反复跳当前点的前驱 mask\2j。
这样子并不好优化,但是可以使用并查集加速,只需要对 (i,mask) 维护并查集即可,每个状态只用一次。
最终时间复杂度 O(n22mmlogn)。
