本文主要是介绍【思特奇杯·云上蓝桥-算法集训营】第2周，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题描述：1. 带分数

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。

解决方案：

#include<iostream>
#include<string.h>
using namespace std;
int a[10]={0};
bool Division(int m)					//分割数字
{
	int t;	
	while(m)
	{
		t=m%10;
		if(t==0)						//为零不符合题意 
			return 0;
		a[t]++;
		m=m/10; 
	}	
	return 1;
}
int main()
{						
	int n,ans=0;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=4938;j++)
		{
			memset(a,0,sizeof(a));  		//每次使数组a的各位为零 
			int k=(n-i)*j; 
			if(Division(i)&&Division(j)&&Division(k))
			{
				int flag=1;			
				for(int x=1;x<10;x++)	//判断数字是否重复
				{
					if(a[x]!=1)
					{
						flag=0;
						break;
					 } 
				}
				if(flag==1) 
					ans++;
			}
		}
	}
	cout<<ans;
	return 0;
} 

问题描述：2. 李白打酒

话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为 a，遇花记为 b。则：
babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？

请你计算出所有可能方案的个数（包含题目给出的）。

解决方案：14

#include <iostream>
using namespace std;
int ans;
void f(int hua,int dian,int jiu)
{
  	if(hua==1&&dian==0&&jiu==1)
  		ans++;
	if(hua>1)
		f(hua-1,dian,jiu-1);
	if(dian>0)
		f(hua,dian-1,jiu*2);
}
int main()
{
	f(10,5,2);
	cout<<ans<<endl;
	return 0;
}

 问题描述：3. 第 39 级台阶

小明刚刚看完电影《第 39 级台阶》，离开电影院的时候，他数了数礼堂前的
台阶数，恰好是 39 级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚，然后左右交替，最后一
步是迈右脚，也就是说一共要走偶数步。那么，上完 39 级台阶，有多少种不同的上法呢？

解决方案：51167078

#include <iostream>
using namespace std;
int ans=0;
void solve(int n,int step)
{
	if(n==0 && step % 2==0)
		ans++;	
	if(n<0)
		return;
	solve(n-1,step+1);
	solve(n-2,step+1);		
}
int main()
{
	solve(39,0);
	cout<<ans<<endl;
	return 0;
}

 问题描述：4. 穿越雷区

已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号
分别表示正负能量辐射区。
例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。
数据格式要求：
输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是 n行，每行有n个数据，可能是 A，B，+，-中的某一个，中间用空格分开。
A，B 都只出现一次。
要求输出一个整数，表示坦克从 A 区到 B 区的最少移动步数。如果没有方案，则输出-1
例如：用户输入：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
则程序应该输出：
10

解决方案：

#include<iostream>
#include<queue>
using namespace std;
const int M = 100,INF = 0x3f3f3f3f;
const int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int n,endx,endy;
char ch[M+5][M+5];
int a[M+5][M+5];
struct Coordinate
{
	int x,y;
	Coordinate(int x,int y):x(x),y(y){}
};
queue<Coordinate>q;
void bfs()
{
	Coordinate t = q.front();
	q.pop();
	//cout<<t.x<<' '<<t.y<<endl;
	for(int i=0;i<4;i++)
	{
		int tx = t.x + move[i][0];
		int ty = t.y + move[i][1];
		if(tx<1||ty<1||tx>n||ty>n||a[tx][ty]||ch[tx][ty]==ch[t.x][t.y])
			continue;
		a[tx][ty]=a[t.x][t.y]+1;
		if(tx==endx&&ty==endy)
		{
			while(!q.empty())
				q.pop();
			return;
		}
		q.push(Coordinate(tx,ty));
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>ch[i][j];
			if(ch[i][j]=='A')
			{
				q.push(Coordinate(i,j));
				a[i][j]=0;
			}
			if(ch[i][j]=='B')
			{
				endx=i;
				endy=j;
			}	
		}
	while(!q.empty())
		bfs();
	cout << a[endx][endy];
	return 0;
}

 问题描述：5. 迷宫

下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它
的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按
DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向
下、向上、向左、向右走。对于下面这个更复杂的迷宫（30行50列），请找
出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字
典序最小的一个作为答案。 请注意在字典序中 D<L<R<U。

