OI 代码调试 - GDB 的使用
打算写一点不涉及算法的指南。这是第二篇。讲讲怎么使用 GDB 来调试代码。要调试代码,最简单的方式就是直接打印出来看,但有时候不想打印,这时候就需要依靠一些外部工具来进行调试了。
GDB 全名为 GNU symbolic debugger,是 GNU 开发的一个支持调试多种语言的调试器。
打开 GDB
GDB 是一个命令行的调试器,意味着其没有任何 UI,全部需要通过输入指令来完成调试操作。你应该习惯这种操作,并也习惯用命令行来编译 C++ 程序,而不是使用 IDE 自带的编译。
linux
linux 下你的发行版在安装 gcc 的时候就会附带 gdb,在终端输入 gdb 即可。
Windows
如果你使用的是 MinGW,那么在 bin 文件夹下就有一个 gdb.exe,将这个文件夹加入 PATH 即可(如果你之前就可以用 g++ 来命令行编译程序,那么你应该已经加入了)。如果你使用的是其他编译器,请自行查询。
加入 PATH 之后就可以在命令行直接输入 gdb 来调出程序了。
基础使用
首先,编译你的代码。在编译时要加入 -g 选项,将调试信息也编译进可执行文件中。注意 - ...
素数与筛法
埃氏筛
筛到一个质数后,把它所有的倍数全部删去。非常简单易懂。
复杂度 O(nloglogn)O(n \log \log n)O(nloglogn)。 (证明略去)
123456789101112131415bool prime[N];void solve(int n){ for(int i=2;i<=n;i++)prime[i]=1; for(int i=2;i<=n;i++){ if(!prime[n])continue; // 优化:从质数 i 的 i 倍开始筛 // 因为 i 的 2~(i-1) 倍一定有一个更小的质数因子 // 所以已经被筛掉了 for(int j=i*i;j<=n;j+=i){ prime[j]=0; } }}
线性筛(欧氏筛)
埃氏筛的效率还是不够高,我们尝试构建一个复杂度为 O(n)O(n)O(n) 的筛法。
线性筛的思路是对于一个数(不一定是质数), ...
NOI Linux 2.0 使用指南
正式比赛的理论环境是 NOI Linux 2.0(虽然上海市目前还是 Windows+Linux 双系统,共享分区,最后用极域上传文件)。总结一下 NOI Linux 中的一些操作,也是为下半年做个准备。
安装
NOI Linux 2.0 的镜像可以从 NOI 官网下载。(https://www.noi.cn/gynoi/jsgz/2021-07-16/732450.shtml)
可以采用 Virtual Box 或者 VMWare 来安装虚拟机(不建议安装实体机,如果想要尝试 Linux 环境,推荐使用 WSL 2.0,亦或用实体机安装 Ubuntu 发行版)。
安装教程有很多,这里就不在赘述了,可自行搜索。总之,安装之后就可以进入系统了。
编辑器
NOI Linux 提供了很多编辑器(没有 Dev C++ www)。
TL;DR:建议使用Code::Blocks。下面详细介绍各个编辑器的利弊。
VS Code
作为编辑器的神(我自己编程的时候全部用的是 VS Code),具有轻量级的优点。但是,因为无法使用 C++ 插件,导致只有最基本的高亮功能,不能补全。因此并不推荐。
Su ...
欧拉回路与欧拉路径
概念
欧拉回路:通过图中每条边恰好一次的回路
欧拉通路:通过图中每条边恰好一次的通路
欧拉图:具有欧拉回路的图
半欧拉图:具有欧拉通路但不具有欧拉回路的图
判断存在欧拉回路/欧拉通路
有向图
欧拉回路:图除一个连通分量之外其余都是孤立点,且所有点入度等于出度。
欧拉通路:有欧拉回路;或图除一个连通分量之外其余都是孤立点,且至多 1 个点出度比入度大 1,至多 1 个点入度比出度大 1,其余点入度等于出度。(特别的,此时通路起点是出度比入度大 1 的点)
无向图
欧拉回路:图连通,且没有度为奇数的点。
欧拉通路:有欧拉回路;或图连通,且至多有两个度为奇数的点。(特别的,此时通路起点是两个奇点中任意一个)
总结
对于一张图,判断是否存在欧拉回路/通路要做两件事情:
把这张图当作无向图,判断是否连通(可以用并查集,或者 dfs)
判断特殊点的个数是否符合要求(奇点、出度入度差 1 的点)
寻找欧拉回路/欧拉通路
使用 dfs,每经过一条边就把这条边删了。最后在递归结束的时候加入栈,即可正确找出路径。
来看一个例子:
对于这张图,实际的运行情况如下:
搜索 1
├ ...
最短路算法
总结一下图论里的最短路。
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歌曲歌词词云
突发奇想,研究一下 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] ...