题解 P2040 【打开所有的灯】

我知道这是道水题，所以自然来水一发题解。 显然题目的数据范围是很小的，所以直接上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; } ```