刷NOIP模拟赛，想起多年以前学过的折半枚举以前学过的好多东西都忘了QAQ。。。
有这样一道题（取自黄学长博客）：
【题目描述】
$n$点$m$双向边的图，每个点有$2$个状态：开和关。每次操作改变一个点的状态，以及与其有边直接相连的点的状态。问开启所有点至少需要多少次操作。
【输入格式】
第一行两个整数$n$,$m$。
第二行$n$个整数，第$i$个数表示第$i$点的状态，$0$为关，$1$为开。
接下来$m$行，每行$2$个整数$a$,$b$，表示$a$和$b$直接相连，同一条边不会出现多次。
【输出格式】
第一行一个整数$k$表示最少的操作次数，所有数据保证至少有一组可行解。
第二行$k$个整数，表示操作的点的编号。
【样例输入】
4 3
1 1 0 0
2 3
1 3
2 4
【样例输出】
3
1 2 3
【数据范围】
对于$100%$的数据，1<=n<=40，0<=m<=500
$n$最大为$40$，显然这题的时间复杂度应该是指数级别的，但是直接枚举$2^{40}$会超时，怎么办？
首先预处理一下改变每个点会造成的影响。
由于直接枚举会超时。我们发现，可以先枚举前$\frac{n}{2}$个点是否进行操作，保存操作后的状态（用HASH表），然后再枚举后$\frac{n}{2}$个点是否进行操作，得出操作后的状态$s$，并$1^{n}-1$与$s$进行异或操作，得出$S_1$。
不难发现，如果前$\frac{n}{2}$个点进行了某种操作$s_2$使状态变成$S_1$，那么显然把操作$s_2$与操作$s$合并就可以使全部开关的状态变成$1$。
最后，只用在HASH表里找$S_1$是否存在就好了。别忘了判断是否为最优解。
因为每次只枚举一半，所以时间复杂度最多为$2^{20}$。
我不会告诉你我不贴代码是因为我死活调不出来QAQ
上面所用到的先枚举前一半的状态，保存结果，再枚举后一半与前一半进行某种操作得出结果的做法就是折半枚举。