蓝桥杯-回路计数(状态压缩、动态规划)

这篇具有很好参考价值的文章主要介绍了蓝桥杯-回路计数(状态压缩、动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11​​ 到 21 21 21​​。对于两栋教学楼 a a a b b b​,当 a a a b b b互质时, a a a b b b之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。

小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼(即走一条哈密尔顿回路),请问他有多少种不同的访问方案?

两个访问方案不同是指存在某个 i i i,小蓝在两个访问方法中访问完教学楼 i i i后访问了不同的教学楼。

提示:建议使用计算机编程解决问题。

答案提交

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

运行限制

最大运行时间:1s
最大运行内存: 128M

思路和参考代码

本题可以使用动态规划的方法解决。

我们用 1 , 2 , . . . , 21 1,2,...,21 1,2,...,21表示某1栋楼,设全集 A = { 1 , 2 , . . . , 21 } A = \{1,2,...,21\} A={1,2,...,21}。设状态 S V ,   l S_{V,\ l} SV, l表示访问了子集 V V V中的全部路径(每个点均只访问1次)且最后一次落点在 l l l处的可行解的个数,其中 V ⊆ A V \subseteq A VA l ∈ V l \in V lV。即有动态规划方程
S V ,   l = ∑ a ∈ V 且 a , l 互质 S V − { l } ,   a S { 1 } ,   1 = 1 S_{V,\ l} = \sum_{a\in V且a,l互质} S_{V- \{l\},\ a} \\S_{\{1\},\ 1 }= 1 SV, l=aVa,l互质SV{l}, aS{1}, 1=1

最终的答案为 ∑ i = 2 21 S A ,   i \sum_{i=2}^{21}{S_{A,\ i}} i=221SA, i。由于只有21栋楼,因此在实现时路径集合 V V V只需要使用位集压缩在1个int变量中,如经过了完整的21栋楼,经过的路径为0x1fffff

完整实现如下:文章来源地址https://www.toymoban.com/news/detail-472809.html

public class Main {
    static boolean[][] isConnected = new boolean[22][22];
    static final int MAXN = 0x1fffff;
    static long[][] counts = new long[MAXN + 1][22];

    static void init() {
        for (int i = 1; i <= 21; i++) {
            for (int j = i + 1; j <= 21; j++) {
                boolean flag = false;
                for (int k = 2; k <= i; k++) {
                    if (i % k == 0 && j % k == 0) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    isConnected[i][j] = isConnected[j][i] = true;
                }
            }
        }
    }

    static void debug() {
        for (int i = 1; i <= 21; i++) {
            for (int j = i + 1; j <= 21; j++) {
                if (isConnected[i][j])
                    System.out.printf("%d %d\n", i, j);
            }
        }
    }

    static void dp() {
        counts[1][1] = 1;
        for (int i = 1; i <= MAXN; i++) {
            for (int j = 1; j <= 21; j++) {
                if (((i >> (j - 1)) & 1) == 0)
                    continue;
                for (int k = 1; k <= 21; k++) {
                    if (((1 << (k - 1)) & i) != 0 || !isConnected[j][k])
                        continue;
                    counts[i | (1 << (k - 1))][k] += counts[i][j];
                }
            }
        }
    }

    static void printAnswer() {
        long cnt = 0;
        for (int i = 1; i <= 21; i++) {
            if (isConnected[i][1])
                cnt += counts[MAXN][i];
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {
        init();
//        debug();
        dp();
        printAnswer();
    }
}

到了这里,关于蓝桥杯-回路计数(状态压缩、动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 动态规划 状态压缩DP 最短Hamilton路径

    给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。 输入格式 第一行输入整数 n 。 接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[

    2024年02月19日
    浏览(39)
  • 【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性

    【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 动态规划汇总 状态压缩 记忆化搜索 给你一个整数数组 nums​​​ 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中,使得同一个子集里面没有两个相同的元素。 一个子集的 不兼容性 是

    2024年02月19日
    浏览(43)
  • 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

    视频算法专题 动态规划汇总 广度优先搜索 状态压缩 存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号。 给你一个数组 graph 表示这个图。其中,graph[i] 是一个列表,由所有与节点 i 直接相连的节点组成。 返回能够访问所有节点的最短路径的长度。你可

    2024年01月23日
    浏览(40)
  • 图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索

    求解哈密尔顿回路 如何求解一个图是否存在哈密尔顿回路呢? 一个最直观的想法就是暴力求解。暴力求解的思路也很简单:我们遍历图的每一个顶点 v,然后从顶点 v 出发,看是否能够找到一条哈密尔顿回路。 暴力求解的代价同求解全排列问题是等价的,其时间复杂度为

    2024年02月04日
    浏览(36)
  • 【LeetCode动态规划#07】01背包问题一维写法(状态压缩)实战,其二(目标和、零一和)

    力扣题目链接(opens new window) 难度:中等 给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例: 输入

    2023年04月18日
    浏览(63)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(50)
  • C++ 动态规划 数位统计DP 计数问题

    给定两个整数 a 和 b ,求 a 和 b 之间的所有数字中 0∼9 的出现次数。 例如,a=1024,b=1032 ,则 a 和 b 之间共有 9 个数如下: 1024 1025 1026 1027 1028 1029 1030 1031 1032 其中 0 出现 10 次,1 出现 10 次,2 出现 7 次,3 出现 3 次等等… 输入格式 输入包含多组测试数据。 每组测试数据占一

    2024年02月20日
    浏览(41)
  • 动态规划2:题目

    目录 第1题 Fibonacci 第2题 字符串分割(Word Break) .第3题 三角矩阵(Triangle) 第4题 路径总数(Unique Paths) 第5题 最小路径和(Minimum Path Sum) 第6题 背包问题 第7题 回文串分割(Palindrome Partitioning) 第8题 编辑距离(Edit Distance) 第9题 不同子序列(Distinct Subsequences) 分析问题: 1. 状态定义F(i):第

    2024年02月06日
    浏览(43)
  • 动态规划题目练习

    动态规划背包问题-CSDN博客 动态规划基础概念-CSDN博客 题目描述 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河

    2024年04月25日
    浏览(36)
  • 【算法】——动态规划题目讲解

    本期继续为大家带来的是关于动态规划类题目的讲解,对于这类题目大家一定要多加练习,争取掌握。 链接如下: 62. 不同路径 题目如下: 算法思路: 1. 状态表⽰:  对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式: i. 从 [i, j] 位置出发; ii. 从起始位置出发

    2024年02月10日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包