蓝桥杯算法题目-垒骰子-使用 C++ 解法
source link: https://blog.sbw.so/u/lanqiao-cpp-dice-combination-code.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
做了道蓝桥杯算法题：赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！ 我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。 假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。atm想计算一下有多少种不同的可能的垒骰子方式。两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。 由于方案数可能过多，请输出模 10^9 + 7 的结果。
先分析一下最简单情况，不考虑互斥问题：假如只有一个骰子，由于有6个面，每个面朝上的时候侧面都可以旋转得到4个不同的摆放结果，所以总共有4*6=24种结果。 那么现在再增加一个骰子，两枚骰子来摆的话，那就总共可以有(4*6)*(4*6)=576种摆法。
再考虑题目中说的“互斥”问题：6个面可以互斥，由于A与B互斥时，B也与A互斥，所以总共有21种互斥可能（1+2+3..+6）。由于题目规定1对面是4，不妨先测试除了[1,4]和[4,1]以外，其它面都互斥的情况。 当有1个骰子时，互斥条件不存在，所以依然是24。当有2个骰子时，两个骰子贴合的地方只可能是(1, 4)或者(4, 1)。当为(1, 4)时，有4*4种组合，当为(4, 1)时，也有4*4种组合，总共32种。
当有3个骰子时，依此类推，有4*4*4*2种组合。
这样就可以看出规律了：当新加一个骰子时，就会在上一个情况的基础上再乘以当前骰子能带来的变化数量，而这个变化数量又依赖与上一个骰子哪个面向上，以及数据所给出的互斥条件。同时，由于在第一个骰子时不存在和上一个骰子的互斥，所以第一个骰子需要额外处理一下。
所以大概程序的构思就是这样：假设现在已经排列好了K-1个骰子，我们当前要计算的结果是K个骰子，最终结果是N个骰子。那么我们需要先知道第K-1个骰子向上的是哪个面，然后根据这个数据和条件所给的互斥数据，遍历第K个骰子可以向下的面的列表。假设有一个不互斥的面，那么就会产生f(K-1)*4种摆法。将所有不互斥的面的摆法相加，即可得到最终结果。
另外，除了当骰子只有一个时，不计算互斥条件以外，还有另一个边界条件，那就是在某条排列路径上，一个骰子的顶面可能会导致接下来的骰子无法摆放，即与下一个骰子的所有面都会造成互斥。
具体实现代码如下，注释已经写的很详细了，应该不需要额外说明了。
#include <iostream>using namespace std;// 总骰子数int N = 0;// 映射某一面与其对面的面编号，0 位置不用int Map[7] = { 0, 4, 5, 6, 1, 2, 3 };// 存储互斥条件bool Forbids[7][7] = { false };#define MOD 1000000007// 计算 sum += r * 4，并按题目规定取余uint64_t round_add_mul(uint64_t sum, uint64_t r){if (r == 0)return sum;sum = sum % MOD;r = r % MOD;r = (4 * r) % MOD;return (sum + r) % MOD;}// 递推计算，top 为上一个骰子向上的面，remain 为还剩下多少个骰子uint64_t f(int top, int remain){// 当骰子排列完时，结束，这里以 0 作为终结以及返回 1 是为了恰好和下面算法对应if (remain == 0)return 1;// sum 保存了从当前骰子开始，到最后一个骰子的排列数量uint64_t sum = 0;// 依次遍历每个面进行测试，这里的 i 为当前骰子的底面// 所有可能的情况为底面取 1 的情况 + 底面取 2 的情况 + ...for (int i(1); i != 7; ++i){// 当前底面和上一个骰子的顶面是否互斥，互斥时，这趟计算结果是不能用的if (Forbids[top][i])continue;// 对剩下的骰子进行排列，新的顶面数据由 Map 转换auto r = f(Map[i], remain - 1);// 剩下的骰子总共有 r 种排列组合，由于当前顶面、底面不变，还可以旋转 4 次，所以 sum += r * 4// 假如当前骰子是最后一个骰子，下一次计算返回 1，这里依然可以用同样的公式计算 sum += 1 * 4// 这是为什么上面的返回条件是以 0 结束并返回 1 的原因sum = round_add_mul(sum, r);}// 当前排列数量算清楚之后，再交给上一轮，乘以上一个骰子的那个 4return sum;}int main(){int m;cin >> N >> m;for (int i(0); i != m; ++i){int a, b;cin >> a >> b;Forbids[a][b] = true;Forbids[b][a] = true;}uint64_t sum = 0;// 此处 i 为第一个骰子的顶面数据for (int i(1); i != 7; ++i){// 对于第一个骰子，无需计算互斥，直接遍历auto r = f(i, N - 1);// 拿到剩下的排列数据 r 之后，r * 4 就是当前以 i 为顶面的排列个数// 把 6 个顶面的排列个数相加，就是最终结果sum = round_add_mul(sum, r);}cout << sum << endl;return 0;}Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK