题解 P4906 【小奔关闹钟】

lilns · 2018-10-24 10:58:57 · 题解

很激动。我的第一篇题解，主要是因为感觉做出来个黑题难以想象。毕竟菜鸡如我，最多也就做个蓝题。 ~~（当然这个题有点水，要不我也做不出来）~~ 好了话不多说我们看一下这个很有水准的题。

首先看一下题目

由于今天是星期一，闹钟准时响了，由于小奔太困了，所以她想关停闹钟。

嗯。。。。。。。。
这个孩子不大行，我们把它稍微改一下；

~~由于今天是星期一，闹钟没有响，由于小奔太爱学习了，所以她想开启闹钟~~。

这样就题目就清楚多了吧；

可是，他的闹钟电路太复杂了，有很多个开关，每个开关都连着其他开关，其他开关又连着更多的开关，当且仅当所有开关都打开时，闹钟才会开始响铃，（初始时默认每个开关都关的），她该如何是好呢//这里改一下，初始时所有都开变为都关，感觉更好理解。

当打开第i个开关时，只有直接关联，间接关联以及第i个开关才会起作用。这句话的意思是我们要和他在两层关系以内的点都会因为这个点打开而打开，2层以后就不需要了，这是解题和这题可做的原因。

请你帮小奔求出最少开关次数，如果无论如何都不能开启闹钟，请输出‘Change an alarm clock，please!’

我们先导入一组小样例

我们看一下每一次只打开一个的情况

当只打开1的时候，2,3会因此而打开 1{2，3}，然后因为2打开的有3，因为开关摁两下相当于没摁。所以3关闭，最后只有{1，2}。
当只打开2的时候，3回打开 2，{3}，然后因为3打开的有1 , 2{ 3 { 1 } },此时所有开关都打开，方案可行，ans=1。
当只有3打开的时候，1会因此打开 3{1}，因为1而打开的有2,3 此时情况为 3{ 1 { 2 } }，不可行。

从上面看来，最优解ans=1，也就是只打开2的时候。

我们回过头来再看一下数据范围，n<=20......... 忍住，忍住不要想状压dp。哼，不让我想状压dp，我想状压总行了吧，反正没dp。当然不状压也行，但感觉麻烦点，可能要开多个数组。

说了这么多，其实这个题用搜索做就好啦，深搜，广搜都可以，等下下会有代码。

介绍一下我方法。

首先存的时候用矩阵存就好啦，（n<=20真的是可以为所欲为）然后预处理一个res数组，表示在打开一个点后所带来的两层之内的影响。在通过搜索处理出答案。

这是res数组处理方法，res[i]的值在亦或^时可以对答案直接产生贡献。解释一下亦或^的原因（来自弱鸡的问候:状压应该懂得吧，二进制上01代表选或不选，因为前面提到同一个开关摁两次想当于不摁，我们因此有了x=（x+1）%2,这相当于亦或^);

当搜索到now>n 而且sum=0的时候，尝试更新答案并返回。//深搜当搜索到w==sum的时候，此时输出答案，此时一定是最优解//广搜

最后提个坑 在表示和i直连的开关中可能会有i，所以我么需要特判。

    for(int i=1;i<=n;i++)
    {
        res[i]^=(1<<i);
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]&&i!=j)
            {
                res[i]^=(1<<j);
                for(int k=1;k<=n;k++)
                {
                    if(a[j][k]&&j!=k)   res[i]^=(1<<k);

                }
            }
        }
    }

深搜代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int f[8000000],a[25][25],res[25],n,m,sum,ans=-1,an;
void dfs(int now,int sum,int cnt)
{
    if(now>n)
    {
        if(sum==0)
        {
            if(ans==-1||ans>cnt)
            {
                ans=cnt;
            }
        }
        return ;
    }
    dfs(now+1,sum,cnt);
    sum^=res[now];
    dfs(now+1,sum,cnt+1);
    sum^=res[now];
} 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            a[i][x]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        res[i]^=(1<<i);
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]&&i!=j)
            {
                res[i]^=(1<<j);
                for(int k=1;k<=n;k++)
                {
                    if(a[j][k]&&j!=k)   res[i]^=(1<<k);

                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        sum+=(1<<i);
    }
    dfs(1,sum,0);
    if(ans==-1) printf("Change an alarm clock，please!");
    else printf("%d \n",ans);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",res[i]);
    }
    printf("\n%d",sum);
    return 0;
}

广搜代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=20010;
int sum,vis[N],n,m,a[N][N],res[N],ans=-1;
struct node{
    int x,d;
};
queue<node>q; 
int read()
{
    int ans=0;char ch;bool c=false;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') c=true;ans=ch-48;
    while((ch=getchar())>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+ch-48;
    return c==true?-ans:ans;
}

void bfs()
{
    q.push(node{0,0}); vis[0]=1;
    while(!q.empty())
    {
        node x=q.front();q.pop();
        int w=x.x,d=x.d;vis[w]=0; 
        for(int i=1;i<=n;i++)
        {
            int r=w^res[i];
            if(r==sum) 
            {
                printf("%d",d+1);
                exit(0);
            }
            if(!vis[r])
            {
                q.push((node){r,d+1});
                vis[r]=1;
            }
        }
    }
}
int main()
{   
    n=read();
    for(int i=1;i<=n;i++)
    {
        m=read();
        for(int o=1;o<=m;o++) a[i][read()]=1; 
    }
    sum=pow(2,n)-1;

    for(int i=1;i<=n;i++) 
    {
        int w=sum^1<<(i-1);
        for(int j=1;j<=n;j++)
        if(a[i][j]&&i!=j)
        {
            w^=1<<(j-1);
            for(int k=1;k<=n;k++)
            if(a[j][k]&&j!=k) w^=1<<(k-1); 
        }
        res[i]=sum^w; 
    }
    bfs();
    printf("%d",ans);
    return 0;
}

。。。。真·完结散花。希望各位大佬支持一下，初次写题解，还请见谅，不会可以直接call我。