【思特奇杯·云上蓝桥-算法集训营】第2周

2022/1/16 20:06:43

本文主要是介绍【思特奇杯·云上蓝桥-算法集训营】第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周的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程