问题描述
蓝桥学院由 21 栋教学楼组成,教学楼编号 1 到 21。

对于两栋教学楼 a 和 b,当 a 和 b 互质时,a 和 b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。

小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼(即走一条哈密尔顿回路),

请问他有多少种不同的访问方案?两个访问方案不同是指存在某个 i,小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。

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

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


答案:881012367360


题解
状压DP:

f[i][j]:从 1 走到 j,且经过的点的状态为 i 的方案数;

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 22, M = 1 << N;

LL f[M][N];
bool e[N][N];

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	for (int i = 1; i <= 21; i ++)
		for (int j = 1; j <= 21; j ++)
			if(gcd(i, j) == 1)
				e[i][j] = true;
				
	f[2][1] = 1;
	for (int i = 2; i <= M - 2; i ++)
		for (int j = 1; j <= 21; j ++)
			if(i >> j & 1)
				for (int k = 1; k <= 21; k ++)
					if(i - (1 << j) >> k & 1 && e[k][j])
						f[i][j] += f[i - (1 << j)][k];
	
	LL ans = 0;
	for (int i = 2; i <= 21; i ++)
		ans += f[M - 2][i];
	
	cout << ans << endl;		
	return 0;								
}

ps:要运行 13 秒,但是可以将 1 ~ 21 映射成 0 ~ 20,效率会快一倍,代码如下;

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 21, M = 1 << N;

LL f[M][N];
bool e[N][N];

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	for (int i = 1; i <= 21; i ++)
		for (int j = 1; j <= 21; j ++)
			if(gcd(i, j) == 1)
				e[i - 1][j - 1] = true;
				
	f[1][0] = 1;
	for (int i = 1; i <= M - 1; i ++)
		for (int j = 0; j <= 20; j ++)
			if(i >> j & 1)
				for (int k = 0; k <= 20; k ++)
					if(i - (1 << j) >> k & 1 && e[k][j])
						f[i][j] += f[i - (1 << j)][k];
	
	LL ans = 0;
	for (int i = 1; i <= 20; i ++)
		ans += f[M - 1][i];
	
	cout << ans << endl;	
	return 0;								
}

蓝桥杯C/C++省赛历年题

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