题解 P2622 【关灯问题II】

题目

感觉大佬们的代码在读入上的处理比本蒟蒻优秀多了，于是，一个AFO蒟蒻弱弱地提出一下自己的看法

【分析】

首先，对于 \(n\) 那么小，肯定是状压啦

对于读入，本蒟蒻开了两个数组来储存每个按钮的效果：\(Open_i\) 和 \(Close_i\) 分别表示在按下第 \(i\) 个按钮后，它对于开着的开关和关闭的开关所造成的影响

那么我们分开来想：

如果一个状态 \(Set\) 中，为 \(1\) 的位表示开着的灯， \(0\) 表示关闭的

那么，对于关闭的灯，如果 \(Close_i\) 对它有影响，那么一定是将它开启

所以我们将 \(Close_i\) 能影响到的灯的状态直接打上 \(1\)

即如果开关效果为

1 0 -1 -1 0

那么我们将 \(Close_i\) 存为 \(00110_{(2)}=6_{(10)}\)

我们在使用它效果时则可以做到：

如果 \(Set\bigcup Close_i\)，本身 \(Close_i\) 中为 \(0\) 的位不影响

\(Close_i\) 中本身为 \(1\) (即能影响到的位) 中，对于开着的，没有影响，对于关闭的，造成影响并打开

而对于 \(Open_i\)，它的效果恰巧反过来，如果开着，则一定关闭

因此，我们将能影响到的灯的状态打上 \(0\)

对于上面那组数据，我们将 \(Open_i\) 存为 \(01111_{(2)}=15_{(10)}\)

使用时，我们就可以直接这么做 \(Set\bigcap Open_i\)

这样可以保证对于 \(Open_i\) 中为 \(1\) 的位(即不能影响的位)，不会造成影响

而对于会造成影响的位，如果本身是 \(0\) 的不会造成影响，而对于 \(1\) 的则关闭

完美地达到了要求

因此，我们初始化 \(Close_i\) 为空集，\(Open_i\) 为全集

如果读入第 \(i\) 个开关第 \(j\) 个灯为 \(1\) ，则 \(Open_i\) 去掉这一位，如果为 \(-1\) ，则 \(Close_i\) 加上这一位

使用时，对于每个状态 \(Set\) ，和第 \(i\) 个开关，它们能达到的状态就是 \(Set\bigcup Close_i\bigcap Open_i\)

而对于最小步，直接 bfs 即可，详情可以看本蒟蒻代码

【代码】

那本蒟蒻就放我码风极丑的代码了

#include<cstdio>

#include<cstring>

using namespace std;

#define f(a,b,c) for(register int a=b;a<=c;a++)

#define g(a,b,c) for(register int a=b;a>=c;a--)

#define Max(a,b) ((a>b)?a:b)

#define Min(a,b) ((a<b)?a:b)

typedef long long int ll;

typedef unsigned long long int ull;

inline ll read(){

	register ll ans=0;register char c=getchar();register bool neg=0;

	while((c<'0')|(c>'9')) neg^=!(c^'-'),c=getchar();

	while((c>='0')&(c<='9')) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();

	return neg?-ans:ans;

}//前面条件反射，莫管

int main(){

	int N=read(),M=read(),U=(1<<N)-1;

	int Close[110],Open[110],Minn[1<<10];

    //Minn[i] 表示到状态 i 的最小步数

	f(i,1,M) Close[i]=0,Open[i]=U;

	f(i,0,U) Minn[i]=-1;

	f(i,1,M)

		f(j,1,N){

			int Tmp=read();

			if(Tmp==1) Open[i]^=1<<j-1;

			else if(Tmp==-1) Close[i]|=1<<j-1;

		}

	int Queue[1<<10],Head=0,Tail=0;

	Queue[Tail++]=U;

	Minn[U]=0;

    //一开始全部开着

	while(Head<Tail){

		int Set=Queue[Head++];

		f(i,1,M){

			int Tmp=Set&Open[i]|Close[i];

			if(Minn[Tmp]>=0) continue;

            //之前搜到肯定更优

			Minn[Tmp]=Minn[Set]+1;

			Queue[Tail++]=Tmp;

		}

	}

	printf("%d",Minn[0]);

	return 0;

}

最后安利一下本蒟蒻的博客

巴特西

题解 P2622 【关灯问题II】

【分析】

【代码】

最新文章

热门文章