题解 P2040 【打开所有的灯】
Creeper_LKF
2017-10-06 22:13:16
我知道这是道水题,所以自然来水一发题解。
显然题目的数据范围是很小的,所以直接上O(2^9)的暴力即可。
然后我们认识到一个事实:答案不会超过9.因为如果答案超过了9自然说明有点被重复改变状态,如果改变奇数次,等价于改变一次,如果改变偶数次,等价于没有改变。所以答案不会超过9.
然后下面用了一堆位运算来减小常数。
```cpp
#include<cstdio>
using namespace std;
const short pow[10]={0,1,2,4,8,16,32,64,128,256};//枚举二进制串00...010...00
short l[10],s,ans;
inline bool ch(short tar){
return s&pow[tar];//返回bool型判断state状态中i是否被改变
}
inline bool check(short tar){//检查一个点最后的情况(被改变的情况异或原来的情况)
switch(tar){
case 1:return ch(1)^ch(2)^ch(4)^l[1];
case 2:return ch(1)^ch(2)^ch(3)^ch(5)^l[2];
case 3:return ch(2)^ch(3)^ch(6)^l[3];
case 4:return ch(1)^ch(4)^ch(5)^ch(7)^l[4];
case 5:return ch(2)^ch(4)^ch(6)^ch(8)^ch(5)^l[5];
case 6:return ch(3)^ch(5)^ch(6)^ch(9)^l[6];
case 7:return ch(4)^ch(7)^ch(8)^l[7];
case 8:return ch(5)^ch(7)^ch(8)^ch(9)^l[8];
case 9:return ch(6)^ch(8)^ch(9)^l[9];
}
}
void dfs(short depth,short state){//dfs枚举情况(for循环也行)
if(depth==9){
s=state;
if(check(1)&&check(2)&&check(3)&&check(4)&&check(5)&&check(6)&&check(7)&&check(8)&&check(9)) ans=state;
return ;
}
dfs(depth+1,state);
dfs(depth+1,state|(1<<depth));
}
int main(){
for(short i=1;i<=9;i++) scanf("%hd",&l[i]);
dfs(0,0);
short sum=0;
for(short i=1,j=1;i<=9;i++,j<<=1) sum+=(bool)(ans&j);//统计方案
printf("%hd",sum);
return 0;
}
```