Mondriaan 的梦(HG 2018.4.15 试题1 T3)

2018-04-19 11:51:14


题目部分

【题目描述】

正方形和长方形让荷兰著名画家皮特·蒙德里安着迷了。一天晚上,在他画完了他的“厕所系列” (因为蒙德里安的画纸都已经画满了正方形和长方形,他不得不用厕所纸来作画)之后,他又幻想着 用 1×2(高×宽)的矩形画满厕所纸。 因为厕所纸有限,他想知道有多少种方式可以画满一张厕所纸。 比如当厕所纸如下大小时,用 1×2 的矩形,可以画出以下图形:

请你帮他计算一下,以免他的梦想变成噩梦。

【输入格式】

只有一行 2 个整数,分别为高 h 和宽 w,(1<=h,w<=11)

【输出格式】

画法总数。假设厕所纸是有方向的,即对称的画法算不同的画法。若无法画满,则输出 0。

【输入样例】

2 4

【输出样例】

5




题解部分

一道状压DP,用f[i][j]表示前i-1行已经填完,第i行状态为j的方案数。 j是表示状态的2进制数,如10010表示第一个位置和第四个位置已经被填了。

对于该行某个位置j: 如果前一行该位置为0,那么该位置可以竖放 即 0->1

如果前一行连续两个位置为0,那么这两个连续位置可以横放 即00->00

如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0 ,即1-> 0


若当前状态为s,对s 有下列操作:

  1. 判断第i位是否为0 -> (s & 1 << i) == 0,意思是将1左移i位与s进行与运算后,看结果是否为0.
  2. 将第i位置变为1 -> s | 1 << i,意思是将1左移动i位与s进行或运算.
  3. 将第i位置变为0 -> s & !(1 << i),意思是s与第i位为0,其余位为1的数进行与运算。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
long long f[15][1<<15];
void dfs(int i,int j,int s,int p)
{
    if(p==m)
    {
        f[i][j]+=f[i-1][s];
        return;
    }
    if((1<<p)&j) dfs(i,j,s,p+1);
    else
    {
        dfs(i,j,(s|(1<<p)),p+1);
        if(p+2<=m && !(j&(1<<(p+1)))) dfs(i,j,s,p+2);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    if(n%2 && m%2)//特判,都为奇数无法填满,不加也可以
    {
        cout<<0;
        return 0;
    }
    f[1][0]=1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<(1<<m);j++)
            dfs(i,j,0,0);
    cout<<f[n+1][0];
    return 0;
}

关于为什么两个都是奇数就填不满:

1.总方格数为奇数,而两个两个填总数必为偶数,矛盾

2.牛逼的染色法,将图进行奇偶染色如下图



然后



这样子,图被奇偶染色。然后你发现,怎么填,都会覆盖一个黑和一个白像这样



所以覆盖的黑的总数必定和白的总数相等,但是当都是奇数时黑和白的总数不相等,故不成立。

还有很多神奇的数学染色方法,有兴趣的自行百度啦