解决方案：

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
const string S[4] = {"D","L","R","U"};
bool a[31][51];
struct Coordinate
{
	int x,y;
	string s;
	Coordinate(int x,int y,string s):x(x),y(y),s(s){}
};
queue<Coordinate> q;
void bfs()
{
	Coordinate t = q.front();
	q.pop();
	for(int i=0;i<4;i++)
	{
		int tx = t.x + move[i][0];
		int ty = t.y + move[i][1];
		if(tx<1||tx>30||ty<1||ty>50||a[tx][ty])
			continue;
		string ts = t.s + S[i];
		if(tx==30&&ty==50)
		{
			while(!q.empty())
				q.pop();
			cout<<ts;
			return;
		}
		a[tx][ty]=true;
		q.push(Coordinate(tx,ty,ts));
	}
}
int main()
{
	for(int i=1;i<=30;i++)
		for(int j=1;j<=50;j++)
		{
			char ch;
			cin>>ch;
			a[i][j] = (ch=='1');
		}
	q.push(Coordinate(1,1,""));
	while(!q.empty())
		bfs();
	return 0;
}

 问题描述：6.跳马

中国象棋半张棋盘如图1所示。马自左下角(0,0)向右上角（m，n）跳。规定只能往右跳，不准往左跳。比如图1中所示为一种跳行路线，并将路径总数打印出来。

输入格式：

只有一行：两个数n，m

输出格式：

只有一个数：总方案数total。

解决方案：

#include <iostream>
using namespace std; 
int n,m,ans;
const int move[4][2]={{1,2},{2,1},{2,-1},{1,-2}};
void dfs(int x,int y)
{
	if(x==m&&y==n)
		ans++;
	for (int i = 0 ; i< 4 ;i++)
	{
		int tx = x + move[i][0];
		int ty = y + move[i][1];
		if(tx<0||tx>m||ty<0||ty>n)
			continue;
		else
			dfs(tx,ty);
	}
}
int main()
{
	cin>>m>>n;
	dfs(0,0);
	cout<<ans<<endl;	
	return 0 ;
}

 问题描述：7.路径之谜

小明冒充X星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n x n 个方格。【如图1.png】所示。

按习俗，骑士要从西北角走到东南角。

可以横向或纵向移动，但不能斜着走，也不能跳跃。

每走到一个新方格，就要向正北方和正西方各射一箭。

（城堡的西墙和北墙内各有 n 个靶子）

同一个方格只允许经过一次。但不必做完所有的方格。

如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？

有时是可以的，比如图1.png中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入：

第一行一个整数N(0<N<20)，表示地面有 N x N 个方格

第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出：

一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....

比如，图1.png中的方块编号为：

0  1  2  3

4  5  6  7

8  9  10 11

12 13 14 15

示例：

用户输入：

4

2 4 3 4

4 3 3 3

程序应该输出：

0 4 5 1 2 3 7 11 10 9 13 14 15

解决方案：

#include<iostream>
using namespace std;
const int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,p=0,a[21],b[21],step[401];
bool st[21][21];
bool dfs(int x,int y)
{
	if(!a[y]||!b[x])
		return false;
	a[y]--,b[x]--;
	if(x==n&&y==n)
	{
		bool st = true;
		for(int i=1;i<=n;i++)
			if(a[i]||b[i])
				st = false;
		if(st)
		{
			step[p++]=(x-1)*n+y-1;
			return true;
		}
	}
	for(int i=0;i<4;i++)
	{
		int tx=x+move[i][0];
		int ty=y+move[i][1];
		if(tx<1||tx>n||ty<1||ty>n)
			continue;
		if(dfs(tx,ty))
		{
			step[p++]=(x-1)*n+y-1;
			return true;
		}
	}
	a[y]++,b[x]++;
	return false;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int j=1;j<=n;j++)
		cin>>b[j];
	dfs(1,1);
	for(int i=p-1;i>=0;i--)
		cout<<step[i]<<' ';
	return 0;
}

问题描述：8.未名湖边的烦恼

       每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。

　　每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）

输入格式 ：两个整数，表示m和n

输出格式 ：一个整数，表示队伍的排法的方案数。

样例输入 ：3 2

样例输出 ：5

数据规模和约定 ：m,n∈［0,18］

解决方案：

#include<iostream>
using namespace std;
 
int solve(int x,int y)
{
	if(x<y) 
		return 0;
	if(y==0) 
		return 1;
    return solve(x-1,y)+solve(x,y-1);
}
int main()
{
	int m,n;
	cin>>m>>n;
	int ans=solve(m,n);
	cout<<ans<<endl;
}

 问题描述：9.大臣的旅费

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数

