蓝桥杯——练习（3.5）_#include #include using names

蓝桥杯——练习（3.5）

基础练习 矩阵乘法

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T58

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
　　例如：
　　A =
　　1 2
　　3 4
　　A的2次幂
　　7 10
　　15 22

输入格式

第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
　　接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

输出格式

输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

样例输入

2 2
1 2
3 4

样例输出

7 10
15 22

解题思路

• 矩阵的乘法需要考虑是几次幂，如果是0次幂，则主对角线上的元素为1，如果为1次幂，那么输出的和原来的矩阵是相同的，当为多次幂的情况下，就要另外考虑这种情况。

• 本题目的代码将打印输出封装为Print函数，计算多次幂也封装成一个函数，通过调用函数可以实现最后的功能。

• 在求幂运算的函数中，用i来表示每次的幂运算，直到加到m，在这个循环里边，遍历数组，定义临时变量暂时存放结果，矩阵的乘法就是线性代数中的方式，行乘以列，最后加和。

代码

#include<iostream>
#include<cstring>
using namespace std;
int a[50][105];
int b[50][105];
int c[50][105];
void Print(int a[][105],int n)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
}
void matrix(int a[][105],int b[][105],int c[][105],int n,int m)
{
	for(int i=1;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<n;k++)
			{
				int tmp=0;
				for(int x=0;x<n;x++)
				{
					tmp+=a[j][x]*b[x][k];
					c[j][k]=tmp;
				}
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				b[i][j]=c[i][j];
			}
		}
	}
} 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			b[i][j]=a[i][j];
		}
	}
	if(m==0)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i==j)
					c[i][j]=1;
			}
		}
		Print(c,n);
	}
	else if(m==1)
	{
		Print(a,n);
	}
	else
	{
		matrix(a,b,c,n,m);
		Print(c,n);
	}
	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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

视频学习——深度优先搜索视频讲解

视频链接：https://www.bilibili.com/video/BV1jE411g76D?p=13

学习心得

1. 深度优先搜索（DFS）是用于遍历或搜索树或图数据结构的算法。该算法从根节点开始(在图的情况下选择一些任意节点作为根节点)，并在回溯之前尽可能沿着每个分支进行探索。

2. 可以使用深度优先搜索对图或树的顶点进行线性排序。有三种常见的方法:

   • 先置排序是顶点的列表，该列表按照深度优先搜索算法访问顶点的顺序进行排列。如前文所述，这是描述搜索过程的一种简洁自然的方式。表达式树的先置排序是波兰表示法中的表达式。

   • 后置排序是顶点的列表，该列表按照后被算法访问顺序进行排列。表达式树的后序是逆波兰表示法中表达式的反向。

   • 反向后置与后置排序相反，即顶点的列表与它们上次访问的顺序相反。反向后置与先置排序不同。

题目练习 算法提高 8皇后·改

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T374

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。

输入格式

一个8*8的棋盘。

输出格式

所能得到的最大数字和

样例输入

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
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

样例输出

260

数据规模和约定

棋盘上的数字范围0~99

代码

#include<iostream>
using namespace std;
const int Max=8;
int Mgraph[Max][Max];
int max1=-32767;
int c[Max];
void dfs(int cur,int sum)
{
	if(cur==Max)
	{
		if(sum>max1)
		{
			max1=sum;
		}
		return ;
	}
	for(int i=0;i<Max;i++)
	{
		c[cur]=i;
		int flag=1;
		for(int j=0;j<cur;j++)
		{
			if(c[cur]==c[j]||cur-j==c[cur]-c[j]||cur-j==c[j]-c[cur])
			{
				flag=0;
				break;
			}
		}
		if(flag)dfs(cur+1,sum+Mgraph[cur][i]);
	}
}
int main()
{
	for(int i=0;i<Max;i++)
	{
		for(int j=0;j<Max;j++)
		{
			cin>>Mgraph[i][j];
		}
	}
	dfs(0,0);
	cout<<max1<<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