蓝桥杯练习——回路计数前言一、题目二、思路总结

115 阅读 0 评论 76 点赞

我是靠谱客的博主风趣黑夜，这篇文章主要介绍蓝桥杯练习——回路计数前言一、题目二、思路总结，现在分享给大家，希望可以做个参考。

文章目录

前言
一、题目
二、思路
- 1.状态
- 2.上一个状态以及转移方程
- 3.填表
- 4.代码：
总结

前言

又是自闭的一天

一、题目

问题描述
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。

答案：881012367360

二、思路

状压DP。设状态由长度为 $21$ 的 $01$ 串构成，左起第 $i$ 个数字表示 $i$ 是否走到过。如 $0110$ 表示 $1$ ， $4$ 没有走到过。

1.状态

设 $d p [i] [s]$ 表示，从1走到 $i$ ，状态为 $s$ 的方案数。

2.上一个状态以及转移方程

对于 $d p [i] [s]$ ，考虑从哪些状态可以转移到 $(i, s)$ ？
是从节点 $i$ 的一个邻接点转移过来的。设他的邻接点为 $t a r$ ，则有：
$dp[i][s]=dp[tar][s_{pre}]$ ，其中s_{pre}是s的上一个情况。
当然 $i$ 不止一个临界点，所以应该是所有邻接点的 $d p$ 值求和。
$dp[i][s]=Σdp[tar][s_{pre}]$

3.填表

方程得到之后，剩下的就是一个填表问题。（DFS递不动了，不知道为啥跑一百年跑不出来）
可以发现应该是从小到大 $(1000 . . . 0001111 . . . 111)$ 枚举状态( $s$ )，对于每个 $s$ 计算 $d p [i] [s]$ ， $i \in [1, 21]$ 。
从小推大。
可以自行填一个N=3的表理解一下，循环顺序不能错。

4.代码：

复制代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21;
int edge[27][27];
const int maxn=1<<22;
ll dp[27][maxn];//dp i j 1-->i 状态为j的方案书  
ll vis[maxn];
//第i位变1 S& 1<<21-i;
//第i位变0 S& ~[1<<21-i]; 
//all 1 (1<<N)-1
// 1000000000——1<<(N-1) 
//取第i位 s>>(N-tar)&1 
const ll las=(1<<N)-1; 
const ll fir=1<<(N-1);
ll all_1=(1<<N)-1;
int main(){
	int i,j;
	for(i=1;i<=N;i++){
		for(j=i+1;j<=N;j++){
			if(__gcd(i,j)==1){
				edge[i][j]=1;
				edge[j][i]=1;
			}
		}
	}
	dp[1][1<<(N-1)]=1;
	for(int state=fir;state<=las;state++){
		for(i=1;i<=N;i++)
		{
			//cout<<"枚举状态"<<state<<endl;
			//state要有i，即第i位为1
			int i_bit=state>>(N-i)&1;
			if(i_bit!=1){
				//cout<<"没有"<<i<<endl;
				continue; 
			}
			int tar;
			int pre_state=state;
			//pre_state第i位变0
			pre_state=pre_state&(~(1<<(N-i)));
			//cout<<"pre_state="<<pre_state<<endl;
			for(tar=1;tar<=N;tar++){
				//cout<<"tar="<<tar<<endl;
				int tar_bit_pre=pre_state>>(N-tar)&1;//取pre_state第tar位 
				if(edge[tar][i]==1&&tar_bit_pre==1){//是邻接点且pre_state第tar位为1 
					dp[i][state]+=dp[tar][pre_state];
					//cout<<"更新辣 add"<<dp[tar][pre_state]<<endl;
				}
				else if(edge[tar][i]==0){
					//cout<<"没有这个邻接点n";
				}
				else if(tar_bit_pre==0){
					//cout<<"pre_state中没有"<<tar<<endl;
				}
			}
		}
	}
	ll ans=0;
	for(i=1;i<=N;i++){
		ans+=dp[i][all_1];//ALL 1
	}
	cout<<ans<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21;
int edge[27][27];
const int maxn=1<<22;
ll dp[27][maxn];//dp i j 1-->i 状态为j的方案书  
ll vis[maxn];
//第i位变1 S& 1<<21-i;
//第i位变0 S& ~[1<<21-i]; 
//all 1 (1<<N)-1
// 1000000000——1<<(N-1) 
//取第i位 s>>(N-tar)&1 
const ll las=(1<<N)-1; 
const ll fir=1<<(N-1);
ll all_1=(1<<N)-1;
int main(){
	int i,j;
	for(i=1;i<=N;i++){
		for(j=i+1;j<=N;j++){
			if(__gcd(i,j)==1){
				edge[i][j]=1;
				edge[j][i]=1;
			}
		}
	}
	dp[1][1<<(N-1)]=1;
	for(int state=fir;state<=las;state++){
		for(i=1;i<=N;i++)
		{
			//cout<<"枚举状态"<<state<<endl;
			//state要有i，即第i位为1
			int i_bit=state>>(N-i)&1;
			if(i_bit!=1){
				//cout<<"没有"<<i<<endl;
				continue; 
			}
			int tar;
			int pre_state=state;
			//pre_state第i位变0
			pre_state=pre_state&(~(1<<(N-i)));
			//cout<<"pre_state="<<pre_state<<endl;
			for(tar=1;tar<=N;tar++){
				//cout<<"tar="<<tar<<endl;
				int tar_bit_pre=pre_state>>(N-tar)&1;//取pre_state第tar位 
				if(edge[tar][i]==1&&tar_bit_pre==1){//是邻接点且pre_state第tar位为1 
					dp[i][state]+=dp[tar][pre_state];
					//cout<<"更新辣 add"<<dp[tar][pre_state]<<endl;
				}
				else if(edge[tar][i]==0){
					//cout<<"没有这个邻接点n";
				}
				else if(tar_bit_pre==0){
					//cout<<"pre_state中没有"<<tar<<endl;
				}
			}
		}
	}
	ll ans=0;
	for(i=1;i<=N;i++){
		ans+=dp[i][all_1];//ALL 1
	}
	cout<<ans<<endl;
	return 0;
}