离散数学题目与解析
离散数学题目图论第七章题目
7.1 图的基本概念 ，顶点集，边集，图的阶，零图判断题 ：存在1阶零图。 ( )
答案：正确
解析：在图 G 中，若E(G)=\emptyset ，则称G为零图，此时，又若 \mid V(G)\mid=n，则称 G 为 n 阶零图，记为 N_n ，特别是称 N_1 为平凡图。
7.1 图的基本概念 ，顶点集，边集，图的阶，零图判断题 ：存在1阶空图。 ( )
答案：错误
解析：顶点集为空集的图为空图。
7.1 图的基本概念 ，领域，闭邻域选择题：
$V_2$的闭邻域是：( )
$A:V_3、V_4、V_0 $ $B:V_3、V_4、V_0、V_2 $
答案：B
解析：闭邻域的定义
7.1 图的基本概念，度数，最大最小度判断题 ：在有向完全图中，所有节点入度的平方和等于所有节点出度的平方和。（ ）
答案：正确
解析：设有向完全图具有$n$个节点，对于任意结点 $V_i$ 均有 \mathrm{deg}^{+}\left(v_{i}\right)+\mathrm{deg} ...
八数码【bfs搜索，A*】
AcWing845 八数码1.0题目描述在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入格式输入初始状态，一行九个数字，空格用0表示
输出格式只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入283104765
输出4
思路容易想到用bfs来搜索，那么怎么记录下每一种状态是否被搜索到了呢？思考1：每一个状态用一个字符串存储，要9个字节，需要的空间太大了。思考2：每一个状态用一个int来存储，因为$87654321<2^{31}$，但是还是太大了。思考3：注意到总共的状态数目为9！个，可以用康托展开来得到每一个状态对应的hash值，这样就能过了。思考4：其实，stl中的unordered_map（哈希表实现）同样可以完成这个任务，更加的方便，所花费的空间和方案3差不多 ...
常见的五种最短路算法
常见的五种最短路算法摘要本文主要介绍关于图的最短路的五种常用算法和其应用。朴素Dijkstra， 堆优化Dijkstra，Bellman-Ford，SPFA， Floyd。这几种算法有各自的优势和劣势，适用于不同的场景。文章的难度不大，适合算法初学者学习。
五种最短路算法之间的区别注：n表示图中点的数目，m表示图中边的数目。
朴素Dijkstra算法介绍
DijKstra的核心思想是贪心。
先将起点距离自己的距离设为0，其余设为正无穷。
一共循环n次，每一次循环，找到目前没有被找到过并且距离起点最近的点。此时，被找到的这个点所记录的距离，正是这个点到起点的最短距离。然后再用这个点来更新与它有连接的其它点的距离。
每一次循环，我们都能找到一个满足条件的点，n次循环过后，我们就可以得到每一个点距离起点的最短距离了。
时间复杂度为o(n^2)，n 表示点数，m表示边数，可以用邻接矩阵存图。
Dijkstra无法处理有负权边的情况
核心代码12345678910111213141516171819202122232425262728int g[N][N]; // 用邻接矩阵存图，存储每条边 ...
食物链 【带权并查集】
洛谷P2024 POJ 1182 食物链 【带权并查集】题目描述动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。
现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是 1 X Y，表示 X 和 Y 是同类。第二种说法是2 X Y，表示 X 吃 Y 。此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
当前的话与前面的某些真的话冲突，就是假话当前的话中 X 或 Y 比 N 大，就是假话当前的话表示 X 吃 X，就是假话你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式第一行两个整数，N，K，表示有 N 个动物，K 句话。
第二行开始每行一句话（按照题目要求，见样例）
输出格式一行，一个整数，表示假话的总数。
输入100 71 101 12 1 22 2 32 3 31 1 32 3 ...
最大异或对
143. 最大异或对在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式输出一个整数表示答案。
数据范围1≤N≤10^5,0≤Ai<2^31
输入样例：31 2 3
输出样例：3
这道题如果没有标签的提示的话，很难想到可以用字典树来完成，不过Ai的数据范围提到了2^31,也不难想到字典树还可以存储二进制数字。思路:将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异.c++代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<vector>#include<deque>#include<queue>#include <unordered_map>using namespace std;const int N=100 ...
最新文章
