CCYL Membership Activist

题解 P1391 【方阵安排】

2021-08-05 16:17:43


emm 为什么题解区大佬都不愿意用状压啊……


看到这题的数据范围:

  • 对于 $100 \%$ 的数据,保证 $n \leq 18$。

而众所周知,int 类型的变量可以存储 32 位带符号整数(去除符号位共 31 位)。也就是说,在这题中,我们甚至不需要 long long 就能将题目中方阵的一行塞到一个变量里(状态压缩)。
思路和其他几篇题解大致相同,但是貌似细节上还是不太一样,并且我的码量介于题解区另外两位大佬之间。
思路简述:

  1. 枚举第一行可能出现的所有状态(状态压缩)
  2. 对于每一种状态:
    1. 验证其是否合法,若其不合法则直接进入下一种状态
    2. 若其合法,则使用一个循环,数出从原方阵的第一行转移到此状态所需要的步骤
    3. 对其进行深度优先搜索:
      1. 根据传入的状态推导出下一行(程序里有详细过程)
      2. 在下一行重复此过程

对于这个思路,我们需要考虑一个问题:什么样的状态是不合法的?
很显然,题目中有明确表述,女生可以改成男生,但是男生不能改成女生。(女拳震怒
还是结合程序说实际一些:

//Luogu-P1391 
//Luogu @Enterpr1se (Userid 363523)
//@_Qijia (Userid 363524) AK IOI!
#include<cstdio>
#define regll register long long
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
_Qijia AK IOI;
int n,mp[20],temp,ans=0x7fffaded,sstep;
bool flag;
int bin_digit(int num,int id){//获取一个二进制数的第 id 位(最低位为第0位) 
    return ((num&(1<<id))>>id);
}
int min(int a,int b){
    return a<b?a:b;
}
void dfs(int id,int currln,int curstep,int prevln=0){
    if(id==n){//如果已经扫过整个方阵,并且没有出现不合法状态 
        ans=min(ans,curstep);//更新答案 
        return;
    }
    int surmal/*一个人周围已有的男生数*/,nextln=0/*下一行的状态*/,nstep=0/*到下一行为止总共的换人次数*/;
    for(regint i=1;i<=n;++i){
        surmal=bin_digit(currln,i-1)+bin_digit(currln,i+1)+bin_digit(prevln,i);//一个人周围的总男生数 = 左边 + 右边 + 上一行同一位置男生数 
        nextln+=((surmal&1)<<i);//更新状态(将新一位加入到下一行的状态中) 
        if((bin_digit(mp[id+1],i)^bin_digit(nextln,i))){//如果下一行该位置需要的人与原方阵中此位置的人性别不同 
            ++nstep;//增加一次换人 
            if(bin_digit(mp[id+1],i))/*若原方阵中此位置是男生*/ return;
        }
    }
    dfs(id+1,nextln,curstep+nstep,currln);//从下一行开始搜索 
    return;
}
signed main(){
    scanf("%d",&n);
    for(regint i=1;i<=n;++i)
        for(regint j=1;j<=n;++j,mp[i]<<=1)
            scanf("%d",&temp),mp[i]+=temp;//将新输入的一位加在末尾 
    for(regint i=0;i<(1<<(n+1));i+=2){//枚举第一行所有状态 
        sstep=0;//初始化 
        flag=true;
        for(regint j=1;j<=n;++j){//检查状态是否合法 并 算出第一行换人次数 
            if((bin_digit(mp[1],j)^bin_digit(i,j))){//类似于 Ln29 至 Ln32 
                ++sstep;
                if(bin_digit(mp[1],j)){
                    flag=false;
                    break;
                }
            }
        }
        if(flag) dfs(1,i,sstep);//如果状态合法 
    }
    printf("%d",((ans^0x7fffaded)?ans:-1));
    return 0;
}

注:这题的状压看着有些奇怪,因为我决定将二进制数的最低位留空(永远为 0),这样在获取二进制数某一位的时候更加方便。例如样例中第二行,在本程序中存储为 $ 1000_2 $。
$\mathtt{Thanks}\text{ }\mathtt{for}\text{ }\mathtt{reading.}\text{ }$