小猫咪吃python

# 前置文章 Spfa 简单应用 Bellman-Ford 简单应用 # 图论之求负环问题模型 给出一张有向图或者无向图，其中每条边都有权值（距离），权值有正有负，如果图中存在一个环，这个环的所有边权值之和是负数，则称之为 “负环”。 # 负环对算法的影响 根据我们的更新条件，当存在一条边 {a, b, w} 满足 dist[x] > dist[b] + w 则可以进行更新，但是如果有负环，那么该更新过程永远都不会结束。 正环图中的更新 在一个正环图中，我们以 点 1 为源点，求 点 1 到 点 2...

# 前置文章 Floyd 算法简单入门 # AcWing 344. 观光之旅 给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。 该问题称为无向图的最小环问题。 你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。 输入格式 第一行包含两个整数 N 和 M，表示无向图有 N 个点，M 条边。 接下来 M 行，每行包含三个整数 u，v，l，表示点 u 和点 v 之间有一条边，边长为 l。 输出格式 输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No...

偶然间，在知乎上突然看到一本书，光看介绍就很吸引人，果断入手，最近终于全看完了。 书名叫做《大国重器》，顾名思义，书的内容讲述了近十年来我国最尖端科技的革新，总共有五十项，每一项都是名副其实的...

# 前置文章 Dijkstra 求最短路 bellman-ford 求限制边数的最短路 spfa 求有负权边的最短路 Floyd 求多源汇最短路 # 最短路问题模型 给出一张无向图，有 n 个点和 m 条边，求从 1 号点到 n 号点的最短距离。 # 存图的方法 一般我们使用两种方式存图： 邻接矩阵：使用一个二维数组 w[i][j] 表示从点 i 到点 j 的距离。 邻接表：常规做法是使用数组模拟邻接表，具体操作如下：// 其中 N 表示点的最大数量，M 表示边的最大数量int h[N], w[M], e[M], ne[M], idx;// 存储点 a 到点 b 且距离是 w...

书接上回 # AcWing 165. 小猫爬山 翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。 经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕 >_<）。 翰翰和达达只好花钱让它们坐索道下山。 索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。 当然，每辆缆车上的小猫的重量之和不能超过 W。 每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？ 输入格式 第 1 行：包含两个用空格隔开的整数，N 和 W。 第 2..N+1...

# 前置知识 可以通过这篇回溯攻略，先了解一下深度优先搜索的决策树以及工作流程。 可以通过这篇文章了解矩阵中坐标向其他方向扩散的实现方式。 # DFS 与 BFS 他们是两种不同的搜索方式，非常相似，以至于很多问题都是用哪种都可以。但是因为搜索顺序的不同，又有些许不同的点： 空间占用 BFS 较多，DFS 较少。BFS 是按照层搜索，一般的实现方式是使用队列，极端情况下队列中会存放非常多的数据，但是 DFS 一般使用递归实现，因此相较于 BFS 使用的空间就少很多了。 DFS 可能出现 “爆栈” 的情况，也就是系统栈不够用。DFS...

# 前置知识 看完必会的搜索之超经典 flood fill 问题攻略，看完必会的 BFS 解决最短路问题攻略。本文所讲的题型与前置文章属于类似问题，因此需要先熟悉前置文章中数组模拟队列、由坐标向其他方向扩散等基础操作，重复内容不会再讲。 # 用 BFS 解决最小步数问题 在前文中的最短路模型中，目的是求一个点到另一个点的最短距离。而在本文的最小步数模型中，目的是求一个状态到另外一个状态的最小步数。 我们依旧是从一个标准的模板题作为切入点。 # AcWing 1107. 魔板 Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本 —— 魔板。 这是一张有 8...

# 前置知识 看完必会的搜索之超经典 flood fill 问题攻略。本文所讲的题型与前置文章属于类似问题，因此需要先熟悉前置文章中数组模拟队列、由坐标向其他方向扩散等基础操作，重复内容不会再讲。 # 用 BFS 解决最短路问题 最短路问题是很常见的问题，而可以用 BFS 解决的最短路问题是其中的一个小小的子集。可以用 BFS 解决的最短路问题必须具备一个条件：所有边的权重全部相等。 从该类型问题的基础模板来研究该问题。 # AcWing 844. 走迷宫 给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1...

这是知乎出品的一小时读书的科普类书籍，全名叫做《猫、爱因斯坦和密码学》。本书字数很少，的确可以在一小时内读完，并且内容生动有趣，循序渐进，一环接一环，将晦涩难懂的物理知识生动的展现出来。 书的内容由经典的双缝干涉实验开始讲起，为了解释实验的内容，历史上的伟大科学家们悉数登场：玻尔、薛定谔、爱因斯坦等等。这个过程中作者把他们研究量子力学的过程依次的展开，让读者可以慢慢的了解历史的演进过程。 而后又讲述了一下密码学的历史和演进过程，最后把两段结合起来科普了未来量子领域可能在密码学中的应用。 看完这本书，我大感震撼，并且对于白嫖行为深感惭愧，于是补了一本实体书（好贵呀）。 为什么会感到震撼呢？这本书...

# 前置知识 # 数组模拟队列 一般我们认为数组模拟队列是要比使用标准库的队列更快的。模拟队列中最常用的三个操作如下： 初始化操作： 伪代码q[N]; // 初始化一个数组int hh = 0, tt = -1; // 初始化头尾指针 取出队列头 / 尾元素。 伪代码q[hh] // 队头 q.front ()hh ++ // 弹出队头 q.pop ()组合起来就是：q[hh ++ ]同理，取出队尾： q[tt -- ] 增加一个元素 伪代码q[++ tt ] = item // 在末尾添加一个元素 item# 四连通的搜索方式 四连通，顾名思义就是矩阵中的一个点可以和周围 上下左右...