题解：P12891 [蓝桥杯 2025 国 Java B] 瓷砖填充

~最近~学了 DP，刷一条题练练。
建议大家跟着下面《深进》的图片的做法一起做，实在不会才跟着题解一起想。

题意

给出一个

2\times n

的长方形，每个格子填入

1,5,6

中的一个数字，要求上下左右互质，求一共有多少种填法。

思路

动态规划题，首先应该先确定状态。很明显，该题是求出填完第

n

列一共有多少种填法。可以尝试定义

dp_i

，表示填完第

i

列一共有多少种填法。

接着就是转移，可是我们却发现了一个问题，就是题目要求相邻两数互质，转态之间无法直接转移，所以需要重新定义状态。

由于需要保证相邻两数互质，所以需要精确知道当前选的是哪两个数，所以需要多加两维。定义

dp_{z,i,j}

表示正在确定第

z

列、这一列的上面填数

i

、下面填数

j

，的情况下一共有几种填法。

转移是根据状态确定的。因为

dp

表示当前状态下一共有几种填法，所以转移方程是所有可以与

dp_{z,i,j}

拼接的

dp_{z-1,k,l}

的和。动态转移方程：

dp_{z,i,j}=\sum_{\gcd(i,j)=1\land\gcd(k,l)=1\land\gcd(k,i)=1\land\gcd(l,j)=1\land(i,j,k,l\in {1,5,6})}dp_{z-1,k,l}

不过第二三维最大是

6

，达到了

6\times6=36

的空间，所以可以用类似离散化的方法，让

i,j,k,l\in {1,2,3}

，表示选第几个数（甚至用

dp_{z,i}(i\in7)

表示

7

种状态。不过为了讲解方便，我们使用刚才的状态）。既然使用了离散化的状态，就需要用

f_{i,j}

数组记录第

i

个数和第

j

个数是否互质。

$i=1,j=1$ ， $1,1$ 互质。
$i=1,j=2$ ， $1,5$ 互质。
$i=1,j=3$ ， $1,6$ 互质。
$i=2,j=1$ ， $5,1$ 互质。
$i=2,j=2$ ， $5,5$ 不互质。
$i=2,j=3$ ， $5,6$ 互质。
$i=3,j=1$ ， $6,1$ 互质。
$i=3,j=2$ ， $6,5$ 互质。
$i=3,j=3$ ， $6,6$ 不互质。

核心代码

CPP

inline bool chek(int x,int y){//检查
	return f[x][y];
}

if(n==1){//加速，提前输出不比计算的东西
	cout<<7;
	return 0;
}
//记录是否互质和初始值
dp[1][1][1]=dp[1][1][2]=dp[1][1][3]=dp[1][2][1]=dp[1][2][3]=dp[1][3][1]=dp[1][3][2]=f[1][1]=f[1][2]=f[1][3]=f[2][1]=f[2][3]=f[3][1]=f[3][2]=1;
for(int z=2;z<=n;z++)//第z列
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)//当前列的选择
			for(int k=1;k<=3;k++)
				for(int l=1;l<=3;l++)//上一列的选择
					if(chek(k,l)&&chek(k,i)&&chek(l,j)&&chek(i,j))
						dp[z][i][j]=(dp[z][i][j]+dp[z-1][k][l])%mod;
						//如果互质则增加答案
for(int i=1;i<=3;i++)
	for(int j=1;j<=3;j++)
		if(chek(i,j))//这行判断其实可以不用，因为不满足 chek(i,j) 的 dp[n][i][j] 是 0
			ans=(ans+dp[n][i][j])%mod;
cout<<ans;//输出

永无止尽的优化

可以发现，

dp_1

和

f

的存储内容是一样的可以合并；当

i

和

j

代表的数不互质的情况下，

k

和

l

的枚举已经没有意义，可以特判优化掉；这样定义的状态下可以使用矩阵快速幂加速，~不过我不会~……

AC 代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,dp[100001][4][4],ans;
const int mod=1e9+7;
inline bool chek(int x,int y){//检查
	return dp[1][x][y];//优化成 dp[1]
}
int main(){
	cin>>n;//输入
	if(n==1){//加速，提前输出不比计算的东西
		cout<<7;
		return 0;
	}
	//记录是否互质
	dp[1][1][1]=dp[1][1][2]=dp[1][1][3]=dp[1][2][1]=dp[1][2][3]=dp[1][3][1]=dp[1][3][2]=1;
	for(int z=2;z<=n;z++)
	//第z列，要从 2 开始，不然初始值都会变成 0
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++){//当前列的选择
				if(!chek(i,j)) continue;
				//若当前选择不合法，则后面循环是不是互质
				for(int k=1;k<=3;k++)
					for(int l=1;l<=3;l++){//上一列的选择
						if(!chek(k,l)) continue;
						//上一列竖着是不是互质
						if(!chek(k,i)||!chek(l,j)) continue;
						//这两行有是不是互质
						dp[z][i][j]=(dp[z][i][j]+dp[z-1][k][l])%mod;
						//更新答案
					}
			}
	for(int i=1;i<=3;i++)
		for(int j=1;j<=3;j++)
			if(chek(i,j))//检查此状态是否合法（互质）
				ans=(ans+dp[n][i][j])%mod;//增加总答案数量
	cout<<ans;//输出
    return 0;
}

java

JAVA

import java.util.Scanner;
public class Main {
    static int n, ans;
    static int[][][] dp = new int[100001][4][4];
    static final int mod = (int)1e9 + 7;
    // 检查
    static boolean chek(int x, int y) {
        return dp[1][x][y] == 1; // 优化成 dp[1]
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 输入
        if (n == 1) { // 加速，提前输出不比计算的东西
            System.out.println(7);
            return;
        }
        // 记录是否互质
        dp[1][1][1] = dp[1][1][2] = dp[1][1][3] = dp[1][2][1] = dp[1][2][3] = dp[1][3][1] = dp[1][3][2] = 1;
        for (int z = 2; z <= n; z++) {
            // 第z列，要从 2 开始，不然初始值都会变成 0
            for (int i = 1; i <= 3; i++) {
                for (int j = 1; j <= 3; j++) { // 当前列的选择
                    if (!chek(i, j)) continue;
                    // 若当前选择不合法，则后面循环是不是互质
                    for (int k = 1; k <= 3; k++) {
                        for (int l = 1; l <= 3; l++) { // 上一列的选择
                            if (!chek(k, l)) continue;
                            // 上一列竖着是不是互质
                            if (!chek(k, i) || !chek(l, j)) continue;
                            // 这两行有是不是互质
                            dp[z][i][j] = (dp[z][i][j] + dp[z - 1][k][l]) % mod;
                            // 更新答案
                        }
                    }
                }
            }
        }
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (chek(i, j)) // 检查此状态是否合法（互质）
                    ans = (ans + dp[n][i][j]) % mod; // 增加总答案数量
            }
        }
        System.out.println(ans); // 输出
    }
}

代码来之不易，点个赞再走也不迟~

题解：P12891 [蓝桥杯 2025 国 Java B] 瓷砖填充

文章操作

题意

思路

核心代码

永无止尽的优化

AC 代码

相关推荐

评论

题解：P12891 [蓝桥杯 2025 国 Java B] 瓷砖填充