immix's blog

总结一下图论里的最短路。 Dijkstra 算法 Dijkstra 算法可用于非负权值的图，可以表示为如下流程。 将源点的距离设为 0，其他点的距离设为无穷大。 从图中找出距离最小且未标记的点 uuu，并标记点 uuu。松弛所有与 uuu 相邻的节点。（松弛：尝试将 s→vs\rightarrow vs→v 的路径用 s→u→vs\rightarrow u \rightarrow vs→u→v 的距离更新，即 dis[v]=min(dis[v],dis[u]+w[u][v])） 重复第二步，直到所有节点都被标记。 如果需要输出路径，可以在松弛成功时记录每个节点的前驱。 根据在第二步找出距离最小的点的处理方法不同，Dijkstra 算法有不同的复杂度。 暴力实现 依次遍历所有 nnn 个节点，找出最小权值。这样第二步的复杂度为 O(n)O(n)O(n)，总共执行 nnn 次，总复杂度为 O(n2)O(n^2)O(n2) 123456789101112131415161718192021222324252627282930313233343536373839const int N = ...

经典的区间三个贪心问题。再总结一下，以作复习。 选择不重叠区间 有 nnn 个区间 [li,ri][l_i,r_i][li​,ri​]，选择尽量多的区间，使得区间之间不重叠（端点可以重叠）。 将右端点从小到大排序（左端点可以随便排序），然后先选择右端点比较小的（不与之前选过的重叠）。 这样的贪心策略是正确的。 考虑如下一个例子。先选择右端点最小的 [1,4][1,4][1,4]，然后右端点次大的 [2,5],[3,5][2,5],[3,5][2,5],[3,5] 重叠无法选择，然后是右端点最大的 [4,6][4,6][4,6] 可以选择。即最多可以选出两个区间。 假设一开始没有选择右端点最小的，选择了 [2,5][2,5][2,5]， 那么 [1,2][1,2][1,2] 的部分就被浪费了，还额外占用了 [4,5][4,5][4,5] 的空间，所以一定从右端点小的开始选更划算。 区间选点问题 有 nnn 个区间 [li,ri][l_i,r_i][li​,ri​]，选择尽可能少的点，使得每一个区间内都有点。 事实上，这个问题的答案和选择不重叠区间的答案是一样的。 为什么两个问题的答案相 ...

二分图最大匹配 给定一张二分图，有 nnn 个点，mmm 条边。求最大匹配。 可以使用匈牙利算法求解，复杂度 O(nm)O(nm)O(nm)。 如果使用 dinic 算法，可以做到复杂度为 O(nm)O(n\sqrt{m})O(nm​) dinic 算法详见 网络流初步-最大流算法。 具体来说，建立超级源点和超级汇点，然后建容量为 1 的边，跑最大流即为最大匹配。 匈牙利算法的本质就是找增广路，基于贪心思想。我们来看一个例子。 首先考虑给节点 1 寻找匹配。发现可以匹配右边的节点 1，则成功匹配。 然后考虑给节点 2 寻找匹配。发现能匹配的唯一一个节点 1 已经被占用，尝试让左边的节点 1 换一个匹配，即等价于找一个增广路。 这样就找到了这张图的最大匹配（3）。我们接下来考虑写一个递归函数实现这种协商找增广路的算法。 匈牙利算法 我们定义一个递归函数 bool dfs(int u)，代表为节点 u 寻找匹配。 数组 int match[v] 表示右部图中节点 v 已经匹配上的左部图节点。 数组 bool used[v] 表示右部图中节点 v 是否已经在本轮中访问过。 则可以 ...

导言 命令行是一种强大、快捷的工具。有时候可以比 GUI 操作更加便捷。其另一大优点是可以极其容易的通过 ssh 控制其他机器。 初识命令行 在 Windows 下，常见 shell 有命令提示符(cmd)，PowerShell 两种。我们主要阐述 cmd。在 linux 平台上你还会见到 bash。bash 和 cmd 的命令是有一部分重合的。 打开 cmd 的一种方式是按 Windows 键，然后搜索 cmd；另一种方式是 Win+R，再输入 cmd 运行。 打开 cmd 后，你会见到这样的界面（因为我安装了 Windows Terminal，与你的电脑外观略有不同，但是内容是一样的）。 在提示符（>）后输入命令，然后按回车就可以看到命令的结果。你学过了 ping 和 ipconfig 命令，但让我们从头开始，学习最基本，使用频率最高的命令。 基本命令 基本命令只有两个（好耶），一个切换目录，一个查看当前目录内容。 cd cd = Chang Directory = 改变目录 用来改变当前的工作目录。在 cmd 中，使用 Tab 可以补全路径。使用 ↑ 键可以找到历史命令 ...

