双向 BFS

[Ir1d]

https://oi-wiki.org/search/dbfs/

[Handgrip]

灯 Lights也可以用利用双向搜索的思路，第二次搜索的起始t设置为(1LL << n) -1（即n个灯全开状态），两次搜索会和时判断是否有一样的状态即可，不用取异或。可能更加好理解一点。
洛谷翻译的题面有误，需要去看一下原文。
另外：%%%位运算用的行云流水

[chenghb911]

这代码有点难以理解啊

[lplalbert]

@Flaryer
灯 Lights也可以用利用双向搜索的思路，第二次搜索的起始t设置为(1LL << n) -1（即n个灯全开状态），两次搜索会和时判断是否有一样的状态即可，不用取异或。可能更加好理解一点。
洛谷翻译的题面有误，需要去看一下原文。
另外：%%%位运算用的行云流水

确实，操作一个灯会使它自己改变状态，题目没翻译出来

[redp4th]

先%%%

不过我想提一嘴,这代码能work的前提是题设保证一定有解...如果出现无解的情况就不太中了

[akynazh]

代码很简洁，很精妙。

[KalarFunc]

与其说是双向搜索，不如说采用了分治策略

[xiao-ming-hub]

@KalarFunc
与其说是双向搜索，不如说采用了分治策略

差别还是有的，分治会一开始就把状态分成两块然后分别搜索，但双向搜索是直接从两端开始搜索。

[2020gyk080]

确切的来说时间复杂度是 $O(a^{b/2}+合并复杂度)$