侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS, 动态规划】垒骰子【蓝桥杯】

GabrielxD
2022-09-19 / 0 评论 / 0 点赞 / 47 阅读 / 2,086 字 / 正在检测是否收录...

题目

试题 历届真题 垒骰子【第六届】【省赛】【C组】

1217. 垒骰子


赌圣 atm 晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。

经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥!

我们先来规范一下骰子:11 的对面是 4422 的对面是 5533 的对面是 66

假设有 mm 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。

atm 想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多,请输出模 109+710^9 + 7 的结果。

输入格式

第一行包含两个整数 n,mn,m,分别表示骰子的数目和排斥的组数。

接下来 mm 行,每行两个整数 a,ba,b,表示 aabb 数字不能紧贴在一起。

输出格式

共一个数,表示答案模 109+710^9 + 7 的结果。

数据范围

对于 30% 的数据:n5n \le 5
对于 60% 的数据:n100n \le 100
对于 100% 的数据:0<n109,m360 < n \le 10^9, m \le 36

输入样例:

2 1
1 2

输出样例:

544

解题

方法一:DFS(超时)

思路

每个骰子有 66 个面,而在上下面固定时可以旋转 44 次,那么如果 nn 个骰子垒在一起不存在冲突面时就有 6n×4n6^n \times 4^n 种情况。

以测试用例:

2 1
1 2

为例,其表示有 22 个骰子垒在一起,其中有一组排斥面:1122 互相排斥。
那么:

  • 当第二个骰子 44 朝上时,其 11 朝下,第一个骰子就不能把 22 朝上,少了一种情况。
  • 当第二个骰子 55 朝上时,其 22 朝下,第一个骰子就不能把 11 朝上,又少了一种情况。

所以此时垒骰子的方案数是:(6211)×42=3416=544(6^2 - 1 - 1) \times 4^2 = 34 * 16 = 544,如图(没体现出四周旋转多形成的方案):

image-20220919151700303

那么很容易想到使用递归模拟求解:
用一个哈希表(opp)(可用数组代替)定义骰子的对面:opp[1] = 4, opp[4] = 1, opp[2] = 5, ...
再用一个哈希表(conflict)(可用数组代替)记录骰子的对立面。

从最上层的骰子(n)开始递归:

  • 递归函数 dfs(int top, int dice),其中 top 表示当前骰子朝上的数字,dice 表示当前骰子在第几层。
  • 递归的结束条件:当递归到第一层骰子时结束,返回该骰子可以有 44 种摆放方案(侧面的四个方向)。
  • 对于 n~2 层的骰子,先取出它们底面的数字(bottom = opp[top]),然后循环 1~6 ,与当前层底面数字不冲突时(!conflict[bottom][i])作为下一层骰子的顶面数字(递归),返回的方案数也要乘以 44,因为该层骰子侧面也可以旋转四个方向。

注意:方案数每次更新都要对 1e9+7 取模,否则可能溢出。

时间复杂度:O(6n)O(6^n)

参考:https://www.bilibili.com/video/BV1QE411E7ft?p=52

代码

import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final int[] opp = {-1, 4, 5, 6, 1, 2, 3};
    static boolean[][] conflict = new boolean[7][7];
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        while (m-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        // 输入完成
        long ans = 0L;
        for (int i = 1; i <= 6; ++i) {
            ans = (ans + dfs(i, n)) % MOD;
        }
        System.out.println(ans);
    }

    static long dfs(int top, int dice) {
        if (dice == 1) return 4;
        long poss = 0L;
        int bottom = opp[top];
        for (int i = 1; i <= 6; ++i) {
            if (conflict[bottom][i]) continue;
            poss = (poss + 4 * dfs(i, dice - 1)) % MOD;
        }
        return poss;
    }
}

方法二:动态规划(超时)

思路

在之前我们发现:垒 nn 个骰子的方案数是 (6nk)×4n(6^n - k) \times 4^n (其中 kk 表示面有排斥舍弃的方案数)。
可以看出方案数与 4n4^n 无关,那么我们可以先忽略骰子侧边的四个面,算出方案数再乘以 4n4^n

