P4906小奔关闹钟（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 7.9k | 阅读时长 ≈ 7 分钟

这里有一篇题解。

P4906 小奔关闹钟

点我

PS.

暂无

Problem.

  1. 目标：关闭所有的电灯
  2. 特殊：关了一个点灯之后，会影响其他电灯的开闭，其他点灯的开闭又继续影响
  3. 限制：上面的影响只会持续2轮，不要问我为什么，我是从样例中看出来的QwQ

    Solution.

    由于题意分析中的第三条，我们可以考虑初始化更改一个点灯的状态后会产生的影响。
    复杂度是$\texttt{O(n}^\texttt{3}\texttt{)}$，对于$\texttt{1<n<20}$的数据一定能过。
    然后就可以暴力$\texttt{dfs}$来求答案了。
    当然，如果两次或多次关同一盏灯，那么开关的效果会被抵消，所以对于每一个点，只有动与不动两种情况。
    所以$\texttt{dfs}$的复杂度是$\texttt{O(2}^\texttt{n}\texttt{)}$，能过。

    Attention.

    由于$\texttt{n<=20}$，$\texttt{2}^\texttt{20}=1048576$，在$\texttt{int}$的数据范围内，所以我们可以考虑状压。
    由于开灯与关灯具有如下性质：$\texttt{0+0=0,1+1=0,0+1=1,1+0=0}$，所以我们可以把它当成异或操作。

    Coding.

    代码里有解释
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include<bits/stdc++.h>
    #define ya(x) (1<<(x))			//状压函数，把一个集合压成一个数字
    #define go(x,y) ((x)!=(y)&&a[(x)][(y)])		//判断函数：这里有一个坑点，就是一盏灯自己会指向自己，要加一个特判
    using namespace std;
    const int N=25,INF=1000000007;
    int n,m,ans,cha[N];
    char a[N][N];
    inline int dfs(int x,int s)
    {
    	if(x==n+1) {if(s==0) return 0;return INF;}		//递归的边界
    	return min(dfs(x+1,s),dfs(x+1,s^cha[x])+1);		//枚举这一盏灯动不动
    }
    inline void init()		//读入函数，没什么好解释的把
    {
    	scanf("%d",&n);
    	memset(a,0,sizeof(a));
    	for(int i=1,t,x;i<=n;i++)
    		for(scanf("%d",&t);t--;)
    			scanf("%d",&x),a[i][x]=1;
    }
    inline void ready()		//前面说的预处理部分
    {
    	memset(cha,0,sizeof(cha));	//cha代表change，表示动一下这个开关，会产生的影响的状态（已压缩
    	for(int i=1;i<=n;i++)
    	{
    		cha[i]^=ya(i-1);	//它本身状态改变
    		for(int j=1;j<=n;j++)	//持续的第一轮
    			if(go(i,j))
    			{
    				cha[i]^=ya(j-1);
    				for(int k=1;k<=n;k++) if(go(j,k)) cha[i]^=ya(k-1);	//它持续的第二轮
    			}
    	}
    	ans=dfs(1,ya(n)-1);		//找到答案
    }
    int main()
    {
    	return init(),ready(),ans<=INF?printf("%d\n",ans):puts("Change an alarm clock，please!"),0;		//一行的主程序完美地结束
    }