FQR_的博客

FQR_的博客

0%

P1869 互不侵犯 题解

题目传送门

思路

对于每一行，我们可以将它设置为一个状态。

比如这一行：

（红的是国王，白的为空）

假设空的为 $0$，国王为 $1$，那么这一行的状态就可以表示为 $0100101$。

把 $0100101$ 看作是一个二进制数，那么它的十进制为 $37$。

我们不需要存储 $0100101$，只存储 $37$ 即可。这就是本题状态压缩的思路。

因此我们称这一行的状态为 $37$。

根据题意可得，当一行内没有相邻的国王时，这一行就成立。

那么，我们如何判断一个状态是否成立呢？

不难想到，可以 $\mathcal{O}(n)$ 枚举，但这样速度太慢。

那么，我们就要用到下面几个位运算。

  1. a & b：按位与。当二进制数 $a$ 与 $b$ 不存在同一位都为 $1$，结果就为 $0$。
  2. a << 1：左移。将二进制数 $a$ 的所有位置上的数字向左移动一位。
  3. a >> 1：右移。将二进制数 $a$ 的所有位置上的数字向右移动一位。

假设此行的状态为 $a$。（$a$ 是一个二进制数 ）

我们先将 $a$ 左移一位，再与原始的 $a$ 对齐

1
2
原始的a：          a[1] a[2] a[3]  
左移一位后的a：a[1] a[2] a[3] a[4]...

这样，我们就把 $a_i$ 和 $a_{i+1}$ 对齐了。

将这两个数进行按位与运算。

如果返回值为 $0$，说明不存在 $a_i$ 和 $a_{i+1}$ 都为 $1$ 的情况。

所以可得，当 (a&(a<<1))==0)时，状态 $a$ 成立。

再思考，什么条件下，上面一行的状态为 $s1$，下面一行的状态为 $s2$，且上下不冲突。

假设上面一行的第 $i$ 位为 $1$ ，那么下面一行的第 $i-1$、$i$、$i+1$ 位都不能是 $1$。

$~$

先将 $s1$ 与 $s2$ 对齐

1
2
s1：s1[1] s1[2] s1[3] s1[4]...
s2：s2[1] s2[2] s2[3] s2[4]...

此时 $s1_i$ 与 $s2_i$ 对齐。

将 $s1$ 与 $s2$ 进行按位与运算。如果返回值为 $0$，就说明不存在 $s1_i$ 与 $s2_i$ 都为 $1$。

$~$

再将 $s1$ 与 左移一位的$s2$ 对齐。

1
2
s1：      s1[1] s1[2] s1[3]...
s2：s2[1] s2[2] s2[3] s2[4]...

此时 $s1_i$ 与 $s2_{i+1}$ 对齐

将 $s1$ 与 左移一位的$s2$ 进行按位与运算。如果返回值为 $0$，就说明不存在 $s1_i$ 与 $s2_{i+1}$ 都为 $1$。

$~$

最后将 $s1$ 与 右移一位的$s2$ 对齐。

1
2
s1：s1[1] s1[2] s1[3] s1[4]...
s2：      s2[1] s2[2] s2[3]...

此时 $s1_i$ 与 $s2_{i-1}$ 对齐

将 $s1$ 与 右移一位的$s2$ 进行按位与运算。如果返回值为 $0$，就说明不存在 $s1_i$ 与 $s2_{i-1}$ 都为 $1$。

$~$

如果上面的三个条件都满足，就说明：当 $s1_i=1$ 时，$s2_{i-1}$、$s2_{i}$、$s2_{i+1}$ 都不为 $1$ 。

所以可得，当 (s1&s2==0)&&(s1&(s2<<1))==0)&&((s1&(s2>>1))==0)时，$s1$ 与 $s2$ 不冲突。

接下来推转移方程式.

假设 $dp[i][j][k]$ 表示第 $i$ 行，使用了 $j$ 个国王，此行的状态为 $k$ 的方案数。

那么，若现在为第 $i$ 行，使用了 $l$ 个国王，当前行状态为 $s2$，上一行状态为 $s1$，转移方程就是 dp[i][l][s2]+=dp[i-1][l-cnt_king[s2]][s1];

注：cnt_king[s2] 为状态为 $s2$ 的国王个数。

代码

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
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
int n,k;
int cnt_king[3000];
int dp[10][100][3000];
vector<int> p;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<(1<<n);i++)//枚举每一个状态，状态数量为 2^n 个
    {
        int x=i,res=0;//res:状态为i时，国王的个数
        while(x)
        {
            x-=(x&-x);//减去最低位的1
            res++;
        }
        cnt_king[i]=res;
        if(((i&(i<<1))==0)) p.push_back(i);//判断i是否合法。如果合法，就加入p里
    }
	
    dp[0][0][0]=1;
	
    for(int i=1;i<=n;i++)//当前是第i行
    {
        for(int j=0;j<p.size();j++)//枚举当前行的状态
        {
            int s2=p[j];
            for(int m=0;m<p.size();m++)//枚举上面行的状态
            {
                int s1=p[m];
                if(!(((s1&s2)==0)&&((s1&(s2<<1))==0)&&((s1&(s2>>1))==0))) 
                    continue;//如果不合法，就直接跳过
					
                 for(int l=cnt_king[s2];l<=k;l++) //遍历国王个数
                    dp[i][l][s2]+=dp[i-1][l-cnt_king[s2]][s1];//转移方程
            }
        }
    }
    int ans=0;
    for(int i=0;i<p.size();i++) 
        ans+=dp[n][k][p[i]];//将最后一行，国王个数为k，所有状态的方案数相加
    cout<<ans;
    return 0；
}