于是我们可以从第一层开始递推(动态规划):

  1. 状态:dp[i][j] 表示在第 i 层顶部为数字 j 的骰子的合法方案数。

  2. 状态转移方程:

    dp[i][j]=x=16dp[i1][x]  opp[j]x不冲突dp[i][j] = \sum_{x=1}^{6}dp[i-1][x]\ |\ opp[j] 与 x 不冲突

    观察到当前行的状态只与上一行有关,可以使用滚动数组

  3. 初始状态:第一层的骰子以每个数字朝上的方案数都是 11dp[0][1:7]=1dp[0][1:7]=1

以输入样例 1 为例:

1(4) 2(5) 3(6) 4(1) 5(2) 6(3)
1 1 1 1 1 1 1
2 6 6 6 5 5 6

方案数就是最后一行的总和再乘上 4n4^n4n×x=16dp[n][x]=42×(6+6+6+5+5+6)=5444^n \times \sum_{x=1}^{6}dp[n][x]=4^2 \times (6+6+6+5+5+6)=544

时间复杂度:O(n)O(n)

参考:https://www.bilibili.com/video/BV1QE411E7ft?p=53

代码

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final int[] opp = {-1, 4, 5, 6, 1, 2, 3};
    static boolean[][] conflict = new boolean[7][7];
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        while (m-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        // 输入完成
        long[][] dp = new long[2][7]; // 滚动数组
        Arrays.fill(dp[0], 1); // 初始化
        int prev = 1, curr = 0;
        // 迭代层数
        for (int level = 2; level <= n; ++level) {
            // 滚动
            int tmp = prev;
            prev = curr;
            curr = tmp;
            // 尝试在当前层把6个面放在上一层的上方
            // upperTop 表示当前层某骰子A顶部的数字
            for (int upperTop = 1; upperTop <= 6; ++upperTop) {
                // 当前层骰子A的合法方案数
                long poss = 0L;
                // 当前层骰子A底部的数字
                int upperBottom = opp[upperTop];
                for (int lowerTop = 1; lowerTop <= 6; ++lowerTop) {
                    // 当前层骰子A底部与上一层骰子B顶部不冲突时把上一层骰子B的可能方案数累加进 poss
                    if (conflict[lowerTop][upperBottom]) continue;
                    poss = (poss + dp[prev][lowerTop]) % MOD;
                }
                // 更新当前层骰子A的合法方案数
                dp[curr][upperTop] = poss;
            }
        }
        long sum = 0L;
        for (int i = 1; i <= 6; ++i) sum = (sum + dp[curr][i]) % MOD;
        // 快速幂求 4^n
        long ans = 1L, base = 4L;
        while (n != 0) {
            if ((n & 1) != 0) ans = (ans * base) % MOD;
            base = (base * base) % MOD;
            n >>= 1;
        }
        System.out.println((sum * ans) % MOD);
    }
}
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int opp[] = {-1, 4, 5, 6, 1, 2, 3};
bool conflict[7][7];
long long dp[2][7];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        conflict[a][b] = true;
        conflict[b][a] = true;
    }
    // 输入完成
    for (int i = 1; i <= 6; ++i) dp[0][i] = 1L;
    int prev = 1, curr = 0;
    for (int level = 2; level <= n; ++level) {
        swap(curr, prev);
        for (int upper_top = 1; upper_top <= 6; ++upper_top) {
            long poss = 0L;
            int upper_bottom = opp[upper_top];
            for (int lower_top = 1; lower_top <= 6; ++lower_top) {
                if (conflict[lower_top][upper_bottom]) continue;
                poss = (poss + dp[prev][lower_top]) % MOD;
            }
            dp[curr][upper_top] = poss;
        }
    }
    long long sum = 0L;
    for (int i = 1; i <= 6; ++i) sum = (sum + dp[curr][i]) % MOD;
    // 快速幂
    long long ans = 1L, base = 4L;
    while (n != 0) {
        if ((n & 1) != 0) ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        n >>= 1;
    }
    printf("%lld", (sum * ans) % MOD);

    return 0;
}
0

评论区