Light switches
*2600
tag：暴力枚举，meet in middle
题目描述
有 \(n(1\le 1000)\) 盏灯和 \(s(1\le s\le 30)\) 个开关，每个开关能控制一些灯，并改变这些灯的状态。
接下来有 \(d(1\le d\le 1000)\) 次询问，每次询问给出 \(k_i\) 盏亮着的灯，询问将所有灯全部熄灭最少需要按几次开关。
思路
每个开关至多会被按一次。
注意到 \(s\) 很小。
可以考虑一个 \(O(2^s)\) 的暴力。
但复杂度显然不对。
所以 meet in middle，将开关划分为 \(k\) 和 \(s-k\) 两部分。
每次询问枚举 \(k\) 中的所有状态，并在 \(s-k\) 的部分找其与初始状态异或后的状态。
具体实现时可以用 unordered_map 存下 \(s-k\) 这部分的所有状态，灯的状态可以用 bitset 来存。
时间复杂度 \(O(2^k+2^{s-k}+\frac{dn2^k}{w})\)，还要带 unordered_map 的常数。
在 \(k\) 取 \(12\) 左右可以通过。
标签：选写,状态,le,middle,询问,开关,杂题,unordered From： https://www.cnblogs.com/ddxrS/p/18544578