突发奇想，研究一下 ACG 歌词的用词特点。 获取歌词 找到了一个共有 4572 首歌（2023-5-10）的歌单，https://music.163.com/#/playlist?id=66652611 ，尝试获取其中所有歌的歌曲 id。 首先尝试查找有没有合适的 API，失败，尝试从歌单页面入手。 可以看到，网易云网页查看别人创建的歌单只可以看到前 20 首歌曲。但是如果我们将歌单复制到自己的自建歌单，则可以显示 1000 首。理论上可以创建 5 个歌单，然后进行获取。 分析网页结构，可以发现每个歌曲都是一个 a 标签，里面的 href 就是我们要的内容。 尝试在控制台编写一个 JS 来获取所有个歌曲 id。 1document.querySelectorAll("div.f-cb span.txt > a") 尝试使用这个选择器，发现能够成功获取所有 a 标签，接下来就是获取所有 a 标签的 href 属性。 12let result = ""document.querySelectorAll("div.f-cb spa ...

引入 洛谷P6175 无向图的最小环问题 给定一张带权无向图，求图中至少包含 333 个点的环，环上节点不重复，并且环上所有边权值和最小。 解法 我们考虑对 Floyd 算法进行修改，找出最小环。 设最小环由节点 V1−V2−⋯−VnV_1 - V_2 - \dots - V_nV1​−V2​−⋯−Vn​ 组成。 其中编号最大的节点为 VmV_mVm​ 与其相连的节点为 VpV_pVp​，VqV_qVq​。 则最小环可以表示为 Vp−{Vp,Vq之间不包含Vm的最短路}−Vq−VmV_p - \{V_p,V_q\text{之间不包含}V_m\text{的最短路}\} - V_q - V_mVp​−{Vp​,Vq​之间不包含Vm​的最短路}−Vq​−Vm​。 如下图： 这是可以证明的： 假设不是最短路：则最短路权值一定更小； 假设包含了 VmV_mVm​：则出现了重复的节点。 在 Floyd 算法中，我们知道，枚举中转点到 k 时，此时数组内下标小于 k 的值保存的是 1~(k-1) 内部之间的最短路。 因此在 Floyd 算法中枚举 i，j 的循环前面再添加一个循环即可。G[i] ...

前言 什么是类？ 类（Class）：可以片面的理解为一类相似事物的抽象。 以圆为例，圆具有半径这样一个相似的属性，并且都可以执行面积、周长等运算。 为什么用类？ 为了是代码更加抽象，封装。事实上，我们以前写的每个 python 代码里都创建了各种各样的类。 一些例子比如 DataFrame 类。 你可能会用 read_csv 创建一个 DataFrame 类，可能也会用下标运算符，来获取它的某一列，也可能会用它的 drop_duplicates 方法。事实上，你并不关心 DataFrame 是怎么把数据排在一起的，你也不关心为什么 drop_duplicates 就能把所有重复的去除，但是，通过这一个抽象的类，你可以方便的调用它的功能。 DataFrame类，将整个表的数据，仅仅用一个变量，就全部包含起来，就像是封装在了一个小小的纸板箱中📦。 需要注意的是，pandas 库并不是魔法，而是正常的 python 语法。一切 pandas 库的功能都是我们也可以实现出一模一样的。 比如说，为什么 df[(df['a']>5) & (df['b']<8)] 中用的是 & ...

POWER 多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。 多瑞卡每晚到早晨5点钟都在晚会上，然后他开始关灯。开始时，他站在某一盏路灯的旁边。 每盏灯都有一个给定功率的电灯泡，因为多端卡有着自觉的节能意识，他希望在耗能总数最少的情况下将所有的灯关掉。 多端卡因为太累了，所以只能以 1m/s的速度行走。关灯不需要花费额外的时间，因为当他通过时就能将灯关掉。 编写程序，计算在给定路灯设置，灯泡功率以及多端卡的起始位置的情况下关掉所有的灯需耗费的最小能量。 输入 输入文件的第一行包含一个整数 NNN，2≤N≤10002≤N≤10002≤N≤1000，表示该村庄路灯的数量。 第二行包含一个整数 VVV，1≤V≤N1≤V≤N1≤V≤N，表示多瑞卡开始关灯的路灯号码。 接下来的 NNN 行中，每行包含两个用空格隔开的整数 DDD和 WWW，用来描述每盏灯的参数，其中 0≤D≤10000≤D≤10000≤D≤1000，0≤W≤10000≤W≤10000≤W≤1000。DDD 表示该路灯与村庄开始处的距离(用米为单位来表示)，WWW 表示灯 ...

胖男孩 麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。 当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。 编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。 输入 输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。 输出 输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。 输入样例 cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukd 输出样例 ...

顺序对齐 考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是 AADDEFGGHC 和 ADCDEGH。 AAD_DEFGGHC ADCDE__GH_ 每一个数值匹配的位置值 2 分，一段连续的空格值 -1 分。所以总分是匹配点的 2 倍减去连续空格的段数，在上述给定的例子中，6 个位置(A, D, D, E, G, H)匹配，三段空格，所以得分 2×6+(-1)×3=9 ，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。 请你写个程序找出最佳右对齐方案。 输入 输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。 输出 一行，为最佳对齐的得分。 样例 输入样例 AADDEFGGHC ADCDEGH 输出样例 9 解法 然后从左边开始区间 DP，设 fi,jf_{i,j}fi,j​ 为第一个字符串左边 iii 位，第二个字符串左边 jjj 位的最大值。可以写出方程： fi,j=max⁡{fi−1,j−1+2(s1[i]=s2[j])fi−1,j−1(s1[i]≠s2[j])fk,j−1(1≤k< ...