城市从1开始依次编号，1号城市为首都。

接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）

每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出一个整数，表示大臣J最多花费的路费是多少。

样例输入1

5
1 2 2
1 3 1
2 4 5
2 5 4

样例输出1

135

解决方案：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int MAX=10000;		//最多城市数
int maxFarNode;				//maxFarNode从指定节点出发所能到的最远节点
int maxLen=-1;				//maxLen从指定节点出发所能到的最远距离
bool st[MAX];				//标记某个点是否被访问过 
struct Node
{							// 存放一个点的子节点及边的权值 
	int child,length;
	Node(int a,int b):child(a),length(b){};
};
vector<Node> v[MAX];		//链式存储，邻接表 
void dfs(int node,int nowLen)
{
	if(st[node]) 
		return;
	st[node]=true;
	for(int i=0;i<v[node].size();i++)
	{
		int child =v[node][i].child;  		
		int length=v[node][i].length; 		
		if(st[child]) 
			continue;      				 
		if(nowLen+length>maxLen)
		{
			maxLen=nowLen+length;			 
			maxFarNode=child;				
		}
		dfs(child,nowLen+length); 
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y,len;
		cin>>x>>y>>len;
		v[x].push_back(Node(y,len));
		v[y].push_back(Node(x,len));
	}
	dfs(1,0);
	memset(st,false,sizeof(st));
	maxLen=-1;
	dfs(maxFarNode,0);
	cout<<(maxLen*10+maxLen*(1+maxLen)/2)<<endl;
	return 0;
}

 问题描述：10.2n 皇后问题

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后

和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两

个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

Input

输入的第一行为一个整数n，表示棋盘的大小。

接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，

如果一个整数为0，表示对应的位置不可以放皇后。

Output

输出一个整数，表示总共有多少种放法。

Sample Input

No.1

4

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

No.2

4

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1

Sample Output

No.1

2

No.2

0

解决方案：

#include<iostream>
#include<stdlib.h>
using namespace std;
const int maxn=10;    
int n,ans=0;  
int posb[maxn]={0};  			//黑皇后 
int posw[maxn]={0};  			//白皇后    
int map[maxn][maxn];
bool checkw(int cur) 		
{  
    for(int i=1;i<cur;i++)  
        if(posw[i]==posw[cur]||abs(i-cur)==abs(posw[i]-posw[cur])) 
            return false;  
    return true;  
}    
bool checkb(int cur)  		
{  
    for(int i=1;i<cur;i++)  
        if(posb[i]==posb[cur]||abs(i-cur)==abs(posb[i]-posb[cur])) 
            return false;  
    return true;  
}
void dfs_white(int cur)  
{  
    if(cur==n+1)  				//白皇后也全部放完，次数+1  
        ans++;  
    for(int i=1;i<=n;i++)  
    {  
        if(posb[cur]==i) 		//表示第cur列的第i行位置已经被黑皇后占用，
            continue;        	//结束当前循环，i+1
        if(map[cur][i]==0) 		//再判断前提条件是否成立
            continue;  
        posw[cur]=i;    		//尝试把第cur列的白皇后放在第i行上
        if(checkw(cur))   		//判断能否放置白皇后
            dfs_white(cur+1);  	//递归
    }  
}  
void dfs_black(int cur)  
{  
    if(cur==n+1)  			//当黑皇后处理完时，再处理白皇后
        dfs_white(1);    
    for(int i=1;i<=n;i++)  
    {  
       	if(map[cur][i]==0) //如果第cur列第i行满足放皇后的前提条件即 mp[cur][i] == 1
            continue;  		//如果不满足，则结束当前循环，进行下一次循环即i+1。
        posb[cur] = i;     	//就尝试把第cur列的黑皇后放在第i行上
        if(checkb(cur))   	//然后判断该尝试是否成立，如成立，则进行递归，如不成立，则尝试把当前列的黑皇后放在下一行(i+1行)上。
            dfs_black(cur+1);  //递归
    }  
}  
int main()  
{     
   	cin>>n;
   	for(int i=1;i<=n;i++)   //定义棋盘
       	for(int j=1;j<=n;j++)  
           cin>>map[i][j];    
   	dfs_black(1);    		//先把黑皇后放在第一列
   	cout<<ans<<endl; 
    return 0;  
}

这篇关于【思特奇杯·云上蓝桥-算法集训营】第2周的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！