我是靠谱客的博主 风趣黑夜,最近开发中收集的这篇文章主要介绍蓝桥杯练习——回路计数前言一、题目二、思路总结,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

文章目录

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


前言


又是自闭的一天

一、题目

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

答案:881012367360

二、思路

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

1.状态

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

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

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

3.填表

方程得到之后,剩下的就是一个填表问题。(DFS递不动了,不知道为啥跑一百年跑不出来)
可以发现应该是从小到大 ( 1000...000   1111...111 ) (1000...000~1111...111) (1000...000 1111...111)枚举状态( s s s),对于每个 s s s计算 d p [ i ] [ s ] dp[i][s] dp[i][s] i ∈ [ 1 , 21 ] i∈[1,21] i[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;
}

总结

提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

最后

以上就是风趣黑夜为你收集整理的蓝桥杯练习——回路计数前言一、题目二、思路总结的全部内容,希望文章能够帮你解决蓝桥杯练习——回路计数前言一、题目二、思路总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(58)

评论列表共有 0 条评论

立即
投稿
返回
顶部